<<算法导论>>一起学之二:红黑树的实现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 编辑 ]

yjm0573

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条你没有实现

yjm0573

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.

iceviewer

  哈哈，跟你一起看，不懂就骚扰你

anthony1983

好像所有的平衡二叉树的删除操作都很麻烦~~~~~

anthony1983

看到红黑树就头大~~~~

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

复制代码

flw2

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

liuweni

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

雨丝风片

原帖由 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.

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