算法导论（十三）－－红黑树

由前一章我们知道，二叉查找树的性能与树的高度密切相关，所以让树中的元素尽量地平衡在树的两侧，使得树的高度尽量地低，便可提高二叉查找树的性能。红黑树（red-black tree）是许多“平衡的”查找树中的一种。

红黑树的性质

１、每个结点或是红的，或是黑的。
２、根结点是黑的。
３、每个叶结点（NIL）是黑的。
４、如果一个结点是红的，则它的两个儿子都是黑的。
５、对每个结点，从该结点到其子孙的所有路径上包含相同数目的黑结点。

红黑树的结点比普通的二叉查找树的结点多了一个颜色属性。下面就是一棵红黑树：

可以看到所有的叶结点都是NIL，且都是黑的。这些叶结点被称为外结点，除了外结点的其它结点便被称为内结点。所有内结点旁标注的数字是该结点的黑高度，即从该结点出发到达一个叶结点的任意一条路径上的黑色结点的个数（根据性质5所有路径上黑结点个数一样）。

因为所有的叶结点都是一样的，所以我们可以用一个哨兵元素来表示它：

根结点的父亲也可以使用这个哨兵元素。

下面来分析下红黑树的高度。

我们用bh(x)来表示结点x的黑高度，先来用归纳法来证明以x为根的子树至少包含2^bh(x) - 1个内结点：
１）如果x的黑高度为0，则x必为叶结点(T.nil)，所以该树包含2^0 - 1 = 0个结点。
２） 若x的孩子是红色的，则该孩子结点的黑高度与x一样，为bh(x)；如果x是黑色的，则该孩子结点的黑高度比x少1，为bh(x)-1。所以x的孩子结点 的黑高度至少为bh(x)-1。根据归纳假设，x的两个子树里的元素个数至少为(2^(bh(x)-1) - 1) + (2^(bh(x)-1) - 1) = 2^bh(x) - 2，加上x结点本身，则以x为根的红黑树至少有2^bh(x)-1个内结点。归纳成立。

根据红黑树性质4，任何路径上，黑结点的个数不会少于红结点的个数，所以根的黑高度至少是h/2（h为树的高度）。同时根据上面的结论，可得：
n ≥ 2^bh(x) - 1 ≥ 2^(h/2) - 1
可求出h ≤ 2*lg(n+1)，所以红黑树的高度为O(lg(n))。

 

旋转

我们可以通过旋转来改变某些结点在树中的位置而不破坏二叉查找树的性质。

可是看到子树b是所有的元素值都介于结点A和B之间，在旋转操作后b仍然处在两结点之间，二叉查找树的性质得以保持。

下面是左旋（把x结点左移，使得其右孩子y代替x的位置）的代码：

LEFT_ROTATE(T, x) {
1      y = x.right;
2      x.right = y.left;
3      if y.left ≠ T.nil
4           y.left.parent = x;
5   y.parent = x.parent;
6   if x.parent == T.nil
7            T.root = y;
8      else if x == x.parent.left
9            x.parent.left = y;
10    else
11    x.parent.right = y;
12    y.left = x;
13    x.parent = y;
}

右旋的代码则刚好与左旋对称，把left和right对换就可以，这里不再赘述。旋转的操作的运行时间为O(1)。

插入

与二叉查找树相同，每次插入时元素都会被放到叶结点处。

RB_INSERT(T, z) {
1      y = T.NIL;
2      x = T.root;
3      while x != T.NIL {
4            y = x;
5            if z.key < x.key
6                  x = x.left;
7           else
8                  x = x.right
9      }
10    z.parent = y;
11    if y == T.nil
12          T.root = z;
13    else if z.key < y.key
14          y.left = z;
15    else
16          y.right = z;
17    z.left = T.nil;
18    z.right = T.nil;
19    z.color = RED;
20    RB_INSERT_FIXUP(T, z);
}

红黑树的插入代码与二叉查找树的插入代码大致相同，区别在于最后z的左右孩子都设为哨兵元素（黑色地NIL），而且z的颜色属性设为红色。新元素插入可能会破坏红黑性质，所以我们要做额外的操作RB_INSERT_FIXUP来保持。

我 们先看一下这个新增的红结点可能会破坏哪些性质。如果它是根结点，则它破坏了性质2：根必须是黑色的。如果它的父亲是红色的，则它破坏了性质4：红结点必 须有两个黑色的孩子。对于性质1、3、5，它并不会破坏：它是红色的，满足性质1；它的两个孩子是黑色的T.nil，满足性质3；它是红色的，不会增加黑 高度，满足性质5。

对于性质2的破坏，我们只需要把根结点设为黑色即可。下面描述如何应对性质4的破坏，它分为三种情况：

其实一共是六种情况，即父结点是左孩子的三种情况加上父结点是右孩子的三种情况。但其它三种情况与前三种情况对称，所以不再赘述。

下面是相应的代码：

RB_INSERT_FIXUP(T, z) {
1     while z.parent.color == RED {
2            if z.parent == z.parent.parent.left {
3                  y = z.parent.parent.right;
//   CASE 1
4                  if y.color == RED {
5                        z.parent.color = BLACK;
6                        y.color = BLACK;
7                        z.parent.parent.color = RED;
8                        z = z.parent.parent;
9                  }
//   CASE 2
10                else if z == z.parent.right {
11                      z = z.parent;
12                     LEFT_ROTATE(T, z);
13                }
//   CASE 3
14                z.parent.color = BLACK;
15                z.parent.parent.color = RED;
16               RIGHT_ROTATE(T, z.parent.parent);
17          }
//    z's parent is a right child
18          else
19                 same as the previous "if" clause with "right" and "left" extranged.
20    }
21    T.root.color = BLACK;
}

最后一行保证了性质2。RB_INSERT_FIXUP操作可能会从叶部一直到根部，所以它的运行时间为O(h) = O(lg(n))。

删除
红黑树的删除同样也是基于普通二叉查找树的删除，并同时维护其红黑性质。下面是删除的代码：

RB_DELETE(T, z) {
1      if z.left == T.nil or z.right == T.nil
2            y = z;
3   else
4            y = SUCCESSOR(z);
5      if y.left != T.nil
6            x = y.left;
7   else
8     x = y.right;
9      x.parent = y.parent;
10    if y.parent == T.NIL
11          T.root = x;
12    else if y == y.parent.left
13          y.parent.left = x;
14    else
15          y.parent.right = x;
16    if y != z {
17          z.key = y.key;
18          copy y's satellite data into x;
19    }
20    if y.color == BLACK
21          RB_DELETE_FIXUP(T, x);
22    return y;
}

注意到，真正从树中移除的结点（代码中的y，不一定是z）最多只有一个孩子（如果删除的不是叶节点的话，会找到它的后继，把后继的覆盖要删除的元素，再把后继移除），所以被移除的元素会被它的孩子（或T.nil）代替。
如果被移除的元素是红色的话，红黑性质不会受到影响：它不可能是根，所以根仍是黑的；黑高度不会变；它的父亲必定是黑的，所以不会出现红父亲和红孩子的情况。所以上面代码的第20行，只有当被删除的元素是黑的，才需要恢复红黑性质。

当移除的元素是黑色的时，经由这个结点的路径的黑高度便少了1。为了（暂时）让红黑树的性质得到保持，我们赋予这个结点的替代结点额外一个黑色属性：在计算黑高度时，树中的所有路径经由这个替代结点时，多计算一次（即加1）。

由于这个替代结点有一个额外的黑色属性，所以我们便要想办法把这个额外的黑色属性去掉。如果替代结点是红色的话，那么我们只要简单的把它变为黑色即可。但如果它是黑色的话，则必须想办法把这个黑色属性转移出去。一共有四种情况需要考虑：

考虑替代结点是右孩子的情况，其实一共是八种情况。下面是RB_DELETE_FIXUP的代码：

RB_DELETE_FIXUP(T, x) {
1   while x != root and x.color == BLACK {
2            if x == x.parent.left {
//   CASE 1
3                  w = x.parent.right; // brother
4                  if w.color == RED {
5                        w.color = BLACK;
6         x.parent.color = RED;
7                       LEFT_ROTATE (T, p[x]);
8                        w = x.parent.right;
9                  }
//   CASE 2
10                if w.left.color == BLACK and w.right.right == BLACK {
11                      w.color = RED;
12                      x = x.parent;
13                }
//   CASE 3
14                else if w.right.color == BLACK {
15                      w.left.color = BLACK;
16                     w.color = RED;
17                     RIGHT_ROTATE(T, w);
18                      w = x.parent.right;
//   CASE 4
19                      w.color = x.parent.color;
20                      x.parent.color = BLACK;
21                      w.right.color = BLACK;
22                     LEFT_ROTATE(T, x.parent);
23                      x = T.root;
24                }
25          }
26          else
27                same as the previous "if" clause with "right" and "left" exchanged;
28  }
29    x.color = BLACK;
}

RB_DELETE_FIXUP中，情况一运行O(1)进行情况二、三、四，情况三运行O(1)时间进入情况四，而情况四运行O(1)时间终止循环。只由每次迭代都进入情况二直到根结点的话，运行时间为O(h) = O(lg(n))。