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

converse

第二章中给出的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

我不懂  也没细看:wink:

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

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

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


显然书上的算法好

converse

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

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

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

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


显然书上的算法好

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

ammy

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


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

呵呵  偶是菜鸟  

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

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

我估计你看不完了

converse

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


呵呵  偶是菜鸟  

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



我估计你看不完了

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

flw

你首先得介绍一下你的程序的功能啊。
晕死，不然还得去找第二章……

converse

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

看的是英文版还是中文版？

converse

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

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

win_hate

>> 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?