版权声明：本文为博主原创文章，未经博主允许不得转载。技术博客 http://blog.csdn.net/stecdeng 技术交流群 群号码：324164944 欢迎c c++ windows驱动爱好者 服务器程序员沟通交流

学习算法 还是建议看看算法导论

算法导论第三版 如果不看数学推导 仅看伪代码 难度还是适中

本系列只是记录我的学习心得 和伪代码转化代码的过程

深入学习 还是建议大家看看算法书籍 教程更加系统。

本文参考算法导论第13章节 红黑树

代码由本人写成

转载请标明出处

先看看不做颜色处理的删除

不做颜色处理的删除基本就和二叉树类似

如果删除节点没有子树 最简单 直接删除

如果待删除的节点只有一个儿子(左子树或者右子树) 那么删除该节点 儿子补上即可

[cpp] view plain copy

 

 

1. void RBTransplant(std::shared_ptr<node>& root,  
2.     std::shared_ptr<node> u, std::shared_ptr<node> v) {  
3.     if (u->parent_ == nil)  
4.         root = v;  
5.     else if (u == u->parent_->left_)  
6.         u->parent_->left_ = v;  
7.     else  
8.         u->parent_->right_ = v;  
9.     v->parent_ = u->parent_;  
10. }  

过程如图:

若是待删除节点有两个子树 那么寻找待删除节点右子树最小的节点，这个节点要么就是删除节点右子树，要么就是沿着删除节点右子树向左遍历的终点

如图： 如果7是待删除节点，那么目标不是11 就是9

将删除节点和目标节点值互换 在处理目标节点  那么就把两棵子树节点的删除更改为无子树或者单子树节点的删除，很巧妙！

伪代码如图

删除代码及测试代码如下(删除未调整颜色版本,可运行)

[cpp] view plain copy

 

 

1. // rbTreeTest.cpp : 定义控制台应用程序的入口点。  
2. //  
3.   
4. #include "stdafx.h"  
5. #include <memory>  
6. #include <iostream>  
7.   
8. using namespace std;  
9.   
10. enum Color {  
11.     red = 1,  
12.     black  
13. };  
14.   
15. struct node {  
16.     Color color_;  
17.     std::shared_ptr<node> left_;  
18.     std::shared_ptr<node> right_;  
19.     std::shared_ptr<node> parent_;  
20.     int value_;  
21.     node() {  
22.         left_ = right_ = parent_ = nullptr;  
23.         value_ = -1;  
24.         color_ = black;  
25.     }  
26. };  
27.   
28. std::shared_ptr<node> nil(new node);  
29.   
30.   
31. std::shared_ptr<node> CreateNode(Color color, int i) {  
32.     std::shared_ptr<node> p(new node);  
33.     p->color_ = color;  
34.     p->left_ = nil;  
35.     p->right_ = nil;  
36.     p->parent_ = nil;  
37.     p->value_ = i;  
38.     return p;  
39. }  
40.   
41. void RightRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
42.     std::shared_ptr<node> y = x->left_;  
43.     x->left_ = y->right_;  
44.     if (y->right_ != nil)  
45.         y->right_->parent_ = x;  
46.     y->parent_ = x->parent_;  
47.     if (x->parent_ == nil) {  
48.         root = y;  
49.     }  
50.     else if (x->parent_->left_ == x) {  
51.         x->parent_->left_ = y;  
52.     }  
53.     else {  
54.         x->parent_->right_ = y;  
55.     }  
56.   
57.     y->right_ = x;  
58.     x->parent_ = y;  
59. }  
60.   
61. void LeftRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
62.     std::shared_ptr<node> y = x->right_;  
63.     x->right_ = y->left_;  
64.     if (y->left_ != nil)  
65.         y->left_->parent_ = x;  
66.   
67.     y->parent_ = x->parent_;  
68.     if (x->parent_ == nil) {  
69.         root = y;  
70.     }  
71.     else if (x->parent_->left_ == x) {  
72.         x->parent_->left_ = y;  
73.     }  
74.     else {  
75.         x->parent_->right_ = y;  
76.     }  
77.     y->left_ = x;  
78.     x->parent_ = y;  
79. }  
80.   
81. void PrinTree(std::shared_ptr<node> root) {  
82.     if (root == nil) {  
83.         std::cout << "nil:" << ":color-" << root->color_ << " ; " << std::endl << std::endl;  
84.         return;  
85.     }  
86.     std::cout << root->value_ << ":color-" << root->color_ << "; address:" << root << std::endl;  
87.     if (root->parent_ == nil) {  
88.         std::cout << "parent_:" << "nil" << std::endl;  
89.     }  
90.     else {  
91.         std::cout << "parent_:" << root->parent_->value_ << std::endl;  
92.     }  
93.   
94.     if (root->left_ == nil) {  
95.         std::cout << "left_:" << "nil" << std::endl;  
96.     }  
97.     else {  
98.         std::cout << "left_:" << root->left_->value_ << std::endl;  
99.     }  
100.   
101.   
102.     if (root->right_ == nil) {  
103.         std::cout << "right_:" << "nil" << std::endl;  
104.     }  
105.     else {  
106.         std::cout << "right_:" << root->right_->value_ << std::endl;  
107.     }  
108.   
109.     std::cout << std::endl;  
110.   
111.   
112.     if (root->left_ != nil)  
113.         PrinTree(root->left_);  
114.     if (root->right_ != nil)  
115.         PrinTree(root->right_);  
116. }  
117.   
118. void RBInsertFixup(std::shared_ptr<node>& root, std::shared_ptr<node> z) {  
119.     while (z->parent_->color_ == red) {   //插入节点Z是红色 若Z父节点也是红色则需要调整  
120.         if (z->parent_ == z->parent_->parent_->left_) {  // 父节点是左子树的情况  
121.             std::shared_ptr<node> y = z->parent_->parent_->right_;  
122.             if (y->color_ == red) {                   //  情况1  
123.                 z->parent_->color_ = black;  
124.                 y->color_ = black;  
125.                 z->parent_->parent_->color_ = red;  
126.                 z = z->parent_->parent_;  
127.             }  
128.             else {  
129.                 if (z == z->parent_->right_) {  
130.                     z = z->parent_;                  //  情况2  
131.                     LeftRotate(root, z);  
132.                 }  
133.                 z->parent_->color_ = black;           //  情况3  
134.                 z->parent_->parent_->color_ = red;  
135.                 RightRotate(root, z->parent_->parent_);  
136.             }  
137.         }  
138.         else {// 父节点是右子树的情况 与上面判断处理均是镜像对称  
139.             std::shared_ptr<node> y = z->parent_->parent_->left_;  
140.             if (y->color_ == red) {  
141.                 z->parent_->color_ = black;  
142.                 y->color_ = black;  
143.                 z->parent_->parent_->color_ = red;  
144.                 z = z->parent_->parent_;  
145.             }  
146.             else {  
147.                 if (z == z->parent_->left_) {  
148.                     z = z->parent_;  
149.                     RightRotate(root, z);  
150.                 }  
151.                 z->parent_->color_ = black;  
152.                 z->parent_->parent_->color_ = red;  
153.                 LeftRotate(root, z->parent_->parent_);  
154.             }  
155.         }  
156.     }//while (z->parent_->color_ == red)  
157.     root->color_ = black;  
158. }//function end  
159.   
160. void RBInsert(std::shared_ptr<node>& root, std::shared_ptr<node> ins) {  
161.     std::shared_ptr<node> y = nil;  
162.     std::shared_ptr<node> x = root;  
163.   
164.     while (x != nil) {  
165.         y = x;  
166.         if (ins->value_ < x->value_) {  
167.             x = x->left_;  
168.         }  
169.         else {  
170.             x = x->right_;  
171.         }  
172.     }  
173.     ins->parent_ = y;  
174.     if (y == nil) {  
175.         root = ins;  
176.     }  
177.     else if (ins->value_ < y->value_) {  
178.         y->left_ = ins;  
179.     }  
180.     else {  
181.         y->right_ = ins;  
182.     }  
183.     ins->left_ = ins->right_ = nil;  
184.     ins->color_ = red;  
185.     // todo  fixup  
186.     RBInsertFixup(root, ins);  
187. }  
188.   
189. std::shared_ptr<node> CreateRB() {  
190.     std::shared_ptr<node> root = nil;  
191.     std::shared_ptr<node> x = CreateNode(red, 7);  
192.     RBInsert(root, x);  
193.   
194.   
195.     x = CreateNode(red, 4);  
196.     RBInsert(root, x);  
197.   
198.     x = CreateNode(red, 11);  
199.     RBInsert(root, x);  
200.   
201.     x = CreateNode(red, 3);  
202.     RBInsert(root, x);  
203.   
204.   
205.       
206.     //PrinTree(root);  
207.     //std::cout << std::endl;  
208.   
209.     return root;  
210. }  
211.   
212. //=============================================  
213. // delete test  
214. std::shared_ptr<node> RBMinimum(std::shared_ptr<node> n) {  
215.     while (n->left_ != nil) {  
216.         n = n->left_;  
217.     }  
218.     return n;  
219. }  
220.   
221. std::shared_ptr<node> RBMaximum(std::shared_ptr<node> n) {  
222.     while (n->right_ != nil) {  
223.         n = n->right_;  
224.     }  
225.     return n;  
226. }  
227.   
228. std::shared_ptr<node> RBSuccessor(std::shared_ptr<node> n) {  
229.     if (n->right_ != nil)  
230.         return RBMinimum(n->right_);  
231.     std::shared_ptr<node> y = n->parent_;  
232.     while (y != nil && n == y->right_) {  
233.         n = y;  
234.         y = y->parent_;  
235.     }  
236.     return y;  
237. }  
238.   
239. void RBTransplant(std::shared_ptr<node>& root,  
240.     std::shared_ptr<node> u, std::shared_ptr<node> v) {  
241.     if (u->parent_ == nil)  
242.         root = v;  
243.     else if (u == u->parent_->left_)  
244.         u->parent_->left_ = v;  
245.     else  
246.         u->parent_->right_ = v;  
247.     v->parent_ = u->parent_;  
248. }  
249.   
250. void RBDelete(std::shared_ptr<node>& root,std::shared_ptr<node> z) {  
251.     if (root == nil || z == nil) {  
252.         return;  
253.     }  
254.     std::shared_ptr<node> y = z;  
255.     Color original_color = y->color_;  
256.     std::shared_ptr<node> x;  
257.     if (z->left_ == nil) {  
258.         x = z->right_;  
259.         RBTransplant(root, z, z->right_);  
260.     }  
261.     else if (z->right_ == nil) {  
262.         x = z->left_;  
263.         RBTransplant(root, z, z->left_);  
264.     }  
265.     else {  
266.         y = RBMinimum(z->right_);  
267.         original_color = y->color_;  
268.         x = y->right_;  
269.         if (y->parent_ == z)  
270.             x->parent_ = y;  
271.         else {  
272.             RBTransplant(root,y,y->right_);  
273.             y->right_ = z->right_;  
274.             y->right_->parent_ = y;  
275.         }  
276.         RBTransplant(root,z,y);  
277.         y->left_ = z->left_;  
278.         y->left_->parent_ = y;  
279.         y->color_ = z->color_;  
280.     }  
281.     if (y->color_ == black) {}  
282.         //RBDeleteFixup(root,x);  
283.           
284. }  
285.   
286. //=============================================  
287.   
288. int main()  
289. {  
290.     std::shared_ptr<node> root = CreateRB();  
291.     PrinTree(root);  
292.     std::cout << "===========================" << std::endl;  
293.       
294.     RBDelete(root,root);  
295.     PrinTree(root);  
296.     std::cout << std::endl;  
297.   
298.     RBDelete(root, root);  
299.     PrinTree(root);  
300.     std::cout << std::endl;  
301.   
302.     RBDelete(root, root);  
303.     PrinTree(root);  
304.     std::cout << std::endl;  
305.   
306.     RBDelete(root, root);  
307.     PrinTree(root);  
308.     std::cout << std::endl;  
309.   
310.     RBDelete(root, root);  
311.     PrinTree(root);  
312.     std::cout << std::endl;  
313.       
314.   
315.   
316.     return 0;  
317. }  

最后全部代码如下  增删 打印 调整功能 可运行调试

 运行效果

[cpp] view plain copy

 

 

1. // rbTreeTest.cpp : 定义控制台应用程序的入口点。  
2. //  
3.   
4. #include "stdafx.h"  
5. #include <memory>  
6. #include <iostream>  
7.   
8. using namespace std;  
9.   
10. enum Color {  
11.     red = 1,  
12.     black  
13. };  
14.   
15. struct node {  
16.     Color color_;  
17.     std::shared_ptr<node> left_;  
18.     std::shared_ptr<node> right_;  
19.     std::shared_ptr<node> parent_;  
20.     int value_;  
21.     node() {  
22.         left_ = right_ = parent_ = nullptr;  
23.         value_ = -1;  
24.         color_ = black;  
25.     }  
26. };  
27.   
28. std::shared_ptr<node> nil(new node);  
29.   
30.   
31. std::shared_ptr<node> CreateNode(Color color, int i) {  
32.     std::shared_ptr<node> p(new node);  
33.     p->color_ = color;  
34.     p->left_ = nil;  
35.     p->right_ = nil;  
36.     p->parent_ = nil;  
37.     p->value_ = i;  
38.     return p;  
39. }  
40.   
41. void RightRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
42.     std::shared_ptr<node> y = x->left_;  
43.     x->left_ = y->right_;  
44.     if (y->right_ != nil)  
45.         y->right_->parent_ = x;  
46.     y->parent_ = x->parent_;  
47.     if (x->parent_ == nil) {  
48.         root = y;  
49.     }  
50.     else if (x->parent_->left_ == x) {  
51.         x->parent_->left_ = y;  
52.     }  
53.     else {  
54.         x->parent_->right_ = y;  
55.     }  
56.   
57.     y->right_ = x;  
58.     x->parent_ = y;  
59. }  
60.   
61. void LeftRotate(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
62.     std::shared_ptr<node> y = x->right_;  
63.     x->right_ = y->left_;  
64.     if (y->left_ != nil)  
65.         y->left_->parent_ = x;  
66.   
67.     y->parent_ = x->parent_;  
68.     if (x->parent_ == nil) {  
69.         root = y;  
70.     }  
71.     else if (x->parent_->left_ == x) {  
72.         x->parent_->left_ = y;  
73.     }  
74.     else {  
75.         x->parent_->right_ = y;  
76.     }  
77.     y->left_ = x;  
78.     x->parent_ = y;  
79. }  
80.   
81. void PrinTree(std::shared_ptr<node> root) {  
82.     if (root == nil) {  
83.         std::cout << "nil:" << ":color-" << root->color_ << " ; " << std::endl << std::endl;  
84.         return;  
85.     }  
86.     std::cout << root->value_ << ":color-" << root->color_ << "; address:" << root << std::endl;  
87.     if (root->parent_ == nil) {  
88.         std::cout << "parent_:" << "nil" << std::endl;  
89.     }  
90.     else {  
91.         std::cout << "parent_:" << root->parent_->value_ << std::endl;  
92.     }  
93.   
94.     if (root->left_ == nil) {  
95.         std::cout << "left_:" << "nil" << std::endl;  
96.     }  
97.     else {  
98.         std::cout << "left_:" << root->left_->value_ << std::endl;  
99.     }  
100.   
101.   
102.     if (root->right_ == nil) {  
103.         std::cout << "right_:" << "nil" << std::endl;  
104.     }  
105.     else {  
106.         std::cout << "right_:" << root->right_->value_ << std::endl;  
107.     }  
108.   
109.     std::cout << std::endl;  
110.   
111.   
112.     if (root->left_ != nil)  
113.         PrinTree(root->left_);  
114.     if (root->right_ != nil)  
115.         PrinTree(root->right_);  
116. }  
117.   
118. void RBInsertFixup(std::shared_ptr<node>& root, std::shared_ptr<node> z) {  
119.     while (z->parent_->color_ == red) {   //插入节点Z是红色 若Z父节点也是红色则需要调整  
120.         if (z->parent_ == z->parent_->parent_->left_) {  // 父节点是左子树的情况  
121.             std::shared_ptr<node> y = z->parent_->parent_->right_;  
122.             if (y->color_ == red) {                   //  情况1  
123.                 z->parent_->color_ = black;  
124.                 y->color_ = black;  
125.                 z->parent_->parent_->color_ = red;  
126.                 z = z->parent_->parent_;  
127.             }  
128.             else {  
129.                 if (z == z->parent_->right_) {  
130.                     z = z->parent_;                  //  情况2  
131.                     LeftRotate(root, z);  
132.                 }  
133.                 z->parent_->color_ = black;           //  情况3  
134.                 z->parent_->parent_->color_ = red;  
135.                 RightRotate(root, z->parent_->parent_);  
136.             }  
137.         }  
138.         else {// 父节点是右子树的情况 与上面判断处理均是镜像对称  
139.             std::shared_ptr<node> y = z->parent_->parent_->left_;  
140.             if (y->color_ == red) {  
141.                 z->parent_->color_ = black;  
142.                 y->color_ = black;  
143.                 z->parent_->parent_->color_ = red;  
144.                 z = z->parent_->parent_;  
145.             }  
146.             else {  
147.                 if (z == z->parent_->left_) {  
148.                     z = z->parent_;  
149.                     RightRotate(root, z);  
150.                 }  
151.                 z->parent_->color_ = black;  
152.                 z->parent_->parent_->color_ = red;  
153.                 LeftRotate(root, z->parent_->parent_);  
154.             }  
155.         }  
156.     }//while (z->parent_->color_ == red)  
157.     root->color_ = black;  
158. }//function end  
159.   
160. void RBInsert(std::shared_ptr<node>& root, std::shared_ptr<node> ins) {  
161.     std::shared_ptr<node> y = nil;  
162.     std::shared_ptr<node> x = root;  
163.   
164.     while (x != nil) {  
165.         y = x;  
166.         if (ins->value_ < x->value_) {  
167.             x = x->left_;  
168.         }  
169.         else {  
170.             x = x->right_;  
171.         }  
172.     }  
173.     ins->parent_ = y;  
174.     if (y == nil) {  
175.         root = ins;  
176.     }  
177.     else if (ins->value_ < y->value_) {  
178.         y->left_ = ins;  
179.     }  
180.     else {  
181.         y->right_ = ins;  
182.     }  
183.     ins->left_ = ins->right_ = nil;  
184.     ins->color_ = red;  
185.     // todo  fixup  
186.     RBInsertFixup(root, ins);  
187. }  
188.   
189. std::shared_ptr<node> CreateRB() {  
190.       
191.     std::shared_ptr<node> root = nil;  
192.     std::shared_ptr<node> x = CreateNode(red, 15);  
193.     RBInsert(root, x);  
194.   
195.   
196.     x = CreateNode(red, 10);  
197.     RBInsert(root, x);  
198.   
199.     x = CreateNode(red, 20);  
200.     RBInsert(root, x);  
201.   
202.     x = CreateNode(red, 5);  
203.     RBInsert(root, x);  
204.   
205.     x = CreateNode(red, 13);  
206.     RBInsert(root, x);  
207.   
208.     x = CreateNode(red, 17);  
209.     RBInsert(root, x);  
210.   
211.     x = CreateNode(red, 25);  
212.     RBInsert(root, x);  
213.       
214.   
215.     return root;  
216. }  
217.   
218. //=============================================  
219. // delete test  
220. std::shared_ptr<node> RBMinimum(std::shared_ptr<node> n) {  
221.     while (n->left_ != nil) {  
222.         n = n->left_;  
223.     }  
224.     return n;  
225. }  
226.   
227. std::shared_ptr<node> RBMaximum(std::shared_ptr<node> n) {  
228.     while (n->right_ != nil) {  
229.         n = n->right_;  
230.     }  
231.     return n;  
232. }  
233.   
234. std::shared_ptr<node> RBSuccessor(std::shared_ptr<node> n) {  
235.     if (n->right_ != nil)  
236.         return RBMinimum(n->right_);  
237.     std::shared_ptr<node> y = n->parent_;  
238.     while (y != nil && n == y->right_) {  
239.         n = y;  
240.         y = y->parent_;  
241.     }  
242.     return y;  
243. }  
244.   
245. void RBTransplant(std::shared_ptr<node>& root,  
246.     std::shared_ptr<node> u, std::shared_ptr<node> v) {  
247.     if (u->parent_ == nil)  
248.         root = v;  
249.     else if (u == u->parent_->left_)  
250.         u->parent_->left_ = v;  
251.     else  
252.         u->parent_->right_ = v;  
253.     v->parent_ = u->parent_;  
254. }  
255.   
256. void RBDeleteFixup(std::shared_ptr<node>& root, std::shared_ptr<node> x) {  
257.     while (x != root && x->color_ == black) {  
258.         if (x == x->parent_->left_) {  
259.             std::shared_ptr<node> w = x->parent_->right_;  
260.             if (w->color_ == red) {  
261.                 w->color_ = black;  
262.                 x->parent_->color_ = red;  
263.                 LeftRotate(root, x->parent_);  
264.                 w = x->parent_->right_;  
265.             }  
266.   
267.             if (w->left_->color_ == black && w->right_->color_ == black) {  
268.                 w->color_ = red;  
269.                 x = x->parent_;  
270.             }  
271.             else {  
272.                 if (w->right_->color_ == black) {  
273.                     w->left_->color_ = black;  
274.                     w->color_ = red;  
275.                     RightRotate(root,w);  
276.                     w = x->parent_->right_;  
277.                 }  
278.                 w->color_ = x->parent_->color_;  
279.                 x->parent_->color_ = black;  
280.                 w->right_->color_ = black;  
281.                 LeftRotate(root,x->parent_);  
282.                 x = root;  
283.             }  
284.         }else {  
285.             std::shared_ptr<node> w = x->parent_->left_;  
286.             if (w->color_ == red) {  
287.                 w->color_ = black;  
288.                 x->parent_->color_ = red;  
289.                 RightRotate(root, x->parent_);  
290.                 w = x->parent_->left_;  
291.             }  
292.   
293.             if (w->right_->color_ == black && w->left_->color_ == black) {  
294.                 w->color_ = red;  
295.                 x = x->parent_;  
296.             }  
297.             else {  
298.                 if (w->left_->color_ == black) {  
299.                     w->right_->color_ = black;  
300.                     w->color_ = red;  
301.                     LeftRotate(root, w);  
302.                     w = x->parent_->left_;  
303.                 }  
304.                 w->color_ = x->parent_->color_;  
305.                 x->parent_->color_ = black;  
306.                 w->left_->color_ = black;  
307.                 RightRotate(root, x->parent_);  
308.                 x = root;  
309.             }  
310.         }  
311.     }//while (x != root && x->color_ == black)   
312.   
313.     x->color_ = black;  
314. }  
315.   
316.   
317.   
318.   
319.   
320.   
321. void RBDelete(std::shared_ptr<node>& root,std::shared_ptr<node> z) {  
322.     if (root == nil || z == nil)  
323.         return;  
324.     std::shared_ptr<node> y;  
325.     std::shared_ptr<node> x;  
326.     if (z->left_ == nil || z->right_ == nil) {  
327.         y = z;  
328.     }  
329.     else {  
330.         y = RBSuccessor(z);  
331.     }  
332.   
333.     if (y->left_ != nil) {  
334.         x = y->left_;  
335.     }  
336.     else {  
337.         x = y->right_;  
338.     }  
339.     x->parent_ = y->parent_;  
340.     if (y->parent_ == nil) {  
341.         root = x;  
342.     }  
343.     else {  
344.         if (y == y->parent_->left_) {  
345.             y->parent_->left_ = x;  
346.         }  
347.         else {  
348.             y->parent_->right_ = x;  
349.         }  
350.     }  
351.   
352.     if (y != z) {  
353.         z->value_ = y->value_;  
354.     }  
355.   
356.     if (y->color_ == black) {  
357.         //todo  
358.         RBDeleteFixup(root,x);  
359.     }  
360. }  
361.   
362.   
363.   
364. //=============================================  
365.   
366. int main()  
367. {  
368.     std::shared_ptr<node> root = CreateRB();  
369.     PrinTree(root);  
370.     std::cout << "===========================" << std::endl;  
371.   
372.   
373.     RBDelete(root,root);  
374.     PrinTree(root);  
375.     std::cout << "===========================" << std::endl;  
376.   
377.     RBDelete(root, root);  
378.     PrinTree(root);  
379.     std::cout << "===========================" << std::endl;  
380.   
381.     RBDelete(root, root);  
382.     PrinTree(root);  
383.     std::cout << "===========================" << std::endl;  
384.   
385.     RBDelete(root, root);  
386.     PrinTree(root);  
387.     std::cout << "===========================" << std::endl;  
388.   
389.     RBDelete(root, root);  
390.     PrinTree(root);  
391.     std::cout << "===========================" << std::endl;  
392.   
393.     RBDelete(root, root);  
394.     PrinTree(root);  
395.     std::cout << "===========================" << std::endl;  
396.   
397.     RBDelete(root, root);  
398.     PrinTree(root);  
399.     std::cout << "===========================" << std::endl;  
400.   
401.     return 0;  
402. }