2-1 Elementary Sort

发表于 2016-04-17 | 分类于《Algorithms》 notes

在所有的排序算法实现中，只使用比较（Compare）和交换（exchange）两种函数操作。考虑算法的时间复杂度时，也只考虑这两种操作（如果没有交换操作，则考虑数组访问（array access）的代价）；考虑空间复杂度时，需考虑排序算法是在原处修改还是新建了一个数组来存储排序结果。

有时候，我们在比较时，只需要比较每个元素的某个特征来对他们排序（以人为元素，我们可能只比较身高，而不比较他们的其他特征）。以下为求简介，统一称为“比较元素”

阅读全文 »

终于搭好了博客

发表于 2016-04-17 | 分类于杂记

花了两三天的工夫，终于搭好了博客。最先是因为忍受不了csdn blog的markdown排版才打算自己建一个博客。从一开始尝试 worldpress 到后来捣鼓 jekyll，再到现在终于用 hexo 搭好平台，走了不少弯路。

阅读全文 »

1-3 Bags,Queues and Stacks

发表于 2016-04-15 | 分类于《Algorithms》 notes

基本的抽象数据类型涉及若干对象的集合以及在这个集合上定义的一些操作，包括添加、删除和集合中的对象等。下面主要以三种基本类型（Bag Stack Queue）来说明。

我们在用不同的方式表现集合中的元素时，通常也会产生不同的操作效率
使用泛型和循环可以显著地简化客户端代码

阅读全文 »

🔨Network Flow Algorithms

发表于 2000-05-16 | 分类于 Under Construction

🔨Balanced Search Trees

发表于 2000-05-16 | 分类于 Under Construction

在许多应用中，二叉搜索树可以工作得很好，然而在最差情况下（插入一个有序序列），它的性能得不到保证。下面介绍一种平衡搜索树，可以在任何情况下保证 O(logN) 的时间复杂度。

理想情况下，我们希望树的形状是完美平衡的，这样的话，查找效率就是 O(lgN)；然而，对于不可预料的动态插入操作，保持树形状完美平衡的开销太大。我们稍稍放松对完美平衡的要求，便可以对所有操作提供 O(logN) 的保证

2-3搜索树（2-3 search trees）

我们现在允许树的一个节点中有两个值（Key），连接着三个子节点（Link），将这样的节点称为3-节点，原来那样的节点称为2-节点。

————————————————————————

一个2-3搜索树要么是空的，要么是：

一个 2-节点，左链接连接着一棵2-3搜索树（所有的值小于当前节点的值），右链接连接着一棵2-3搜索树（所有的值大于当前结点的值）
一个 3-节点，左链接连接着一棵2-3搜索树（所有的值小于当前节点中较小的那个值），中链接连接着一棵2-3搜索树（所有值在当前结点两个值之间），右链接连接着一棵2-3搜索树（所有的值大于当前结点较大的那个值）

————————————————————————

如果一个2-3搜索树的所有空链接到根节点的距离都相等，那么我们就说这棵2-3搜索树是平衡的。

————————————————————————

搜索（Search）

从根节点开始向下比较，如果与节点中任一值相等，则搜索命中；如果不相等，我们按照左中右连接进行分流；如果遇到空节点，则说明查找失败。

插入到一个 2-节点中（Insert into a 2-node）

用一个 3-节点替换掉原来的 2-节点

插入到只含一个3-节点的2-3树中（Insert into a tree consisting of a single 3-node）

把3-节点变成一个暂时的4-节点，然后把这个4-节点分成三个2-节点

插入到一个父节点是2-节点的3-节点中（Insert into a 3-node whose parent is a 2-node）

把3-节点变成一个暂时的4-节点，然后把这个4-节点分成三个2-节点，将父节点变为一个3-节点

插入到一个父节点是3-节点的3-节点中（Insert into a 3-node whose parent is a 3-node）

向上把每个3-节点变成一个暂时的4-节点，然后把这个4-节点分成三个2-节点，将父节点变为一个暂时的4-节点。由此向上，直到遇到一个2-节点，或到根节点时让整个树增加1层。

怎样分开一个4-节点

————————————————————————

对于一个含有N个元素的2-3树，搜索和插入操作保证最多访问 lgN 个节点

————————————————————————

红黑树（Red-Black BSTs）

编码 3-节点

最自然的方法是利用二分查找树(BST)，然后添加一些信息来标记 3-节点

我们把链接分为两种：

红链接(Red Link)：连接着两个2-节点来表示一个3-节点
黑链接(Black Link)：和BST的链接一样，连接着2-3树

特别地，我们用向左倾斜的红链接连接着的两个2-节点来表示一个3-节点

————————————————————————

红黑树是满足下列调节的具有红黑链接的二叉树：

红链接向左倾斜
没有一个节点连接着两条红链接
红黑树是平衡的：每个空链接到根节点的路径上有相同数量的黑链接

————————————————————————

红黑树即是2-3树，也是BST，所以它结合了BST的高效搜索方法和2-3树的平衡插入特点

颜色表示

在节点的定义里加入一个 bool 变量来表示当前结点与父节点的链接是不是红链接

旋转（Rotation）

在红黑书的实现中，我们暂时允许以下情况：

向右倾斜的红链接
一个节点连接着两个红链接

我们用旋转来修正第一种情况

Node rotateLeft(Node h)
{
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

Node rotateRight(Node h)
{
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

插入到一个 2-节点中（Insert into a 2-node）

如果新插入的节点比原来的节点小，则将它正常插入，然后把新节点的颜色设为红色；如果比原来的大，则正常插入，把新节点的颜色设置为红色，然后进行一次左旋转。

插入到只含一个3-节点的2-3树中（Insert into a tree consisting of a single 3-node）

void flipColors(Node h)
{
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

保持根节点是黑色的

上面的代码有可能会使根节点的颜色变为红色，所以每次插入操作后，我们要让根节点的颜色变回黑色。注意到，每当根节点颜色变红时，树的高度就增加了1。

插入到一个位于底部的 3-节点中（Insert into a 3-node at the bottom）

相当于将一个新的红链接逐层向上传递，直到符合顺序（没有右倾斜的红链接，没有两个红链接连着同一个节点等），或到达根节点。

插入操作的实现

public void put(Key key, Value val)
{
    root = put(root, key, val);
    root.color = BLACK;
}

private Node put(Node h, Key key, Value val)
{
    if (h == null)    return new Node(key, val, 1, RED);

    int cmp = key.compareTo(h.key);
    if        (cmp < 0) h.left  = put(h.left,  key, val);
    else if (cmp > 0) h.right = put(h.right, key, val);
    else h.val = val;

    if (isRed(h.right) && !isRed(h.left))    h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left) h = rotateRight(h);
    if (isRed(h.left) && isRed(h.right))    flipColors(h);

    h.N = size(h.left) + size(h.right) + 1;
    return h;
}