<<算法导论>>一起学之二:红黑树的实现C源码

converse

原帖由 win_hate 于 2006-3-21 23:33 发表
>> 2) 根结点是黑色的

这个观点好象很可疑.......

书上：

第13章才是讲的红黑树的吧？这个第二个是红黑树的性质之一呀，没明白老大的问题是什么

albcamus

根节点的颜色是黑色的， 红色的， 不要求的？  以前我也遇到这个问题， 查了Weiss的书， 黑色； ULK2, 黑色； Algorithms没说。 P.S. Linux内核的virtual memory area， 同一个进程的， 是通过rbtree组织到一起的(2.4.9以后的都是)， 代码实现在mm/mmap.c中。

converse

原帖由 albcamus 于 2006-3-22 10:06 发表
根节点的颜色是黑色的， 红色的， 不要求的？  以前我也遇到这个问题， 查了Weiss的书， 黑色； ULK2, 黑色； Algorithms没说。 P.S. Linux内核的virtual memory area， 同一个进程的， 是通过rbtree组织到一起的 ...

昨晚跟win_hate老大聊了,确定了在算法导论第一版中确实没有要求root是黑色的,里面红黑树的性质只有4个,网上流传很广的算法导论中文版也是第一版的翻译,哪位手头有的可以看看,里面确实是只有4个性质.对此我也很是好奇,但是没有再仔细的看里面的实现了,红黑树是我遇到的最为复杂的一种数据结构了,头大了,不想继续深究下去了

converse

另:很多书包括很多经典的数据结构算法书都没有讲述到红黑树的删除节点操作,比如Weiss的和Algorithms,我现在手头三本书都有,算法导论为主,看到实现的地方不明白的就参考这两本书,可就是这个删除算法,因为没有可以参考的,花费了我一个礼拜的时间去找资料和写算法加调试

雨丝风片

原帖由 albcamus 于 2006-3-22 10:06 发表
P.S. Linux内核的virtual memory area， 同一个进程的， 是通过rbtree组织到一起的(2.4.9以后的都是)， 代码实现在mm/mmap.c中。 ...

Linux中是用vm_area_struct结构体来描述一段连续的内存区域的，FreeBSD中与此对应的结构体是vm_map_entry。两者的共同点是，都同时使用两种数据结构来组织这些结构体，一种是链表，一种是树，只不过FreeBSD是用splay树来组织vm_map_entry结构体的。我前两天做了点FreeBSD的splay树相关代码的分析：

【FreeBSD虚存系统splay树的基本原理】

【FreeBSD虚存系统splay树的代码分析】

等我把这边的代码分析做完了，就和Linux的红黑树比较一下。
另外，NetBSD里面好像使用的也是红黑树。

albcamus

哈， 好~那我也回去看一下，到时比较下(linux的2.4.9以前用的是AVL树^_^)

雨丝风片

原帖由 albcamus 于 2006-3-22 11:23 发表
哈， 好~那我也回去看一下，到时比较下(linux的2.4.9以前用的是AVL树^_^)

嗯，ULK2有云：

Up to Version 2.4.9, the Linux kernel used another type of balanced search tree called AVL tree.

看来各个系统都在来回折腾寻找更好的算法，这样就更有互相比较借鉴的必要了，

liuweni

不知道红黑树到底有什么优势，在算法上插入删除更复杂

flw2

查找很快，虽然平时复杂了点。
就像操作系统的调度，如果有了一个新进程直接插一个链表很简单，但是调度的时候决定谁该运行就费时了。 所有就有多种优先级链表。
就好比平时如果不复习，考试的前几天就得熬夜^^

converse

这份代码是有问题的，修正的在这里：

1. 
   
2. /*-----------------------------------------------------------
   
3.         RB-Tree的插入和删除操作的实现算法
   
4.         参考资料:
   
5.         1) <<Introduction to algorithm>>
   
6.         2) <<STL源码剖析>>
   
7.         3) sgi-stl中stl_tree.h中的实现算法
   
8.         4) [url]http://epaperpress.com/sortsearch/index.html[/url]
   
9.         5) [url]http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html[/url]
   
10. 
    
11.         作者：李创 ([url]http://www.cppblog.com/converse/[/url])
    
12.         您可以自由的传播，修改这份代码，转载处请注明原作者
    
13. 
    
14.         红黑树的几个性质:
    
15.         1) 每个结点只有红和黑两种颜色
    
16.         2) 根结点是黑色的
    
17.         3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
    
18.         4) 如果一个结点是红色的,那么它的左右两个子结点的颜色是黑色的
    
19.         5) 对于每个结点而言,从这个结点到叶子结点的任何路径上的黑色结点
    
20.         的数目相同
    
21. -------------------------------------------------------------*/
    
22. 
    
23. #include <stdio.h>
    
24. #include <stdlib.h>
    
25. #include <time.h>
    
26. 
    
27. typedef int KEY;
    
28. 
    
29. enum NODECOLOR
    
30. {
    
31.         BLACK        = 0,
    
32.         RED          = 1
    
33. };
    
34. 
    
35. typedef struct RBTree
    
36. {
    
37.         struct                RBTree *parent;
    
38.         struct      RBTree *left, *right;
    
39.         KEY                        key;
    
40.         NODECOLOR   color;
    
41. }RBTree, *PRBTree;
    
42. 
    
43. PRBTree RB_InsertNode(PRBTree root, KEY key);
    
44. PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z);
    
45. 
    
46. PRBTree RB_DeleteNode(PRBTree root, KEY key);
    
47. PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x , PRBTree x_parent);
    
48. 
    
49. PRBTree Find_Node(PRBTree root, KEY key);
    
50. void    Left_Rotate(PRBTree A, PRBTree& root);
    
51. void    Right_Rotate(PRBTree A, PRBTree& root);
    
52. void    Mid_Visit(PRBTree T);
    
53. void    Mid_DeleteTree(PRBTree T);
    
54. void    Print_Node(PRBTree node);
    
55. 
    
56. /*-----------------------------------------------------------
    
57. |   A              B
    
58. |  / \    ==>     / \
    
59. | a   B           A  y
    
60. |    / \         / \
    
61. |    b  y        a  b
    
62. -----------------------------------------------------------*/
    
63. void Left_Rotate(PRBTree A, PRBTree& root)
    
64. {      
    
65.         PRBTree B;
    
66.         B = A->right;
    
67. 
    
68.         A->right  = B->left;
    
69.         if (NULL != B->left)
    
70.                 B->left->parent = A;
    
71.         B->parent = A->parent;
    
72. 
    
73.         // 这样三个判断连在一起避免了A->parent = NULL的情况
    
74.         if (A == root)
    
75.         {
    
76.                 root = B;
    
77.         }
    
78.         else if (A == A->parent->left)
    
79.         {
    
80.                 A->parent->left = B;
    
81.         }
    
82.         else
    
83.         {
    
84.                 A->parent->right = B;
    
85.         }
    
86.         B->left          = A;
    
87.         A->parent = B;
    
88. }
    
89. 
    
90. /*-----------------------------------------------------------
    
91. |    A              B
    
92. |   / \            / \
    
93. |  B   y   ==>    a   A
    
94. | / \                / \
    
95. |a   b              b   y
    
96. -----------------------------------------------------------*/
    
97. void Right_Rotate(PRBTree A, PRBTree& root)
    
98. {
    
99.         PRBTree B;
    
100.         B = A->left;
     
101. 
     
102.         A->left   = B->right;
     
103.         if (NULL != B->right)
     
104.                 B->right->parent = A;
     
105. 
     
106.         B->parent = A->parent;
     
107.         // 这样三个判断连在一起避免了A->parent = NULL的情况
     
108.         if (A == root)
     
109.         {
     
110.                 root = B;
     
111.         }
     
112.         else if (A == A->parent->left)
     
113.         {
     
114.                 A->parent->left = B;
     
115.         }
     
116.         else
     
117.         {
     
118.                 A->parent->right = B;
     
119.         }
     
120.         A->parent = B;
     
121.         B->right  = A;
     
122. }
     
123. 
     
124. /*-----------------------------------------------------------
     
125. |        函数作用:查找key值对应的结点指针
     
126. |        输入参数:根节点root,待查找关键值key
     
127. |        返回参数:如果找到返回结点指针,否则返回NULL
     
128. -------------------------------------------------------------*/
     
129. PRBTree Find_Node(PRBTree root, KEY key)
     
130. {
     
131.         PRBTree x;
     
132. 
     
133.         // 找到key所在的node
     
134.         x = root;
     
135.         do
     
136.         {
     
137.                 if (key == x->key)
     
138.                         break;
     
139.                 if (key < x->key)
     
140.                 {
     
141.                         if (NULL != x->left)
     
142.                                 x = x->left;
     
143.                         else
     
144.                                 break;
     
145.                 }
     
146.                 else
     
147.                 {
     
148.                         if (NULL != x->right)
     
149.                                 x = x->right;
     
150.                         else
     
151.                                 break;
     
152.                 }
     
153.         } while (NULL != x);
     
154. 
     
155.         return x;
     
156. }
     
157. 
     
158. /*-----------------------------------------------------------
     
159. |        函数作用:在树中插入key值
     
160. |        输入参数:根节点root,待插入结点的关键值key
     
161. |        返回参数:根节点root
     
162. -------------------------------------------------------------*/
     
163. PRBTree RB_InsertNode(PRBTree root, KEY key)
     
164. {
     
165.         PRBTree x, y;
     
166. 
     
167.         PRBTree z;
     
168.         if (NULL == (z = (PRBTree)malloc(sizeof(RBTree))))
     
169.         {
     
170.                 printf("Memory alloc error\n");
     
171.                 return NULL;
     
172.         }
     
173.         z->key = key;
     
174. 
     
175.         // 得到z的父节点, 如果KEY已经存在就直接返回
     
176.         x = root, y = NULL;
     
177.         while (NULL != x)
     
178.         {
     
179.                 y = x;
     
180.                 if (key < x->key)
     
181.                 {
     
182.                         if (NULL != x->left)
     
183.                         {
     
184.                                 x = x->left;
     
185.                         }
     
186.                         else
     
187.                         {
     
188.                                 break;
     
189.                         }
     
190.                 }
     
191.                 else if (key > x->key)
     
192.                 {
     
193.                         if (NULL != x->right)
     
194.                         {
     
195.                                 x = x->right;
     
196.                         }
     
197.                         else
     
198.                         {
     
199.                                 break;
     
200.                         }
     
201.                 }
     
202.         else
     
203.         {
     
204.             return root;   
     
205.         }
     
206.         }
     
207. 
     
208.     if (NULL == y || y->key > key)
     
209.     {
     
210.         if (NULL == y)
     
211.             root = z;
     
212.         else
     
213.             y->left = z;
     
214.     }
     
215.     else
     
216.     {
     
217.         y->right = z;
     
218.     }
     
219. 
     
220.         // 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red
     
221.     z->parent = y;   
     
222.         z->left = z->right = NULL;
     
223.         z->color = RED;
     
224. 
     
225.         // 对红黑树进行修正
     
226.         return RB_InsertNode_Fixup(root, z);
     
227. }
     
228. 
     
229. /*-----------------------------------------------------------
     
230. |        函数作用:对插入key值之后的树进行修正
     
231. |        输入参数:根节点root,插入的结点z
     
232. |        返回参数:根节点root
     
233. -------------------------------------------------------------*/
     
234. PRBTree RB_InsertNode_Fixup(PRBTree root, PRBTree z)
     
235. {
     
236.         PRBTree y;
     
237.         while (root != z && RED == z->parent->color)        // 当z不是根同时父节点的颜色是red
     
238.         {
     
239.                 if (z->parent == z->parent->parent->left)        // 父节点是祖父节点的左子树
     
240.                 {
     
241.                         y = z->parent->parent->right;                        // y为z的伯父节点
     
242.                         if (NULL != y && RED == y->color)                // 伯父节点存在且颜色是red
     
243.                         {
     
244.                                 z->parent->color = BLACK;                        // 更改z的父节点颜色是B
     
245.                                 y->color = BLACK;                                        // 更改z的伯父节点颜色是B
     
246.                                 z->parent->parent->color = RED;                // 更改z的祖父节点颜色是B
     
247.                                 z = z->parent->parent;                                // 更新z为它的祖父节点
     
248.                         }
     
249.                         else                                                                        // 无伯父节点或者伯父节点颜色是b
     
250.                         {
     
251.                                 if (z == z->parent->right)                        // 如果新节点是父节点的右子树
     
252.                                 {
     
253.                                         z = z->parent;
     
254.                                         Left_Rotate(z, root);
     
255.                                 }
     
256.                                 z->parent->color = BLACK;                        // 改变父节点颜色是B
     
257.                                 z->parent->parent->color = RED;                // 改变祖父节点颜色是R
     
258.                                 Right_Rotate(z->parent->parent, root);
     
259.                         }
     
260.                 }
     
261.                 else                                                                                // 父节点为祖父节点的右子树
     
262.                 {
     
263.                         y = z->parent->parent->left;                        // y为z的伯父节点
     
264.                         if (NULL != y && RED == y->color)                // 如果y的颜色是red
     
265.                         {
     
266.                                 z->parent->color = BLACK;                        // 更改父节点的颜色为B
     
267.                                 y->color = BLACK;                                        // 更改伯父节点的颜色是B
     
268.                                 z->parent->parent->color = RED;                // 更改祖父节点颜色是R
     
269.                                 z = z->parent->parent;                                // 更改z指向祖父节点
     
270.                         }               
     
271.                         else                                                                        // y不存在或者颜色是B
     
272.                         {
     
273.                                 if (z == z->parent->left)                        // 如果是父节点的左子树
     
274.                                 {
     
275.                                         z = z->parent;
     
276.                                         Right_Rotate(z, root);
     
277.                                 }
     
278.                                 z->parent->color = BLACK;                        // 改变父节点的颜色是B
     
279.                                 z->parent->parent->color = RED;                // 改变祖父节点的颜色是RED
     
280.                                 Left_Rotate(z->parent->parent, root);
     
281.                         }
     
282.                 }
     
283.         } // while(RED == z->parent->color)
     
284. 
     
285.         // 根节点的颜色始终都是B
     
286.         root->color = BLACK;
     
287. 
     
288.         return root;
     
289. }
     
290. 
     
291. /*-----------------------------------------------------------
     
292. |        函数作用:在树中删除key值
     
293. |        输入参数:根节点root,待插入结点的关键值key
     
294. |        返回参数:根节点root
     
295. -------------------------------------------------------------*/
     
296. PRBTree RB_DeleteNode(PRBTree root, KEY key)
     
297. {
     
298.         PRBTree x, y, z, x_parent;
     
299. 
     
300.     // 首先查找需要删除的节点
     
301.         z = Find_Node(root, key);
     
302.         if (NULL == z)
     
303.                 return root;
     
304. 
     
305.     y = z, x = NULL, x_parent = NULL;
     
306. 
     
307.         // y是x按照中序遍历树的后继
     
308.     if (NULL == y->left)
     
309.     {
     
310.         x = y->right;
     
311.     }
     
312.     else
     
313.     {
     
314.         if (NULL == y->right)
     
315.         {
     
316.             x = y->left;
     
317.         }
     
318.         else
     
319.         {
     
320.             y = y->right;
     
321.             while (NULL != y->left)
     
322.                 y = y->left;
     
323.             x = y->right;
     
324.         }
     
325.     }
     
326. 
     
327.     if (y != z)
     
328.     {
     
329.         z->left->parent = y;
     
330.         y->left = z->left;
     
331.         if (y != z->right)
     
332.         {
     
333.             x_parent = y->parent;
     
334.             if (NULL != x)
     
335.                 x->parent = y->parent;
     
336.             y->parent->left = x;
     
337.             y->right = z->right;
     
338.             z->right->parent = y;
     
339.         }
     
340.         else
     
341.         {
     
342.             x_parent = y;
     
343.         }
     
344.         if (root == z)
     
345.         {
     
346.             root = y;
     
347.         }
     
348.         else if (z == z->parent->left)
     
349.         {
     
350.             z->parent->left = y;
     
351.         }
     
352.         else
     
353.         {
     
354.             z->parent->right = y;
     
355.         }
     
356.         y->parent = z->parent;
     
357.         NODECOLOR color = y->color;
     
358.         y->color = z->color;
     
359.         z->color = color;
     
360.         y = z;
     
361.     }
     
362.     else
     
363.     {
     
364.         x_parent = y->parent;
     
365.         if (NULL != x)
     
366.             x->parent = y->parent;
     
367.         if (root == z)
     
368.         {
     
369.             root = y;
     
370.         }
     
371.         else if (z == z->parent->left)
     
372.         {
     
373.             z->parent->left = x;
     
374.         }
     
375.         else
     
376.         {
     
377.             z->parent->right = x;
     
378.         }
     
379. 
     
380.     }
     
381. 
     
382.     if (BLACK == y->color)
     
383.     {
     
384.         root = RB_DeleteNode_Fixup(root, x, x_parent);
     
385.     }
     
386.         free(y);
     
387. 
     
388.         return root;
     
389. }
     
390. 
     
391. /*-----------------------------------------------------------
     
392. |        函数作用:对删除key值之后的树进行修正
     
393. |        输入参数:根节点root,删除的结点的子结点x
     
394. |        返回参数:根节点root
     
395. -------------------------------------------------------------*/
     
396. PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x, PRBTree x_parent)
     
397. {
     
398.         PRBTree w;
     
399. 
     
400.         while (x != root && BLACK == x->color)
     
401.         {
     
402.                 if (x == x_parent->left)                                                                // 如果x是左子树
     
403.                 {
     
404.                         w = x_parent->right;                                                                // w是x的兄弟结点
     
405.                         if (RED == w->color)                                                                // 如果w的颜色是红色
     
406.                         {
     
407.                                 w->color = BLACK;
     
408.                                 x_parent->color = RED;
     
409.                                 Left_Rotate(x_parent, root);
     
410.                                 w = x_parent->right;
     
411.                         }
     
412.                         if ((NULL == w->left  || BLACK == w->left->color) &&
     
413.                                 (NULL == w->right || BLACK == w->right->color))
     
414.                         {
     
415.                                 w->color = RED;
     
416.                 x = x_parent;
     
417.                                 x_parent = x_parent->parent;
     
418.                         }
     
419.                         else
     
420.                         {
     
421.                                 if (NULL == w->right || BLACK == w->right->color)
     
422.                                 {
     
423.                     if (NULL != w->left)
     
424.                         w->left->color = BLACK;
     
425. 
     
426.                                         w->color = RED;
     
427.                                         Right_Rotate(w, root);
     
428.                                         w = x_parent->right;
     
429.                                 }
     
430. 
     
431.                                 w->color = x_parent->color;
     
432.                 x_parent->color = BLACK;
     
433.                 if (NULL != w->right)
     
434.                                     w->right->color  = BLACK;
     
435.                                 Left_Rotate(x->parent, root);
     
436.                 break;
     
437.                         }
     
438.                 }
     
439.                 else
     
440.         {
     
441.                         w = x_parent->left;                                                                // w是x的兄弟结点
     
442. 
     
443.                         if (RED == w->color)                                                                // 如果w的颜色是红色                                               
     
444.                         {
     
445.                                 w->color = BLACK;
     
446.                                 x_parent->color = RED;
     
447.                                 Right_Rotate(x_parent, root);
     
448.                                 w = x_parent->left;
     
449.                         }
     
450.                         if ((NULL == w->left  || BLACK == w->left->color) &&
     
451.                                 (NULL == w->right || BLACK == w->right->color))
     
452.                         {
     
453.                                 w->color = RED;
     
454.                 x = x_parent;
     
455.                                 x_parent = x_parent->parent;
     
456.                         }
     
457.                         else
     
458.                         {
     
459.                                 if (NULL == w->left || BLACK == w->left->color)
     
460.                                 {
     
461.                     if (NULL != w->right)
     
462.                         w->right->color = BLACK;
     
463. 
     
464.                                         w->color = RED;
     
465.                                         Left_Rotate(w, root);
     
466.                                         w = x_parent->left;
     
467.                                 }
     
468. 
     
469.                                 w->color = x_parent->color;
     
470.                 x_parent->color = BLACK;
     
471.                 if (NULL != w->left)
     
472.                                     w->left->color  = BLACK;
     
473.                                 Right_Rotate(x->parent, root);
     
474.                 break;
     
475.                         }
     
476.                 }
     
477.         }
     
478. 
     
479.         x->color = BLACK;
     
480. 
     
481.         return root;
     
482. }
     
483. 
     
484. void Print_Node(PRBTree node)
     
485. {
     
486.         char* color[] = {"BLACK", "RED"};
     
487.         printf("Key = %d,\tcolor = %s", node->key, color[node->color]);
     
488.         if (NULL != node->parent)
     
489.                 printf(",\tparent = %d", node->parent->key);
     
490.         if (NULL != node->left)
     
491.                 printf(",\tleft = %d", node->left->key);
     
492.         if (NULL != node->right)
     
493.                 printf(",\tright = %d", node->right->key);
     
494.         printf("\n");
     
495. }
     
496. 
     
497. // 中序遍历树, 加了一个判断, 如果输出的数据不满足序列关系就报错退出
     
498. void Mid_Visit(PRBTree T)
     
499. {
     
500.         if (NULL != T)
     
501.         {
     
502.                 if (NULL != T->left)
     
503.                 {
     
504.                         if (T->left->key > T->key)
     
505.                         {
     
506.                                 printf("wrong!\n");
     
507.                                 exit(-1);
     
508.                         }
     
509.                         Mid_Visit(T->left);
     
510.                 }
     
511.                 Print_Node(T);
     
512.                 if (NULL != T->right)
     
513.                 {
     
514.                         if (T->right->key < T->key)
     
515.                         {
     
516.                                 printf("wrong\n");
     
517.                                 exit(-1);
     
518.                         }
     
519.                         Mid_Visit(T->right);
     
520.                 }
     
521.         }
     
522. }
     
523. 
     
524. // 中序删除树的各个节点
     
525. void Mid_DeleteTree(PRBTree T)
     
526. {
     
527.         if (NULL != T)
     
528.         {
     
529.                 if (NULL != T->left)
     
530.                         Mid_DeleteTree(T->left);
     
531.                 PRBTree temp = T->right;
     
532.                 free(T);
     
533.                 T = NULL;
     
534.                 if (NULL != temp)
     
535.                         Mid_DeleteTree(temp);
     
536.         }
     
537. }
     
538. 
     
539. void Create_New_Array(int array[], int length)
     
540. {
     
541.         for (int i = 0; i < length; i++)
     
542.         {
     
543.                 array[i] = rand() % 256;
     
544.         }
     
545. }
     
546. 
     
547. int main(int argc, char *argv[])
     
548. {
     
549.         srand(time(NULL));
     
550.         PRBTree root = NULL;
     
551.         int i;
     
552.         for (i = 0; i < 100000; i++)
     
553.         {
     
554.                 root = RB_InsertNode(root, rand() % 10000);
     
555.         }
     
556. 
     
557.     Mid_Visit(root);
     
558. 
     
559.         // 删除整颗树
     
560.         Mid_DeleteTree(root);
     
561. 
     
562.         return 0;
     
563. }
     

复制代码