借着stl的由头，讲讲红黑树（二）

这里先来说一下上篇文章没有说到的地方，在stl中，插入红黑树返回的是一个pair, 其中第二个元素表示成功与否，第一个元素表示插入成功的元素对应的迭代器或者插入失败（已经存在的键）的旧的迭代器~

好了，开始今天的主题——红黑树的删除操作~~~

首先，来回顾一下红黑树的性质，这东西是要时刻记在脑袋里面的：

1. 每一个节点多出一个关于颜色的性质：非黑即红

2. 根节点是黑色的

3. 每一个叶子节点（NULL）视为黑色

4. 如果一个节点为红色，那么它的两个孩子的颜色必须都为黑色

5. 对于任意节点来说，从其开始，至其任意子孙当中的叶子结点的每一条路径当中，所包含的黑色节点数目相同。

对于删除操作，对于二叉搜索树来讲，只需要考虑以下三种情况中的前两种，因为第三种可以将当前要删除节点的值与其后继节点的值相互调换，之后转变为情况1,或者情况2：

1)      叶子结点

2)      只有一个孩子不为空

3)      两个孩子都不为空

这样的话，如果要删除一个节点，就先按照正常的二叉搜索树来删除掉该节点，并且

记录注删除节点的颜色，以及递补上来节点的颜色（NULL视为黑色）；如果我们只是如此的话，就可能会违背红黑树的性质2,4, 5。对于以上的情况，算法导论里面提出了一个“额外黑色”的概念，即如果被删除的节点的颜色为黑，需要将其原来的黑色额外的加入到递补上来的节点的颜色上，如果递补上来的颜色为红色，那么直接将其变为黑色即可，如果递补进来的节点为黑色，则黑色和额外的黑色无法累加，需要进行如下四张图的调整（调整的时候要看兄弟节点的颜色，且x为递补上来的节点，s为其兄弟节点）：其中四张图的顺序依次为兄弟节点为红色、兄弟节点为黑色且两个侄子均为黑色、兄弟节点为黑色且近侄子为红色、兄弟节点为黑色且远侄子为红色，其中，只有情况4是可以肯定使得这个递归过程彻底结束的，所以，其他三种情况应该及可能的向其形式靠拢~

当递补上来的节点的兄弟节点为红色时，由于从根本上来讲，A的实际黑高比D（即C和E）低1，通过变换颜色以及旋转无法直接解决问题，，所以需要将x的兄弟变为黑色，以便后续求解，同时，需要保证B的parent的该子树下的黑高尽可能不变；

当x的兄弟节点为黑色，且两个侄子的颜色均为黑色的时候，最简单的做法就是将兄弟节点的颜色变为红色，x指向其父节点，递归向上，去除“额外的黑色”

由于下面一种情况是比较好解决的，所以这种情况就需要委屈一下，尽量变为下边一种情况喽~这里不要害怕E的颜色为红色，因为在下一步操作中，D的颜色会被变为黑色的~

这种情况是肯定会终止的，现在C，e, f 的黑高与A相同，B的parent的该方向的子树的黑高为：BH(A) + 1 + B->color==BLACK?1:0;即BH(D)

但是A所在的子树理应多出一个黑高才能使之结束，这样，就将B，D颜色对调，E的颜色置为黑色，对B再进行一次左旋就行了~

整个红黑树以及测试代码奉上：

点击(此处)折叠或打开

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. struct RB_tree_node{
   
5.     int val;
   
6.     bool color;// false: red; true: black
   
7.     struct RB_tree_node *parent;
   
8.     struct RB_tree_node *lchild;
   
9.     struct RB_tree_node *rchild;
   
10.     RB_tree_node(int value):val(value), color(false), parent(NULL), lchild(NULL), rchild(NULL){}
    
11. };
    
12. struct RB_tree_node *root = NULL;
    
13. struct RB_tree_node *Left_Rotate(struct RB_tree_node *x){
    
14.     struct RB_tree_node *y = x->rchild;
    
15.     bool flag = false;
    
16.     if( root == x) flag = true;
    
17.     x->rchild = y->lchild;
    
18.     if( y->lchild != NULL) y->lchild->parent = x;
    
19.     y->parent = x->parent;
    
20.     if( !flag ){
    
21.         if( x == x->parent->lchild)x->parent->lchild = y;
    
22.         else x->parent->rchild= y;
    
23.     }
    
24.     y->lchild = x;
    
25.     x->parent = y;
    
26.     if(flag) root = y;
    
27.     return y;
    
28. }
    
29. struct RB_tree_node *Right_Rotate(struct RB_tree_node *y){
    
30.     struct RB_tree_node *x = y->lchild;
    
31.     bool flag =false;
    
32.     if( y == root) flag = true;
    
33.     y->lchild = x->rchild;
    
34.     if(x->rchild != NULL) x->rchild->parent = y;
    
35.     x->parent = y->parent;
    
36.     if(!flag){
    
37.         if( y==y->parent->lchild) y->parent->lchild = x;
    
38.         else y->parent->rchild = x;
    
39.     }
    
40.     x->rchild = y;
    
41.     y->parent = x;
    
42.     if(flag) root = x;
    
43.     return x;
    
44. }
    
45. struct RB_tree_node *Get_Sibling(struct RB_tree_node *cur){
    
46.     if( cur->parent == NULL) return NULL;
    
47.     if( cur == cur->parent->lchild) return cur->parent->rchild;
    
48.     else return cur->parent->lchild;
    
49. }
    
50. struct RB_tree_node *Get_Uncle(struct RB_tree_node *cur){
    
51.     if(cur->parent == NULL) return NULL;
    
52.     else return(Get_Sibling(cur->parent));
    
53. }
    
54. void insert_fix( struct RB_tree_node *cur){
    
55.     while(cur->parent != NULL && cur->parent->color == false){
    
56.         if(cur->parent == cur->parent->parent->lchild){
    
57.             struct RB_tree_node *uncle = Get_Uncle(cur);
    
58.             if(uncle != NULL && uncle->color == false){
    
59.                 cur->parent->color = true;
    
60.                 uncle->color = true;
    
61.                 cur->parent->parent->color = false;
    
62.                 cur = cur->parent->parent;
    
63.             }
    
64.             else{
    
65.                 if(cur == cur->parent->rchild){//内插，需要多一步旋转
    
66.                     Left_Rotate(cur->parent);
    
67.                     cur=cur->lchild;
    
68.                 }
    
69.                 //外插情况
    
70.                 cur->parent->color = true;
    
71.                 cur->parent->parent->color = false;
    
72.                 Right_Rotate(cur->parent->parent);
    
73.             }
    
74.         }else{//父节点是祖节点的右孩子
    
75.             struct RB_tree_node *uncle = Get_Uncle(cur);
    
76.             if(uncle != NULL && uncle->color == false){
    
77.                 cur->parent->color = true;
    
78.                 uncle->color = true;
    
79.                 cur->parent->parent->color = false;
    
80.                 cur = cur->parent->parent;
    
81.             }
    
82.             else{
    
83.                 if(cur == cur->parent->lchild){//内插，需要多一步旋转
    
84.                     Right_Rotate(cur->parent);
    
85.                     cur=cur->rchild;
    
86.                 }
    
87.                 //外插情况
    
88.                 cur->parent->color = true;
    
89.                 cur->parent->parent->color = false;
    
90.                 Left_Rotate(cur->parent->parent);
    
91.             }
    
92.         }
    
93.     }
    
94.     root->color = true;
    
95. }
    
96. void insert(int val){
    
97.     struct RB_tree_node *cur = new RB_tree_node(val);
    
98.     if( root == NULL){
    
99.         cur->color = true; root = cur; return;
    
100.     }
     
101.     struct RB_tree_node *x = root, *y;
     
102.     while(x != NULL){
     
103.         y=x;
     
104.         if (val < x->val) x = x->lchild;
     
105.         else x = x->rchild;
     
106.     }
     
107.     if( val < y->val) y->lchild = cur;
     
108.     else y->rchild = cur;
     
109.     cur->parent = y;
     
110.     if( y->color == false)insert_fix(cur);
     
111. }
     
112. struct RB_tree_node *Find(int val){
     
113.     struct RB_tree_node *cur = root;
     
114.     while( cur ){
     
115.         if(cur->val == val) break;
     
116.         else if(cur->val > val) cur = cur->lchild;
     
117.         else cur = cur->rchild;
     
118.     }
     
119.     return cur;
     
120. }
     
121. void Transplant(struct RB_tree_node *u, struct RB_tree_node *v){
     
122.     if( u->parent == NULL) root = v;
     
123.     else if(u == u->parent->lchild) u->parent->lchild = v;
     
124.     else u->parent->rchild = v;
     
125.     if(v) v->parent = u->parent;
     
126. }
     
127. void Delete_fix(struct RB_tree_node *x){
     
128.     while(x != root && x->color == true){
     
129.         if(x == x->parent->lchild){
     
130.             struct RB_tree_node *w = x->parent->rchild;
     
131.             if( w->color == false){
     
132.                 w->color = true;
     
133.                 x->parent->color = false;
     
134.                 Left_Rotate(x->parent);
     
135.                 w = x->parent->rchild;
     
136.             }
     
137.             if( w->lchild->color==true && w->rchild->color == true){
     
138.                 w->color = false;x = x->parent;
     
139.             }else{
     
140.                 if(w->rchild->color == true){
     
141.                     w->lchild->color = true;
     
142.                     w->color = false;
     
143.                     Right_Rotate(w);
     
144.                     w = x->parent->rchild;
     
145.                 }
     
146.                 w->color = x->parent->color;
     
147.                 x->parent->color = true;
     
148.                 w->rchild->color = true;
     
149.                 Left_Rotate(x->parent);
     
150.                 x = root;
     
151.             }
     
152.         }else{
     
153.             struct RB_tree_node *w = x->parent->lchild;
     
154.             if( w->color == false){
     
155.                 w->color = true;
     
156.                 x->parent->color = false;
     
157.                 Right_Rotate(x->parent);
     
158.                 w = x->parent->lchild;
     
159.             }
     
160.             if( w->lchild->color==true && w->rchild->color == true){
     
161.                 w->color = false;x = x->parent;
     
162.             }else{
     
163.                 if(w->lchild->color == true){
     
164.                     w->rchild->color = true;
     
165.                     w->color = false;
     
166.                     Left_Rotate(w);
     
167.                     w = x->parent->lchild;
     
168.                 }
     
169.                 w->color = x->parent->color;
     
170.                 x->parent->color = true;
     
171.                 w->lchild->color = true;
     
172.                 Right_Rotate(x->parent);
     
173.                 x = root;
     
174.             }
     
175.         }
     
176.     }
     
177.     x->color = true;
     
178. }
     
179. struct RB_tree_node *Delet_Black_leaf(struct RB_tree_node *s){
     
180.     if(s == s->parent->rchild){
     
181.         if( s->color == false){
     
182.             s->color = true;
     
183.             s->parent->color = false;
     
184.             Left_Rotate(s->parent);
     
185.             s = s->lchild->rchild;
     
186.         }
     
187.         if( s->lchild==NULL && s->rchild== NULL ){
     
188.             s->color = false;
     
189.             return s->parent;
     
190.         }else{
     
191.             if(s->rchild == NULL){
     
192.                 s->lchild->color = true;
     
193.                 s->color = false;
     
194.                 Right_Rotate(s);
     
195.                 s = s->parent;
     
196.             }
     
197.             s->color = s->parent->color;
     
198.             s->parent->color = true;
     
199.             s->rchild->color = true;
     
200.             Left_Rotate(s->parent);
     
201.             return NULL;
     
202.         }
     
203.     }else{
     
204.         if( s->color == false){
     
205.             s->color = true;
     
206.             s->parent->color = false;
     
207.             Right_Rotate(s->parent);
     
208.             s = s->rchild->lchild;
     
209.         }
     
210.         if( s->lchild==NULL && s->rchild== NULL ){
     
211.             s->color = false;
     
212.             return s->parent;
     
213.         }else{
     
214.             if(s->lchild == NULL){
     
215.                 s->rchild->color = true;
     
216.                 s->color = false;
     
217.                 Left_Rotate(s);
     
218.                 s = s->parent;
     
219.             }
     
220.             s->color = s->parent->color;
     
221.             s->parent->color = true;
     
222.             s->rchild->color = true;
     
223.             Right_Rotate(s->parent);
     
224.             return NULL;
     
225.         }
     
226.     }
     
227. }
     
228. void Delete(int val){
     
229.     struct RB_tree_node *cur = Find(val);
     
230.     if(!cur) return;
     
231.     struct RB_tree_node *y = cur, *successor, *sibling;
     
232.     bool original_color = y->color;
     
233.     if( cur->lchild == NULL) {
     
234.         successor = cur->rchild;
     
235.         sibling = Get_Sibling(y);
     
236.         Transplant(cur, cur->rchild);
     
237.     }
     
238.     else if( cur->rchild == NULL){
     
239.         successor = cur->lchild;
     
240.         sibling = Get_Sibling(y);
     
241.         Transplant(cur, cur->lchild);
     
242.     }
     
243.     else{
     
244.         y = cur->rchild;
     
245.         while(y->lchild){
     
246.             y = y->lchild;
     
247.         }
     
248.         original_color = y->color;
     
249.         successor = y->rchild;
     
250.         sibling = Get_Sibling(y);
     
251.         cur->val = y->val;
     
252.         Transplant(y, y->rchild);
     
253.     }
     
254.     if(original_color){
     
255.         if(successor == NULL){
     
256.             successor = Delet_Black_leaf(sibling);
     
257.         }
     
258.         if( successor)
     
259.             Delete_fix(successor);
     
260.     }
     
261.     delete cur;
     
262. }
     
263. int main()
     
264. {
     
265.     int arr[] = {10, 7, 8, 15,5, 6,11, 13, 12 };//9
     
266.     for(int i = 0; i < 9; i++){
     
267.         insert(arr[i]);
     
268.     }
     
269.     Delete(15);
     
270.     Delete(12);
     
271.     Delete(10);
     
272.     Delete(6);
     
273.     Delete(8);
     
274.     return 0;
     
275. }

由于我没有采用算法导论当中的指定T.nil 来充当辅助节点，所以我在处理删除黑色叶子结点的时候，多谢了一个函数，其形式是照搬的Delete_fix函数~