Chinaunix

标题: <<算法导论>>一起学之二:红黑树的实现C源码 [打印本页]

---

作者: converse    时间: 2006-03-04 22:42
标题: <<算法导论>>一起学之二:红黑树的实现C源码
第二章中给出的Merge算法,本质是初始化两个数组分别保存前后两个已经排序好了的数组,然后逐个扫描比较两个数组中的元素把元素放在原来数组的合适的位置上.
     不知道之前有没有人做过这个算法,比起书上的那个并不见得高明,在最坏的情况下要交换元素(N/2)*(N/2)也就是N的平方数量级(这里N是数组的大小),这个最坏的情况就是前面的数组中的元素都比后面数组的元素大.
       虽然不见得是最好的,不过至少是自己思考的结果,放上来也许对别人有启发.

1. 
   
2. // 如何证明算法的正确性?
   
3. // 我写的merge算法
   
4. void Merge1(int array[], int start, int mid, int end)
   
5. {
   
6.     // 思想:设置两个哨兵,分别指向前后两个数组,
   
7.     // 逐个把前面的数组的元素和后面数组的元素进行比较
   
8.     // 如果前面的元素不比后面的元素大,那么前面数组的哨兵前移一位
   
9.     // 否则,交换两个元素,并且对后面的数组进行扫描,确保新的元素放在合适的位置
   
10.     // 当前面的数组扫描完毕之后循环结束
    
11.     for (int i = start; i < mid + 1; ++i)
    
12.     {
    
13.         if (array[i] > array[mid + 1])
    
14.         {
    
15.             swap(&array[i], &array[mid + 1]);
    
16. 
    
17.             // 把新放入后面数组的元素放到合适的位置去
    
18.             for (int j = mid +1; j + 1 <= end && array[j] > array[j + 1]; ++j)
    
19.             {
    
20.                 swap(&array[j], &array[j + 1]);
    
21.             }
    
22.         }      
    
23.     }
    
24. }
    
25. 
    
26. // 书上的算法实现
    
27. void Merge(int array[], int start, int mid, int end)
    
28. {
    
29.     int temp1[10], temp2[10];
    
30.     int n1, n2;
    
31.     n1 = mid - start + 1;
    
32.     n2 = end - mid;
    
33. 
    
34.     // 拷贝前半部分数组
    
35.     for (int i = 0; i < n1; i++)
    
36.     {
    
37.         temp1[i] = array[start + i];
    
38.     }
    
39.     // 拷贝后半部分数组
    
40.     for (int i = 0; i < n2; i++)
    
41.     {
    
42.         temp2[i] = array[mid + i + 1];
    
43.     }
    
44.     // 把后面的元素设置的很大
    
45.     temp1[n1] = temp2[n2] = 1000;
    
46.     // 逐个扫描两部分数组然后放到相应的位置去
    
47.     for (int k = start, i = 0, j = 0; k <= end; k++)
    
48.     {
    
49.         if (temp1[i] <= temp2[j])
    
50.         {
    
51.             array[k] = temp1[i];
    
52.             i++;
    
53.         }
    
54.         else
    
55.         {
    
56.             array[k] = temp2[j];
    
57.             j++;
    
58.         }
    
59.     }
    
60. }
    
61. 
    
62. void Merge_Sort(int array[], int start, int end)
    
63. {
    
64.     if (start < end)
    
65.     {
    
66.         int i;
    
67.         i = (end + start) / 2;
    
68.         Merge_Sort(array, start, i);
    
69.         Merge_Sort(array, i + 1, end);
    
70. 
    
71.         Merge1(array, start, i, end);
    
72.         //Merge(array, start, i, end);
    
73.     }
    
74. }

复制代码

对外的接口:Merge_Sort(array, start, end);
即:传入一个数组,和起始位置中止位置,比如数组array[10],那么就是Merge_Sort(arrry,0,9)
附带的说明:在Merge中,也就是书中的算法实现部分,初始化的两个temp数组都是10大小的,另外,最后存储完了两部分的数组元素之后放了一个"足够大"的数值1000,相应的都可以改变,这里为求简单方便所以进行了一些限制.

[ 本帖最后由 converse 于 2006-3-21 23:20 编辑 ]

---

作者: ammy    时间: 2006-03-04 22:58
我不懂  也没细看:wink:

但只要扫一眼就可以看出：

你的算法的复杂度：O(n*n)

书上算法的复杂度：O(n)


显然书上的算法好

---

作者: converse    时间: 2006-03-04 23:06

原帖由 ammy 于 2006-3-4 22:58 发表
我不懂  也没细看:wink:

但只要扫一眼就可以看出：

你的算法的复杂度：O(n*n)

书上算法的复杂度：O(n)


显然书上的算法好

我知道我的不好,不过多一个想法记录一下罢了...

---

作者: ammy    时间: 2006-03-04 23:38

原帖由 converse 于 2006-3-4 23:06 发表


我知道我的不好,不过多一个想法记录一下罢了...

呵呵  偶是菜鸟  

今儿个不小心  从清茶灌到这儿来了  打扰:wink:

两周看<<算法导论>>的一章,估计一年下来我可以看完了~~

我估计你看不完了

---

作者: converse    时间: 2006-03-04 23:45

原帖由 ammy 于 2006-3-4 23:38 发表


呵呵  偶是菜鸟  

今儿个不小心  从清茶灌到这儿来了  打扰:wink:



我估计你看不完了

这个是我跟自己在较劲...结果未知...
OK,别在技术帖子里面谈论也技术不太相关的事情了,不然斑竹删了我的帖子了...

---

作者: flw    时间: 2006-03-05 09:52
你首先得介绍一下你的程序的功能啊。
晕死，不然还得去找第二章……

---

作者: converse    时间: 2006-03-21 23:22
标题: 红黑树的代码

1. 
   
2. /*-----------------------------------------------------------
   
3. RB-Tree的插入和删除操作的实现算法
   
4. 参考资料:
   
5. 1) <<Introduction to algorithm>>
   
6. 2) <<STL源码剖析>>
   
7. 3) sgi-stl中stl_tree.h中的实现算法
   
8. 4) http://epaperpress.com/sortsearch/index.html
   
9. 5) http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html
   
10. 
    
11. 作者：李创 (http://www.cppblog.com/converse/)
    
12. 您可以自由的传播，修改这份代码，转载处请注明原作者
    
13. 
    
14. 红黑树的几个性质:
    
15. 1) 每个结点只有红和黑两种颜色
    
16. 2) 根结点是黑色的
    
17. 3) 每个叶子结点(空结点被认为是叶子结点)是黑色的
    
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 z);
    
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.         if (NULL == B)
    
69.                 return;
    
70. 
    
71.         A->right  = B->left;
    
72.         if (NULL != B->left)
    
73.                 B->left->parent = A;
    
74.         B->parent = A->parent;
    
75.         // 这样三个判断连在一起避免了A->parent = NULL的情况
    
76.         if (A == root)
    
77.         {
    
78.                 root = B;
    
79.         }
    
80.         else if (A == A->parent->left)
    
81.         {
    
82.                 A->parent->left = B;
    
83.         }
    
84.         else
    
85.         {
    
86.                 A->parent->right = B;
    
87.         }
    
88.         B->left          = A;
    
89.         A->parent = B;
    
90. }
    
91. 
    
92. /*-----------------------------------------------------------
    
93. |    A              B
    
94. |   / \            / \
    
95. |  B   y   ==>    a   A
    
96. | / \                / \
    
97. |a   b              b   y
    
98. -----------------------------------------------------------*/
    
99. void Right_Rotate(PRBTree A, PRBTree& root)
    
100. {
     
101.         PRBTree B;
     
102.         B = A->left;
     
103. 
     
104.         if (NULL == B)
     
105.                 return;
     
106. 
     
107.         A->left   = B->right;
     
108.         if (NULL != B->right)
     
109.                 B->right->parent = A;
     
110.         B->parent = A->parent;
     
111.         // 这样三个判断连在一起避免了A->parent = NULL的情况
     
112.         if (A == root)
     
113.         {
     
114.                 root = B;
     
115.         }
     
116.         else if (A == A->parent->left)
     
117.         {
     
118.                 A->parent->left = B;
     
119.         }
     
120.         else
     
121.         {
     
122.                 A->parent->right = B;
     
123.         }
     
124.         A->parent = B;
     
125.         B->right  = A;
     
126. }
     
127. 
     
128. /*-----------------------------------------------------------
     
129. |        函数作用:查找key值对应的结点指针
     
130. |        输入参数:根节点root,待查找关键值key
     
131. |        返回参数:如果找到返回结点指针,否则返回NULL
     
132. -------------------------------------------------------------*/
     
133. PRBTree Find_Node(PRBTree root, KEY key)
     
134. {
     
135.         PRBTree x;
     
136. 
     
137.         // 找到key所在的node
     
138.         x = root;
     
139.         do
     
140.         {
     
141.                 if (key == x->key)
     
142.                         break;
     
143.                 if (key < x->key)
     
144.                 {
     
145.                         if (NULL != x->left)
     
146.                                 x = x->left;
     
147.                         else
     
148.                                 break;
     
149.                 }
     
150.                 else
     
151.                 {
     
152.                         if (NULL != x->right)
     
153.                                 x = x->right;
     
154.                         else
     
155.                                 break;
     
156.                 }
     
157.         } while (NULL != x);
     
158. 
     
159.         return x;
     
160. }
     
161. 
     
162. /*-----------------------------------------------------------
     
163. |        函数作用:在树中插入key值
     
164. |        输入参数:根节点root,待插入结点的关键值key
     
165. |        返回参数:根节点root
     
166. -------------------------------------------------------------*/
     
167. PRBTree RB_InsertNode(PRBTree root, KEY key)
     
168. {
     
169.         PRBTree x, y;
     
170. 
     
171.         PRBTree z;
     
172.         if (NULL == (z = (PRBTree)malloc(sizeof(RBTree))))
     
173.         {
     
174.                 printf("Memory alloc error\n");
     
175.                 return NULL;
     
176.         }
     
177.         z->key = key;
     
178. 
     
179.         // 得到z的父节点
     
180.         x = root, y = NULL;
     
181.         while (NULL != x)
     
182.         {
     
183.                 y = x;
     
184.                 if (z->key < x->key)
     
185.                 {
     
186.                         if (NULL != x->left)
     
187.                         {
     
188.                                 x = x->left;
     
189.                         }
     
190.                         else
     
191.                         {
     
192.                                 break;
     
193.                         }
     
194.                 }
     
195.                 else
     
196.                 {
     
197.                         if (NULL != x->right)
     
198.                         {
     
199.                                 x = x->right;
     
200.                         }
     
201.                         else
     
202.                         {
     
203.                                 break;
     
204.                         }
     
205.                 }
     
206.         }
     
207. 
     
208.         // 把z放到合适的位置
     
209.         z->parent = y;
     
210.         if (NULL == y)
     
211.         {
     
212.                 root = z;
     
213.         }
     
214.         else
     
215.         {
     
216.                 if (z->key < y->key)
     
217.                         y->left = z;
     
218.                 else
     
219.                         y->right = z;
     
220.         }
     
221.         // 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red
     
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.         z = Find_Node(root, key);
     
301.         if (NULL == z)
     
302.                 return root;
     
303. 
     
304.         // 当z有一个空子树的时候,y == z
     
305.         // 否则,y是大于z最小的结点
     
306.         if (NULL == z->left || NULL == z->right)
     
307.                 y = z;
     
308.         else
     
309.         {
     
310.                 y = z->right;
     
311.                 while (NULL != y->left)
     
312.                         y = y->left;
     
313.         }
     
314. 
     
315.         // x是y的子树,可能为NULL
     
316.         if (NULL != y->left)
     
317.                 x = y->left;
     
318.         else
     
319.                 x = y->right;
     
320. 
     
321.         // 设定x的位置取代y
     
322.         if (NULL != x)
     
323.                 x->parent = y->parent;
     
324.         if (NULL == y->parent)
     
325.                 root = x;
     
326.         else if (y == y->parent->left)
     
327.                 y->parent->left = x;
     
328.         else
     
329.                 y->parent->right = x;
     
330. 
     
331.         // 把y的key拷贝到z中,这样y就是待删除的结点了
     
332.         if (y != z)
     
333.         {
     
334.                 z->key = y->key;
     
335.         }
     
336. 
     
337.         // 如果y的颜色值是B,那么要对树进行修正
     
338.         if (BLACK == y->color && NULL != x)
     
339.                 RB_DeleteNode_Fixup(root, x);
     
340. 
     
341.         free(y);
     
342. 
     
343.         return root;
     
344. }
     
345. 
     
346. /*-----------------------------------------------------------
     
347. |        函数作用:对删除key值之后的树进行修正
     
348. |        输入参数:根节点root,删除的结点的子结点x
     
349. |        返回参数:根节点root
     
350. -------------------------------------------------------------*/
     
351. PRBTree RB_DeleteNode_Fixup(PRBTree root, PRBTree x)
     
352. {
     
353.         PRBTree w;
     
354. 
     
355.         while (x != root && BLACK == x->color)
     
356.         {
     
357.                 if (x == x->parent->left)                                                                // 如果x是左子树
     
358.                 {
     
359.                         w = x->parent->right;                                                                // w是x的兄弟结点
     
360. 
     
361.                         if (NULL == w)
     
362.                                 continue;
     
363. 
     
364.                         if (RED == w->color)                                                                // 如果w的颜色是红色                                               
     
365.                         {
     
366.                                 w->color = BLACK;
     
367.                                 x->parent->color = RED;
     
368.                                 Left_Rotate(x->parent, root);
     
369.                                 w = x->parent->right;
     
370.                         }
     
371.                         if (NULL != w->left         && BLACK == w->left->color &&
     
372.                                 NULL != w->right && BLACK == w->right->color)
     
373.                         {
     
374.                                 w->color = RED;
     
375.                                 x = x->parent;
     
376.                         }
     
377.                         else
     
378.                         {
     
379.                                 if (NULL != w->right && BLACK == w->right->color)
     
380.                                 {
     
381.                                         w->left->color = BLACK;
     
382.                                         w->color = RED;
     
383.                                         Right_Rotate(w, root);
     
384.                                         w = x->parent->right;
     
385.                                 }
     
386. 
     
387.                                 w->color = x->parent->color;
     
388.                                 x->parent->color = BLACK;
     
389.                                 w->right->color  = BLACK;
     
390.                                 Left_Rotate(x->parent, root);
     
391.                                 x = root;
     
392.                         }
     
393.                 }
     
394.                 else
     
395.                 {
     
396.                         w = x->parent->left;
     
397.                         if (NULL == w)
     
398.                                 continue;
     
399.                         if (RED == w->color)
     
400.                         {
     
401.                                 w->color = BLACK;
     
402.                                 x->parent->color = RED;
     
403.                                 Left_Rotate(x->parent, root);
     
404.                                 w = x->parent->left;
     
405.                         }
     
406.                         if (NULL != w->left         && BLACK == w->left->color &&
     
407.                                 NULL != w->right && BLACK == w->right->color)
     
408.                         {
     
409.                                 w->color = RED;
     
410.                                 x = x->parent;
     
411.                         }
     
412.                         else
     
413.                         {
     
414.                                 if (NULL != w->left && BLACK == w->left->color)
     
415.                                 {
     
416.                                         w->right->color = BLACK;
     
417.                                         w->color = RED;
     
418.                                         Left_Rotate(w, root);
     
419.                                         w = x->parent->left;
     
420.                                 }
     
421. 
     
422.                                 w->color = x->parent->color;
     
423.                                 x->parent->color = BLACK;
     
424.                                 w->left->color  = BLACK;
     
425.                                 Right_Rotate(x->parent, root);
     
426.                                 x = root;
     
427.                         }
     
428.                 }
     
429.         }
     
430. 
     
431.         x->color = BLACK;
     
432. 
     
433.         return root;
     
434. }
     
435. 
     
436. void Print_Node(PRBTree node)
     
437. {
     
438.         char* color[] = {"BLACK", "RED"};
     
439.         printf("Key = %d,\tcolor = %s", node->key, color[node->color]);
     
440.         if (NULL != node->parent)
     
441.                 printf(",\tparent = %d", node->parent->key);
     
442.         if (NULL != node->left)
     
443.                 printf(",\tleft = %d", node->left->key);
     
444.         if (NULL != node->right)
     
445.                 printf(",\tright = %d", node->right->key);
     
446.         printf("\n");
     
447. }
     
448. 
     
449. // 中序遍历树
     
450. void Mid_Visit(PRBTree T)
     
451. {
     
452.         if (NULL != T)
     
453.         {
     
454.                 if (NULL != T->left)
     
455.                         Mid_Visit(T->left);
     
456.                 Print_Node(T);
     
457.                 if (NULL != T->right)
     
458.                         Mid_Visit(T->right);
     
459.         }
     
460. }
     
461. 
     
462. // 中序删除树的各个节点
     
463. void Mid_DeleteTree(PRBTree T)
     
464. {
     
465.         if (NULL != T)
     
466.         {
     
467.                 if (NULL != T->left)
     
468.                         Mid_DeleteTree(T->left);
     
469.                 PRBTree temp = T->right;
     
470.                 free(T);
     
471.                 T = NULL;
     
472.                 if (NULL != temp)
     
473.                         Mid_DeleteTree(temp);
     
474.         }
     
475. }
     
476. 
     
477. void Create_New_Array(int array[], int length)
     
478. {
     
479.         for (int i = 0; i < length; i++)
     
480.         {
     
481.                 array[i] = rand() % 256;
     
482.         }
     
483. }
     
484. 
     
485. int main(int argc, char *argv[])
     
486. {
     
487.         //int array[10] = {80, 116, 81, 205, 82, 68, 151, 20, 109, 100};
     
488.         int array[10];
     
489.         srand(time(NULL));
     
490.         Create_New_Array(array, 10);
     
491.         PRBTree root = NULL;
     
492.         int i;
     
493.         for (i = 0; i < 10; i++)
     
494.         {
     
495.                 root = RB_InsertNode(root, array[i]);
     
496.         }
     
497. 
     
498.         Mid_Visit(root);
     
499. 
     
500.         // 随机删除一个结点
     
501.         int index = rand() % 10;
     
502.         printf("delete node %d\n", array[index]);
     
503.         root = RB_DeleteNode(root, array[index]);
     
504.         Mid_Visit(root);
     
505. 
     
506.         // 删除整颗树
     
507.         Mid_DeleteTree(root);
     
508. 
     
509.         return 0;
     
510. }
     
511. 
     
512. 
     

复制代码

先把代码放上来，基本按照书上的算法写作的，相应的文档整理中，看<<算法导论>>有点头大了，看来两周一篇的任务很是艰难了。

[ 本帖最后由 converse 于 2006-3-21 23:28 编辑 ]

---

作者: lenovo    时间: 2006-03-21 23:25
看的是英文版还是中文版？

---

作者: converse    时间: 2006-03-21 23:28

原帖由 lenovo 于 2006-3-21 23:25 发表
看的是英文版还是中文版？

英文，中文那本是第一版了，英文的是第二版的

---

作者: win_hate    时间: 2006-03-21 23:33
>> 2) 根结点是黑色的

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

书上：

14.1-2

Suppose that the root of a red-black tree is red. If we make it black, does the tree remain a red-black tree?

---

作者: converse    时间: 2006-03-21 23:38

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

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

书上：

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

---

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

---

作者: converse    时间: 2006-03-22 10:19

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

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

---

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

---

作者: 雨丝风片    时间: 2006-03-22 11:13

原帖由 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    时间: 2006-03-22 11:23
标题: 回复 15楼 雨丝风片 的帖子
哈， 好~那我也回去看一下，到时比较下(linux的2.4.9以前用的是AVL树^_^)

---

作者: 雨丝风片    时间: 2006-03-22 11:28

原帖由 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    时间: 2007-07-29 09:56
不知道红黑树到底有什么优势，在算法上插入删除更复杂

---

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

---

作者: converse    时间: 2007-11-28 14:32
这份代码是有问题的，修正的在这里：

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. }
     

复制代码

---

作者: anthony1983    时间: 2007-11-28 21:44
看到红黑树就头大~~~~

---

作者: anthony1983    时间: 2007-11-28 21:47
好像所有的平衡二叉树的删除操作都很麻烦~~~~~

---

作者: iceviewer    时间: 2007-11-29 09:59
  哈哈，跟你一起看，不懂就骚扰你

---

作者: yjm0573    时间: 2008-03-07 11:30

1. 
   
2. /*-----------------------------------------------------------
   
3. |        函数作用:查找key值对应的结点指针
   
4. |        输入参数:根节点root,待查找关键值key
   
5. |        返回参数:如果找到返回结点指针,否则返回NULL
   
6. -------------------------------------------------------------*/
   
7. PRBTree Find_Node(PRBTree root, KEY key)
   
8. {
   
9.         PRBTree x;
   
10. 
    
11.         // 找到key所在的node
    
12.         x = root;
    
13.         do
    
14.         {
    
15.                 if (key == x->key)
    
16.                         break;
    
17.                 if (key < x->key)
    
18.                 {
    
19.                         if (NULL != x->left)
    
20.                                 x = x->left;
    
21.                         else
    
22.                                 break;
    
23.                 }
    
24.                 else
    
25.                 {
    
26.                         if (NULL != x->right)
    
27.                                 x = x->right;
    
28.                         else
    
29.                                 break;
    
30.                 }
    
31.         } while (NULL != x);
    
32. 
    
33.         return x;
    
34. }
    

复制代码

对于这一段：我有点疑问
按你的要求是否应该是这样：

1. 
   
2. /*-----------------------------------------------------------
   
3. |        函数作用:查找key值对应的结点指针
   
4. |        输入参数:根节点root,待查找关键值key
   
5. |        返回参数:如果找到返回结点指针,否则返回NULL
   
6. -------------------------------------------------------------*/
   
7. PRBTree Find_Node(PRBTree root, KEY key)
   
8. {
   
9.         PRBTree x;
   
10. 
    
11.         // 找到key所在的node
    
12.         x = root;
    
13.         do
    
14.         {
    
15.                 if (key == x->key)
    
16.                         break;
    
17.                 if (key < x->key)
    
18.                 {                    
    
19.                        x = x->left;                     
    
20.                 }
    
21.                 else
    
22.                 {
    
23.                        x = x->right;                  
    
24.                 }
    
25.         } while (NULL != x);
    
26. 
    
27.         return x;
    
28. }
    

复制代码

1. 
   
2.     10              
   
3.    / \            
   
4.   5   15  
   
5. / \               
   
6. 3   6   
   

复制代码

假如你要找4，当x指向3的时候，你直接判断其右结点为null, 结果你直接break了，那么这个时候x指向的是3,实际上应该返回的是null.

---

作者: yjm0573    时间: 2008-03-11 11:23

1. 
   
2. 3)空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
   
3. 
   
4.   // 设置z的左右子树为空并且颜色是red，注意新插入的节点颜色都是red
   
5.         z->parent = y;   
   
6.         z->left = z->right = NULL;
   
7.         z->color = RED;
   

复制代码

看了半天,感觉第3条你没有实现

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2