二叉平衡树AVL的插入和删除的C实现源码

ypxing

复习数据结构,顺便用C实现了一下二叉平衡树AVL的插入和删除算法
共享一下,呵呵

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. #include <stdlib.h>
   
5. #include <errno.h>
   
6. #include <assert.h>
   
7. 
   
8. typedef struct node node;
   
9. 
   
10. struct node
    
11. {
    
12.   node* parent;
    
13.   node* left;
    
14.   node* right;
    
15.   int   balance;  //左右子树高度之差
    
16.   int   key;
    
17. };
    
18. 
    
19. extern void traverseAVL1(node* root); //中序遍历, 下面定义
    
20. 
    
21. extern void traverseAVL2(node* root); //前序遍历, 下面定义
    
22. 
    
23. int searchNode(int key, node* root, node** parent) //按key查找结点
    
24. {
    
25.   node* temp;
    
26.   assert(root != NULL);
    
27.   temp = root;
    
28.   *parent = root->parent;
    
29.   while (temp !=NULL)
    
30.   {
    
31.     if (temp->key == key)
    
32.       return 1;
    
33.     else
    
34.     {
    
35.        *parent = temp;
    
36.       if (temp->key > key)
    
37.         temp = temp->left;
    
38.       else
    
39.         temp = temp->right;
    
40.     }
    
41.   }
    
42.   return 0;
    
43. 
    
44. }
    
45. 
    
46. node* minNode(node* root) //树root的最小结点
    
47. {
    
48.   if (root == NULL)
    
49.     return NULL;
    
50.   while (root->left != NULL)
    
51.     root = root->left;
    
52.   return root;
    
53. }
    
54. 
    
55. node* maxNode(node* root) //树root的最大结点
    
56. {
    
57.   if (root == NULL)
    
58.     return NULL;
    
59.   while (root->right != NULL)
    
60.     root = root->right;
    
61.   return root;
    
62. }
    
63. 
    
64. node* preNode(node* target) //求前驱结点
    
65. {
    
66.   if (target == NULL)
    
67.     return NULL;
    
68.   if (target->left != NULL)
    
69.     return maxNode(target->left);
    
70.   else
    
71.     while ((target->parent!=NULL) && (target!=target->parent->right))
    
72.       target = target->parent;
    
73.   return target->parent;
    
74. }
    
75. 
    
76. node* nextNode(node* target) //求后继结点
    
77. {
    
78.   if (target == NULL)
    
79.     return NULL;
    
80.   if (target->right != NULL)
    
81.     return minNode(target->right);
    
82.   else
    
83.     while ((target->parent!=NULL) && (target!=target->parent->left))
    
84.       target = target->parent;
    
85.   return target->parent;
    
86. }
    
87. 
    
88. node* adjustAVL(node* root, node* parent, node* child)
    
89. {
    
90.   node *cur;
    
91.   assert((parent != NULL)&&(child != NULL));
    
92.   switch (parent->balance)
    
93.   {
    
94.   case 2:
    
95.     if (child->balance == -1)//LR型
    
96.     {
    
97.       cur = child->right;
    
98.       cur->parent = parent->parent;
    
99.       child->right = cur->left;
    
100.       if (cur->left != NULL)
     
101.         cur->left->parent = child;
     
102.       parent->left = cur->right;
     
103.       if (cur->right != NULL)
     
104.         cur->right->parent = parent;
     
105.       cur->left = child;
     
106.       child->parent = cur;
     
107.       cur->right = parent;
     
108.       if (parent->parent != NULL)
     
109.         if (parent->parent->left == parent)
     
110.           parent->parent->left = cur;
     
111.         else parent->parent->right = cur;
     
112.       else
     
113.         root = cur;
     
114.       parent->parent = cur;
     
115.       if (cur->balance == 0)
     
116.       {
     
117.         parent->balance = 0;
     
118.         child->balance = 0;
     
119.       }
     
120.       else if (cur->balance == -1)
     
121.       {
     
122.         parent->balance = 0;
     
123.         child->balance = 1;
     
124.       }
     
125.       else
     
126.       {
     
127.         parent->balance = -1;
     
128.         child->balance = 0;
     
129.       }
     
130.       cur->balance = 0;
     
131.     }
     
132.     else //LL型
     
133.     {
     
134.       child->parent = parent->parent;
     
135.       parent->left = child->right;
     
136.       if (child->right != NULL)
     
137.         child->right->parent = parent;
     
138.       child->right = parent;
     
139.       if (parent->parent != NULL)
     
140.         if (parent->parent->left == parent)
     
141.           parent->parent->left = child;
     
142.         else parent->parent->right = child;
     
143.       else
     
144.         root = child;
     
145.       parent->parent = child;
     
146.       if (child->balance == 1) //插入时
     
147.       {
     
148.         child->balance = 0;
     
149.         parent->balance = 0;
     
150.       }
     
151.       else //删除时
     
152.       {
     
153.         child->balance = -1;
     
154.         parent->balance = 1;
     
155.       }
     
156.     }
     
157.    break;
     
158.    
     
159.   case -2:
     
160.     if (child->balance == 1) //RL型
     
161.     {
     
162.       cur = child->left;
     
163.       cur->parent = parent->parent;
     
164.       child->left = cur->right;
     
165.       if (cur->right != NULL)
     
166.         cur->right->parent = child;
     
167.       parent->right = cur->left;
     
168.       if (cur->left != NULL)
     
169.         cur->left->parent = parent;
     
170.       cur->left = parent;
     
171.       cur->right = child;
     
172.       child->parent = cur;
     
173.       if (parent->parent != NULL)
     
174.         if (parent->parent->left == parent)
     
175.           parent->parent->left = cur;
     
176.         else parent->parent->right = cur;
     
177.       else
     
178.         root = cur;
     
179.       parent->parent = cur;
     
180.       if (cur->balance == 0)
     
181.       {
     
182.         parent->balance = 0;
     
183.         child->balance = 0;
     
184.       }
     
185.       else if (cur->balance == 1)
     
186.       {
     
187.         parent->balance = 0;
     
188.         child->balance = -1;
     
189.       }
     
190.       else
     
191.       {
     
192.         parent->balance = 1;
     
193.         child->balance = 0;
     
194.       }
     
195.       cur->balance = 0;
     
196.     }
     
197.     else  //RR型
     
198.     {
     
199.       child->parent = parent->parent;
     
200.       parent->right = child->left;
     
201.       if (child->left != NULL)
     
202.         child->left->parent = parent;
     
203.       child->left = parent;
     
204.       if (parent->parent != NULL)
     
205.         if (parent->parent->left == parent)
     
206.           parent->parent->left = child;
     
207.         else parent->parent->right = child;
     
208.       else
     
209.         root = child;
     
210.       parent->parent = child;
     
211.       if (child->balance == -1) //插入时
     
212.       {
     
213.         child->balance = 0;
     
214.         parent->balance = 0;
     
215.       }
     
216.       else //删除时
     
217.       {
     
218.         child->balance = 1;
     
219.         parent->balance = -1;
     
220.       }
     
221.     }
     
222.     break;
     
223.   }
     
224.   return root;
     
225. }
     
226. 
     
227. 
     
228. node* insertNode(int key, node* root)
     
229. {
     
230.   node *parent, *cur, *child;
     
231.   assert (root != NULL);
     
232.   if (searchNode(key, root, &parent)) //结点已存在
     
233.     return root;
     
234.   else
     
235.   {
     
236.     cur = (node*)malloc(sizeof(node));
     
237.     cur->parent = parent;
     
238.     cur->key = key;
     
239.     cur->left = NULL;
     
240.     cur->right = NULL;
     
241.     cur->balance = 0;
     
242.     if (key<parent->key)
     
243.     {
     
244.       parent->left = cur;
     
245.       child = parent->left;
     
246.     }
     
247.     else
     
248.     {
     
249.       parent->right = cur;
     
250.       child = parent->right;
     
251.     }
     
252.    
     
253.     while ((parent != NULL)) //查找需要调整的最小子树
     
254.     {
     
255.       if (child == parent->left)
     
256.         if (parent->balance == -1)
     
257.         {
     
258.           parent->balance = 0;
     
259.           return root;
     
260.         }
     
261.         else if (parent->balance == 1)
     
262.         {
     
263.           parent->balance = 2;
     
264.           break;
     
265.         }
     
266.         else
     
267.         {
     
268.           parent->balance = 1;
     
269.           child = parent;
     
270.           parent = parent->parent;
     
271.         }
     
272.       else if (parent->balance == 1)
     
273.       {
     
274.         parent->balance = 0;
     
275.         return root;
     
276.       }
     
277.       else if (parent->balance == -1)
     
278.       {
     
279.         parent->balance = -2;
     
280.         break;
     
281.       }
     
282.       else
     
283.       {
     
284.         parent->balance = -1;
     
285.         child = parent;
     
286.         parent = parent->parent;
     
287.       }
     
288.     }
     
289.    
     
290.     if (parent == NULL)
     
291.       return root;
     
292.     return adjustAVL(root, parent, child);
     
293.   }
     
294. }
     
295. 
     
296. node* deleteNode(int key, node* root)
     
297. {
     
298.   node *dNode, *parent, *child, *tp;
     
299.   int temp, tc;
     
300.   assert(root!=NULL);
     
301.   if (!searchNode(key, root, &parent))
     
302.     return root;
     
303.   else
     
304.   {
     
305.     if (parent == NULL)
     
306.       dNode = root;
     
307.     else if ((parent->left!=NULL)&&(parent->left->key==key))
     
308.       dNode = parent->left;
     
309.     else dNode = parent->right;
     
310. 
     
311.     child = dNode;
     
312.     while ((child->left!=NULL)||(child->right!=NULL)) //确定需要删除的结点
     
313.     {
     
314.       if (child->balance == 1)
     
315.         child = preNode(dNode);
     
316.       else child = nextNode(dNode);
     
317.       temp = child->key;
     
318.       child->key = dNode->key;
     
319.       dNode->key = temp;
     
320.       dNode = child;
     
321.     }
     
322.    
     
323.     child = dNode;
     
324.     parent = dNode->parent;
     
325.       
     
326.     while ((parent != NULL)) //查找需要调整的最小子树
     
327.     {
     
328.       if (child == parent->left)
     
329.         if (parent->balance == 1)
     
330.         {
     
331.           parent->balance = 0;
     
332.           child = parent;
     
333.           parent = parent->parent;
     
334.         }
     
335.         else if (parent->balance == -1)
     
336.         {
     
337.           parent->balance = -2;
     
338.           child = parent->right;
     
339.           temp = parent->right->balance;//临时变量保存
     
340.           tp = parent->parent;//临时变量保存
     
341.           if (tp != NULL)
     
342.             if (parent == tp->left)
     
343.               tc = 1;
     
344.             else tc = -1;
     
345.           else tc = 0;
     
346.          
     
347.           root = adjustAVL(root, parent, child);
     
348.          
     
349.           if (temp == 0)
     
350.             break;
     
351.           else
     
352.           {
     
353.             if (tc == 1)
     
354.               child = tp->left;
     
355.             else if (tc == -1)
     
356.               child = tp->right;
     
357.             parent = tp;
     
358.           }
     
359. 
     
360.         }
     
361.         else
     
362.         {
     
363.           parent->balance = -1;
     
364.           break;
     
365.         }
     
366.       else if (parent->balance == -1)
     
367.       {
     
368.         parent->balance = 0;
     
369.         child = parent;
     
370.         parent = parent->parent;
     
371.       }
     
372.       else if (parent->balance == 1)
     
373.       {
     
374.         parent->balance = 2;
     
375.         child = parent->left;
     
376.         temp = parent->left->balance;//临时变量保存
     
377.         tp = parent->parent;//临时变量保存
     
378.         if (tp != NULL)
     
379.           if (parent == tp->left)
     
380.             tc = 1;
     
381.           else tc = -1;
     
382.         else tc = 0;
     
383.         
     
384.         root = adjustAVL(root, parent, child);
     
385.         
     
386.         if (temp == 0)
     
387.           break;
     
388.         else
     
389.         {
     
390.           if (tc == 1)
     
391.             child = tp->left;
     
392.           else if (tc == -1)
     
393.             child = tp->right;
     
394.           parent = tp;
     
395.         }
     
396.       }
     
397.       else
     
398.       {
     
399.         parent->balance = 1;
     
400.         break;
     
401.       }
     
402.     }
     
403.    
     
404.     if (dNode->parent != NULL)
     
405.       if (dNode == dNode->parent->left)
     
406.         dNode->parent->left = NULL;
     
407.       else dNode->parent->right = NULL;
     
408.     free(dNode);
     
409.     if (root == dNode)
     
410.       root = NULL; //root被删除, 避免野指针
     
411.     dNode = NULL;
     
412.    
     
413.     return root;
     
414.   }
     
415. }
     
416. 
     
417. 
     
418. node* createAVL(int *data, int size)
     
419. {
     
420.   int i, j;
     
421.   node *root;
     
422.   if (size<1)
     
423.     return NULL;
     
424.   root = (node*)malloc(sizeof(node));
     
425.   root->parent = NULL;
     
426.   root->left = NULL;
     
427.   root->right = NULL;
     
428.   root->key = data[0];
     
429.   root->balance = 0;
     
430.   
     
431.   for(i=1;i<size;i++)
     
432.     root = insertNode(data[i], root);
     
433.   return root;
     
434. }
     
435. 
     
436. void destroyAVL(node* root)
     
437. {
     
438.   if (root != NULL)
     
439.   {
     
440.     destroyAVL(root->left);
     
441.     destroyAVL(root->right);
     
442.     free(root);
     
443.     root=NULL;
     
444.   }
     
445.   
     
446. }
     
447. 
     
448. void traverseAVL1(node* root) //中序遍历
     
449. {
     
450.   if (root != NULL)
     
451.   {
     
452.     traverseAVL1(root->left);
     
453.     printf("%d, %d\n", root->key, root->balance);
     
454.     traverseAVL1(root->right);
     
455.   }
     
456. }
     
457. 
     
458. void traverseAVL2(node* root) //先序遍历
     
459. {
     
460.   if (root != NULL)
     
461.   {
     
462.     printf("%d, %d\n", root->key, root->balance);
     
463.     traverseAVL2(root->left);
     
464.     traverseAVL2(root->right);
     
465.   }
     
466. }
     
467. 
     
468. int main(int argc, char *argv[])
     
469. {
     
470.   int data[] = {1, 5, 7, 4, 3, 2, 11, 9, 10};
     
471.   node* root;
     
472.   root = createAVL(data, sizeof(data)/sizeof(data[0]));
     
473. 
     
474.   printf("++++++++++++++++++++++++++++\n");
     
475.   traverseAVL1(root);
     
476.   printf("\n");
     
477.   traverseAVL2(root);
     
478.   
     
479.   root = deleteNode(5, root);
     
480.   printf("++++++++++++++++++++++++++++\n");
     
481.   traverseAVL1(root);
     
482.   printf("\n");
     
483.   traverseAVL2(root);
     
484. 
     
485.   root = deleteNode(3, root);
     
486.   printf("++++++++++++++++++++++++++++\n");
     
487.   traverseAVL1(root);
     
488.   printf("\n");
     
489.   traverseAVL2(root);
     
490. 
     
491.   root = deleteNode(1, root);
     
492.   printf("++++++++++++++++++++++++++++\n");
     
493.   traverseAVL1(root);
     
494.   printf("\n");
     
495.   traverseAVL2(root);
     
496. 
     
497.   root = deleteNode(7, root);
     
498.   printf("++++++++++++++++++++++++++++\n");
     
499.   traverseAVL1(root);
     
500.   printf("\n");
     
501.   traverseAVL2(root);
     
502. 
     
503.   root = deleteNode(4, root);
     
504.   printf("++++++++++++++++++++++++++++\n");
     
505.   traverseAVL1(root);
     
506.   printf("\n");
     
507.   traverseAVL2(root);
     
508. 
     
509.   root = deleteNode(2, root);
     
510.   printf("++++++++++++++++++++++++++++\n");
     
511.   traverseAVL1(root);
     
512.   printf("\n");
     
513.   traverseAVL2(root);
     
514. 
     
515.   destroyAVL(root);
     
516. }
     
517. 
     

复制代码

[ 本帖最后由 ypxing 于 2007-12-8 12:06 编辑 ]

cugb_cat

顶～～～

converse

我也写过一个:
http://www.cppblog.com/converse/archive/2007/08/29/31179.html

细细想来,基本的数据结构除了图没有碰过以外其他都自己动手实践过了

ypxing

看过你写的红黑树
准备自己也实现一下

原帖由 converse 于 2007-11-3 21:42 发表
我也写过一个:
http://www.cppblog.com/converse/archive/2007/08/29/31179.html

细细想来,基本的数据结构除了图没有碰过以外其他都自己动手实践过了

converse

原帖由 ypxing 于 2007-11-3 21:47 发表
看过你写的红黑树
准备自己也实现一下

最近一直在想AVL树和红黑树效率上到底有什么区别?分别有哪些适用场合...

更让我吐血的是,发明红黑树的哥们是怎么想到这么个鬼东西的

ypxing

印象里红黑树的应用似乎更广些

原帖由 converse 于 2007-11-3 21:52 发表


最近一直在想AVL树和红黑树效率上到底有什么区别?分别有哪些适用场合...

更让我吐血的是,发明红黑树的哥们是怎么想到这么个鬼东西的

converse

我总觉得红黑树是AVL的特例

win_hate

红黑树不是 AVL 的特例

AVL 的左子树和右子树高度最多相差 1， 而红黑的最长路径可以是最短路径的两倍， AVL 比红黑树要平衡。

AVL 的删除最多需要 O(lg n) 次旋转，而红黑树的删除需要不多于 3 次旋转，但更改颜色次数以 log n 为界。

红黑树的黑点是骨架，限制了整棵树的高度；而红点是肉，可以通过插入红点来把树撑高，但由于两个黑点之间最多有一个红点，所以高度仍受黑点限制。最短的路径上可以全是黑点，而最长的路径上，红点至多能达到黑点数减 1，或者说路径长度是 black height 的两倍。

红黑树其实与 2－3－4 树（一种 B 树）对应，若把黑点的红儿子提上来，并与黑点一起，作为一个大点，就得到了一棵 2-3-4 树，树高就是 black height. 而红黑树的插入、删除与相应的 2－3－4 树的插入删除是可以相互印证的。

[ 本帖最后由 win_hate 于 2007-11-4 17:36 编辑 ]

baohuaihuai

原帖由 win_hate 于 2007-11-4 17:32 发表
红黑树不是 AVL 的特例

AVL 的左子树和右子树高度最多相差 1， 而红黑的最长路径可以是最短路径的两倍， AVL 比红黑树要平衡。

AVL 的删除最多需要 O(lg n) 次旋转，而红黑树的删除需要不多于 3 次旋转， ...

版主给讲讲红黑树吧,之前看过你的AVL讲解.
我也比较不懂发明红黑树的人是怎么想到的.

win_hate

红黑树刚出来的时候不叫红黑树，叫对称二元 B 树， 发明者是 Bayer， 后来 Sedgewick  和另一个不记得是谁把颜色加进去，演化成现在的红黑树。

看他们的文章就可以知道红黑树是怎么演变过来的了。一些算法书的参考文献列出了相关文献。