《算法导论(十三)--红黑树》由会员分享，可在线阅读，更多相关《算法导论(十三)--红黑树（9页珍藏版）》请在金锄头文库上搜索。
1、算法导论（十三）红黑树2013-09-17 17:56:45分类： C/C+原文地址：算法导论（十三）红黑树 作者：yourtommy由前一章我们知道，二叉查找树的性能与树的高度密切相关，所以让树中的元素尽量地平衡在树的两侧，使得树的高度尽量地低，便可提高二叉查找树的性能。红黑树（红黑树（red-black tree）是许多“平衡的”查找树中的一种。红黑树的性质、每个结点或是红的，或是黑的。、根结点是黑的。、每个叶结点（NIL）是黑的。、如果一个结点是红的，则它的两个儿子都是黑的。、对每个结点，从该结点到其子孙的所有路径上包含相同数目的黑结点。红黑树的结点比普通的二叉查找树的结点多了一个颜色属
2、性。下面就是一棵红黑树：可以看到所有的叶结点都是 NIL，且都是黑的。这些叶结点被称为外结点外结点，除了外结点的其它结点便被称为内结点内结点。所有内结点旁标注的数字是该结点的黑高度黑高度，即从该结点出发到达一个叶结点的任意一条路径上的黑色结点的个数从该结点出发到达一个叶结点的任意一条路径上的黑色结点的个数（根据性质5所有路径上黑结点个数一样） 。因为所有的叶结点都是一样的，所以我们可以用一个哨兵元素来表示它：根结点的父亲也可以使用这个哨兵元素。下面来分析下红黑树的高度。我们用 bh(x)来表示结点 x 的黑高度黑高度，先来用归纳法来证明以以 x 为根的子树至少包含为根的子树至少包含2bh(x)
3、 - 1个内结点个内结点：）如果 x 的黑高度为0，则 x 必为叶结点(T.nil)，所以该树包含20 - 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) = 2bh(x) - 2，加上 x 结点本身，则以 x 为根的红黑树至少有2bh(x)-1个内结点。归纳成立。根据红黑树性质4，任何路径上，黑结点的个数
4、不会少于红结点的个数，所以根的黑高度至少是 h/2（h 为树的高度） 。同时根据上面的结论，可得：n 2bh(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.lef
5、t;3 if y.left T.nil4 y.left.parent = x;5 y.parent = x.parent;6 if x.parent = T.nil7 T.root = y;8 else if x = x.parent.left9 x.parent.left = y;10 else11 x.parent.right = y;12 y.left = x;13 x.parent = y;右旋的代码则刚好与左旋对称，把 left 和 right 对换就可以，这里不再赘述。旋转的操作的运行时间为 O(1)。插入插入与二叉查找树相同，每次插入时元素都会被放到叶结点处。RB_INSERT(
6、T, z) 1 y = T.NIL;2 x = T.root;3 while x != T.NIL 4 y = x;5 if z.key x.key6 x = x.left;7 else8 x = x.right9 10 z.parent = y;11 if y = T.nil12 T.root = z;13 else if z.key y.key14 y.left = z;15 else16 y.right = z;17 z.left = T.nil;18 z.right = T.nil;19 z.color = RED;20 RB_INSERT_FIXUP(T, z);红黑树的插入代码与二
7、叉查找树的插入代码大致相同，区别在于最后 z 的左右孩子都设为哨兵元素（黑色地 NIL） ，而且 z 的颜色属性设为红色。新元素插入可能会破坏红黑性质，所以我们要做额外的操作 RB_INSERT_FIXUP 来保持。我 们先看一下这个新增的红结点可能会破坏哪些性质。如果它是根结点，则它破坏了性质2：根必须是黑色的。如果它的父亲是红色的，则它破坏了性质4：红结点必 须有两个黑色的孩子。对于性质1、3、5，它并不会破坏：它是红色的，满足性质1；它的两个孩子是黑色的 T.nil，满足性质3；它是红色的，不会增加黑 高度，满足性质5。对于性质2的破坏，我们只需要把根结点设为黑色即可。下面描述如何应对性
8、质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;/CASE14 if y.color = RED 5 z.parent.color = BLACK;6 y.color = BLACK;7 z.parent.parent.color
9、 = RED;8 z = z.parent.parent;9 /CASE210 else if z = z.parent.right 11 z = z.parent;12 LEFT_ROTATE(T, z);13 /CASE314 z.parent.color = BLACK;15 z.parent.parent.color = RED;16 RIGHT_ROTATE(T, z.parent.parent);17 /zs parent is a right child18 else19 same as the previous “if“ clause with “right“ and “lef
10、t“ 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.nil2 y = z;3 else4 y = SUCCESSOR(z);5 if y.left != T.nil6 x = y.left;7 else8 x = y.right;9 x.par
11、ent = y.parent;10 if y.parent = T.NIL11 T.root = x;12 else if y = y.parent.left13 y.parent.left = x;14 else15 y.parent.right = x;16 if y != z 17 z.key = y.key;18 copy ys satellite data into x;19 20 if y.color = BLACK21 RB_DELETE_FIXUP(T, x);22 return y;注意到，真正从树中移除的结点（代码中的 y，不一定是 z）最多只有一个孩子（如果删除的不是叶节
12、点的话，会找到它的后继，把后继的覆盖要删除的元素，再把后继移除） ，所以被移除的元素会被它的孩子（或 T.nil）代替。如果被移除的元素是红色的话，红黑性质不会受到影响：它不可能是根，所以根仍是黑的；黑高度不会变；它的父亲必定是黑的，所以不会出现红父亲和红孩子的情况。所以上面代码的第20行，只有当被删除的元素是黑的，才需要恢复红黑性质。当移除的元素是黑色的时，经由这个结点的路径的黑高度便少了1。为了（暂时）让红黑树的性质得到保持，我们赋予这个结点的替代结点额外一个黑色属性：在计算黑高度时，树中的所有路径经由这个替代结点时，多计算一次（即加1） 。由于这个替代结点有一个额外的黑色属性，所以我们便
13、要想办法把这个额外的黑色属性去掉。如果替代结点是红色的话，那么我们只要简单的把它变为黑色即可。但如果它是黑色的话，则必须想办法把这个黑色属性转移出去。一共有四种情况需要考虑：考虑替代结点是右孩子的情况，其实一共是八种情况。下面是 RB_DELETE_FIXUP 的代码：RB_DELETE_FIXUP(T, x) 1 while x != root and x.color = BLACK 2 if x = x.parent.left /CASE13 w = x.parent.right; / brother4 if w.color = RED 5 w.color = BLACK;6 x.pare
14、nt.color = RED;7 LEFT_ROTATE (T, px);8 w = x.parent.right;9 /CASE2 10 if w.left.color = BLACK and w.right.right = BLACK 11 w.color = RED; 12 x = x.parent; 13 /CASE3 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; /CASE4 19 w.c
15、olor = 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)。
