算法导论学习笔记——第13章红黑树

浏览数：28 / 时间：2015年06月08日

红黑树

红黑树是一种二叉查找树，但在每个结点上增加一个存储位存储结点的颜色，可以是red或black。通过对任意一条从根到叶的路径上结点颜色的限制，红黑树确保没有任何一条路径比其他路径长出两倍，因而是接近平衡的。

每个结点包含5个域，color，key，left，right，p

满足以下红黑性质：

1、每个结点是红色或黑色

2、根结点是黑色

3、每个叶结点(nil)是黑色

4、如果一个结点是红色，那么它的两个子结点都是黑色

5、对每个结点，从该结点到它每个子孙结点的路径上，黑结点数目相同

左旋转

 1 LEFT-ROTATE(T,x)
 2 y←right[x]
 3 right[x]←left[y]
 4 p[left[y]]←x
 5 p[y]←p[x]
 6 if p[x]==nil[T]
 7     then root[T]←y
 8     else if x=left[p[x]]
 9         then left[p[x]]←y
10         else right[p[x]]←y
11 left[y]←x
12 p[x]←y

插入

 1 RB-INSERT(T,z)
 2 y←nil[T]
 3 x←root[T]
 4 while x!=nil[T]
 5     do y←x
 6         if key[z]<key[x]
 7             then x←left[x]
 8             else x←right[x]
 9 p[z]←y
10 if y=nil[T]
11     then root[T]←z
12     else if key[z]<key[y]
13         then left[y]←z
14         else right[y]←z
15 left[z]←nil[T]
16 right[z]←nil[T]
17 color[z]←RED
18 RB-INSERT-FIXUP(T,z)
19 
20 //保持红黑性质
21 RB-INSERT-FIXUP(T,z)
22 while color[p[x]]=RED
23     do if p[z]=left[p[p[z]]]
24         then y←right[p[p[z]]]
25             if color[y]=RED
26                 then color[p[z]]←BLACK
27                     color[y]←BLACK
28                     color[p[p[z]]]←RED
29                     z←p[p[z]]
30                 else if z=right[p[x]]
31                     then z←p[x]
32                         LEFT-ROTATE(T,z)
33                 color[p[z]]←BLACK
34                 color[p[p[z]]]←RED
35                 RIGHT-ROTATE(T,p[p[z]])
36             else ( same as then clause with "right" and "left" exchanged )
37 color[root[T]]←BLACK

删除

 1 RB-DELETE(T,z)
 2 if left[z]=nil[T] or right[z]=nil[T]
 3     then y←z
 4     else y←TREE-SUCCESSOR(z)
 5 if left[y]!=nil[T]
 6     then x←left[y]
 7     else x←right[y]
 8 p[x]←p[y]
 9 if p[y]=nil[T]
10     then root[T]←x
11     else if y=left[p[y]]
12         then left[p[y]]←x
13         else right[p[y]]←x
14 if y!=z
15     then key[x]←key[y]
16         copy y‘s satellite data into z
17 if color[y]=BLACK
18     then RB-DELETE-FIXUP(T,x)
19 return y
20 
21 //保持红黑性质
22 RB-DELETE-FIXUP(T,x)
23 while x!=root[T] and color[x]=BLACK
24     do if x=left[p[x]]
25         then ω←right[p[x]]
26             if color[ω]=RED
27                 then color[ω]=BLACK
28                     color[p[x]]←RED
29                     LEFT-ROTATE(T,p[x])
30                     ω←right[p[x]]
31             if color[left[ω]]=BLACK and color[right[ω]]=BLACK
32                 then color[ω]←RED
33                     x←p[x]
34                 else if color[right[ω]]=BLACK
35                     then color[left[ω]]←BLACK
36                         color[ω]←RED
37                         RIGHT-ROTATE(T,ω)
38                         ω←right[p[x]]
39             color[ω]←color[p[x]]
40             color[p[x]]←BLACK
41             color[right[ω]]←BLACK
42             LEFT-ROTATE(T,p[x])
43             x←root[T]
44         else ( same as then clause with "right" and "left" exchanged )
45 color[x]←BLACK