求AVL平衡树删除操作的过程分析和实例程序

augustusqing

哈哈，多谢“看好”,^_^

原帖由 Sorehead 于 2007-12-7 11:06 发表
由于工作需要，这段时间一直在接触AVL树，不过需求是需要插入，不用删除，所以对删除操作也不是非常熟悉。
不过查过一些删除方面的资料，了解一些，删除其实并不比插入难多少，只要真正理解了插入是怎么一回事 ...

哈哈，确实如你所说，现在发现删除操作与插入操作很比较对称的，
用递规版本实现代码，删除操作的代码与插入代码很相似，就是在平衡处理中要多添加一种情况，因为平衡操作后，仍然可能变短了，需要上一层继续平衡处理

augustusqing

多谢你的分析，我差不多是按你的思路来的，先找到相应节点，如果它本来就是叶子节点，就删除它，不是，就找它的后继节点代替，保证删除的始终是叶子节点，唯一的例外是只有两个节点的时候，一个根节点，一个左儿子节点，这个例外，我的代码中处理了

我是看到下面这篇文章
http://blog.csdn.net/happycock/archive/2003/08/15/20874.aspx
文章前面没怎么看，但最后面说删除操作和插入操作是对称的，给了我很大鼓舞
然后我就画图，把删除操作过程中与插入过程不同的地方分析出来了，确实删除操作其实没有所谓的很“复杂”，没有比插入复杂很“多”，只是多了几种情况，代码中处理后，就可以了，下面是代码了

采用的是C++实现的，因为节点里没有用父指针，那么在旋转操作中，就必须用二级指针，所以就用了C++的引用，又由于没有父指针，中序遍历的前趋和后继操作没有实现，对于这两个操作，我现在只会实现有父指针的，^_^

文件: include/Item.h

1. 
   
2. /*-----------------------------------------------------------
   
3.         Item.h
   
4.         Author: QingXiaoming, 12-06, 2007([url]http://www.cublog.com/augustusqing/[/url]
   
5.        您可以自由拷贝,修改，分发这份代码，但请注明原作者
   
6. -------------------------------------------------------------*/
   
7. 
   
8. #ifndef ITEM_H
   
9. #define ITEM_H
   
10. 
    
11. typedef int Item;
    
12. 
    
13. #endif
    

复制代码

文件：include/AVL_ADT.h

1. 
   
2. /*-----------------------------------------------------------
   
3.         AVL的ADT接口
   
4.         Author: QingXiaoming, 12-06, 2007([url]http://www.cublog.com/augustusqing/[/url]
   
5.        您可以自由拷贝,修改，分发这份代码，但请注明原作者
   
6. -------------------------------------------------------------*/
   
7. #ifndef AVL_ADT_H
   
8. #define AVL_ADT_H
   
9. 
   
10. #include "Item.h"
    
11. 
    
12. typedef struct AVLNode *AVLTree;
    
13. 
    
14. AVLTree initAVL(void);
    
15. int emptyAVL(AVLTree);
    
16. void pretravseAVL(AVLTree);
    
17. void midtravseAVL(AVLTree);
    
18. Item minAVL(AVLTree);
    
19. Item maxAVL(AVLTree);
    
20. AVLTree findAVL(AVLTree, Item);
    
21. Item preAVL(AVLTree, Item);
    
22. Item sucAVL(AVLTree, Item);
    
23. int insertAVL(AVLTree &, Item, int &);
    
24. int deleteAVL(AVLTree &, Item);
    
25. void destroyAVL(AVLTree &);
    
26. 
    
27. #endif
    

复制代码

augustusqing

文件：AVL_ADT.c

1. 
   
2. /*-----------------------------------------------------------
   
3.         AVL的ADT实现
   
4.      Author: QingXiaoming, 12-06, 2007([url]http://www.cublog.com/augustusqing/[/url]
   
5.        您可以自由拷贝,修改，分发这份代码，但请注明原作者
   
6. -------------------------------------------------------------*/
   
7. #include <iostream>
   
8. #include <cstdlib>
   
9. #include "include/AVL_ADT.h"
   
10. 
    
11. #define EH 0
    
12. #define LH 1
    
13. #define RH -1
    
14. #define TRUE 1
    
15. #define FALSE 0
    
16. 
    
17. struct AVLNode {
    
18.        public:
    
19.               AVLNode(Item);
    
20.                Item item;
    
21.                AVLTree lchild;
    
22.                AVLTree rchild;
    
23.                int bh;
    
24.        };
    
25. AVLNode::AVLNode(Item t)
    
26. {
    
27.     item = t;bh = EH;
    
28.     lchild = rchild = NULL;
    
29. }
    
30. 
    
31. static void showAVLTreeNode(AVLTree tree);
    
32. static void Left_Rotate(AVLTree & tree);
    
33. static void Right_Rotate(AVLTree & tree);
    
34. static int Left_Balance(AVLTree & tree);
    
35. static int Right_Balance(AVLTree & tree);
    
36. static int deleteavl(AVLTree & tree, AVLTree link, int & shorter);
    
37. static AVLTree deleteAVLNode(AVLTree & tree, Item item);
    
38. 
    
39. AVLTree initAVL()
    
40. {
    
41.     return NULL;
    
42. }
    
43. 
    
44. int emptyAVL(AVLTree tree)
    
45. {
    
46.     return tree == NULL;
    
47. }
    
48. inline static void showAVLTreeNode(AVLTree tree)
    
49. {
    
50.        Item t;
    
51.        std::cout << "Item: " << tree->item <<  " BH: " <<  tree->bh << " ";
    
52.        if (NULL == tree->lchild && NULL == tree->rchild)
    
53.        {
    
54.            std::cout << std::endl;
    
55.            return;
    
56.        }
    
57.        if (tree->lchild )
    
58.        {
    
59.            t = tree->lchild->item;
    
60.            std::cout <<  " Lchild: " << t << " ";
    
61.        }
    
62.        if (tree->rchild)
    
63.        {
    
64.            t = tree->rchild->item;
    
65.            std::cout <<  " Rchild: " << t << " " << std::endl;
    
66.        }
    
67.        else
    
68.        {
    
69.            std::cout << std::endl;
    
70.        }
    
71. }
    
72. 
    
73. void pretravseAVL(AVLTree tree)
    
74. {
    
75.      if (tree)
    
76.      {
    
77.               showAVLTreeNode(tree);
    
78.               pretravseAVL(tree->lchild);
    
79.               pretravseAVL(tree->rchild);
    
80.      }
    
81. }
    
82. 
    
83. void midtravseAVL(AVLTree tree)
    
84. {
    
85.      if (tree)
    
86.      {
    
87.               midtravseAVL(tree->lchild);
    
88.               showAVLTreeNode(tree);
    
89.               midtravseAVL(tree->rchild);
    
90.      }
    
91. }
    
92. 
    
93. Item minAVL(AVLTree tree)
    
94. {
    
95.      if (tree)
    
96.      {
    
97.               while (tree->lchild)
    
98.               {
    
99.                     tree = tree->lchild;
    
100.               }
     
101.               return tree->item;
     
102.      }
     
103.      else  return -1;
     
104. }
     
105. 
     
106. Item maxAVL(AVLTree tree)
     
107. {
     
108.      if (tree)
     
109.      {
     
110.               while (tree->rchild)
     
111.               {
     
112.                     tree = tree->rchild;
     
113.               }
     
114.               return tree->item;
     
115.      }
     
116.      else  return -1;
     
117. }
     
118. 
     
119. AVLTree findAVL(AVLTree tree, Item item)
     
120. {
     
121.     while (NULL != tree && item != tree->item)
     
122.     {
     
123.           tree = (item < tree->item) ? tree->lchild : tree->rchild;
     
124.     }
     
125.     return tree;
     
126. }
     
127. 
     
128. int insertAVL(AVLTree & tree, Item item, int &taller)
     
129. {
     
130.     int tall;
     
131.     taller = FALSE;//also should give the default value
     
132.     if (!tree)
     
133.     {
     
134.         tree = new AVLNode(item);
     
135.         taller = TRUE;
     
136.         return 1;
     
137.     }
     
138.     if (item == tree->item)
     
139.     {
     
140.              taller = FALSE; return 0;
     
141.     }
     
142.     else if (item < tree->item)
     
143.     {
     
144.         if (!insertAVL(tree->lchild, item, tall)) return 0;
     
145.         if (tall)
     
146.         {
     
147.             switch (tree->bh)
     
148.             {
     
149.                   case EH:
     
150.                        taller = TRUE;  tree->bh = LH;      break;
     
151.                   case RH:
     
152.                        taller = FALSE; tree->bh = EH;      break;
     
153.                   case LH:
     
154.                        taller = FALSE; Left_Balance(tree); break;
     
155.             }
     
156.         }
     
157.     }
     
158.     else
     
159.     {
     
160.         if (!insertAVL(tree->rchild, item, tall)) return 0;
     
161.         if (tall)
     
162.         {
     
163.               switch (tree->bh)
     
164.             {
     
165.                   case EH:
     
166.                        taller = TRUE;  tree->bh = RH;       break;
     
167.                   case LH:
     
168.                        taller = FALSE; tree->bh = EH;       break;
     
169.                   case RH:
     
170.                        taller = FALSE; Right_Balance(tree); break;
     
171.             }     
     
172.         }
     
173.     }
     
174.     return 1;
     
175. }
     
176. static void Left_Rotate(AVLTree & tree)
     
177. {
     
178.        assert(NULL != tree->rchild);//assert to assure the valid
     
179.        AVLTree rc = tree->rchild;
     
180.        tree->rchild = rc->lchild;
     
181.        rc->lchild = tree;
     
182.        tree = rc;
     
183. }
     
184. 
     
185. static void Right_Rotate(AVLTree & tree)
     
186. {
     
187.        assert(NULL != tree->lchild);//assert to assure the valid
     
188.        AVLTree lc = tree->lchild;
     
189.        tree->lchild = lc->rchild;
     
190.        lc->rchild = tree;
     
191.        tree = lc;
     
192. }
     
193. 
     
194. static int Left_Balance(AVLTree & tree)
     
195. {
     
196.     int shorter;//this just for delete action, to tell the delete action whether this balance action shotter
     
197.     assert(NULL != tree && NULL != tree->lchild);//assert to assure the valid
     
198.     AVLTree lc = tree->lchild, rd;
     
199.     switch (lc->bh)
     
200.     {
     
201.           case LH:
     
202.                lc->bh = EH; tree->bh = EH;
     
203.                Right_Rotate(tree);
     
204.                shorter = 1;
     
205.                break;
     
206.           case RH:
     
207.                rd = lc->rchild;
     
208.                switch (rd->bh)
     
209.                {
     
210.                      case EH:
     
211.                           tree->bh = EH; lc->bh = EH;
     
212.                           break;
     
213.                      case LH:
     
214.                           tree->bh = RH; lc->bh = EH;
     
215.                           break;
     
216.                      case RH:
     
217.                           tree->bh = EH; lc->bh = LH;
     
218.                           break;      
     
219.                }
     
220.                rd->bh = EH;
     
221.                Left_Rotate(tree->lchild);
     
222.                Right_Rotate(tree);
     
223.                shorter = 1;
     
224.                break;
     
225.           /*
     
226.           when insert , this case will not be ture, it just for delete action
     
227.           */
     
228.           case EH:
     
229.                lc->bh = RH; tree->bh = LH;
     
230.                Right_Rotate(tree);
     
231.                shorter = 0;
     
232.                break;
     
233.     }
     
234.     return shorter;
     
235. }
     
236. static int Right_Balance(AVLTree & tree)
     
237. {
     
238.     int shorter;//this just for delete action, to tell the delete action whether this balance action shotter
     
239.     assert(NULL != tree && NULL != tree->rchild);//assert to assure the valid
     
240.     AVLTree rc = tree->rchild, ld;
     
241.     switch (rc->bh)
     
242.     {
     
243.           case RH:
     
244.                rc->bh = EH; tree->bh = EH; shorter = 1;
     
245.                Left_Rotate(tree);
     
246.                break;
     
247.           case LH:
     
248.                ld = rc->lchild;
     
249.                switch (ld->bh)
     
250.                {
     
251.                      case EH:
     
252.                           tree->bh = EH; rc->bh = EH;
     
253.                           break;
     
254.                      case LH:
     
255.                           tree->bh = EH; rc->bh = RH;
     
256.                           break;
     
257.                      case RH:
     
258.                           tree->bh = LH; rc->bh = EH;
     
259.                           break;      
     
260.                }
     
261.                ld->bh = EH;
     
262.                Right_Rotate(tree->rchild);
     
263.                Left_Rotate(tree);
     
264.                shorter = 1;
     
265.                break;
     
266.           /*
     
267.           when insert , this case will not be ture, it just for delete action
     
268.           */
     
269.           case EH:
     
270.                rc->bh = LH; tree->bh = RH;
     
271.                Left_Rotate(tree);
     
272.                shorter = 0;
     
273.                break;
     
274.     }
     
275.     return shorter;
     
276. }
     
277. static int deleteavl(AVLTree & tree, AVLTree link, int & shorter)
     
278. {
     
279.        int sht;
     
280.        shorter = FALSE;//forget give this default value  
     
281.        //case: only two node, root and his lchild, delete the root node
     
282.        //Only this case, the link will not be a leaves node
     
283.        if (link == tree && tree->lchild)
     
284.        {
     
285.            tree = link->lchild;
     
286.            shorter = TRUE;
     
287.            return 1;
     
288.        }
     
289.        if (link == tree)
     
290.        {
     
291.            tree = link->rchild;
     
292.            shorter = TRUE;
     
293.            return 1;
     
294.        }
     
295.       
     
296.        if (link->item < tree->item)
     
297.        {
     
298.            deleteavl(tree->lchild, link, sht);
     
299.            if (sht)
     
300.            {
     
301.                switch (tree->bh)
     
302.                {
     
303.                       case EH:
     
304.                            tree->bh = RH; shorter = FALSE; break;
     
305.                       case LH:
     
306.                            tree->bh = EH; shorter = TRUE; break;
     
307.                       case RH:
     
308.                            shorter = Right_Balance(tree); break;
     
309.                }
     
310.            }
     
311.        }
     
312.        else
     
313.        {
     
314.            deleteavl(tree->rchild, link, sht);
     
315.            if (sht)
     
316.            {
     
317.                switch (tree->bh)
     
318.                {
     
319.                       case EH:
     
320.                            tree->bh = LH; shorter = FALSE; break;
     
321.                       case RH:
     
322.                            tree->bh = EH; shorter = TRUE; break;
     
323.                       case LH:
     
324.                            shorter = Left_Balance(tree); break;
     
325.                }
     
326.            }
     
327.        }
     
328.        return 1;
     
329. }
     
330. 
     
331. static AVLTree deleteAVLNode(AVLTree & tree, Item item)
     
332. {
     
333.         int shorter;
     
334.         Item t;
     
335.         AVLTree y, x = findAVL(tree, item);
     
336.         if (!x){std::cerr << "Cant delete Non Exist Node from a AVL Tree" << std::endl;return NULL;}
     
337.         if (x->rchild)
     
338.         {
     
339.             y = x->rchild;
     
340.             while (y->lchild)
     
341.             {
     
342.                   y = y->lchild;
     
343.             }
     
344.         }
     
345.         else
     
346.         {
     
347.             y = x;
     
348.         }
     
349.         deleteavl(tree, y, shorter);
     
350.         if (y != x)
     
351.         {
     
352.             t = x->item; x->item = y->item; y->item = t;
     
353.         }
     
354.         return y;
     
355. }
     
356. 
     
357. int deleteAVL(AVLTree & tree, Item item)
     
358. {
     
359.      AVLTree x = deleteAVLNode(tree, item);
     
360.      if (x)
     
361.      {
     
362.         delete x;
     
363.         return 1;
     
364.      }
     
365.      else
     
366.      {
     
367.          return 0;
     
368.      }
     
369. }
     
370. 
     
371. void destroyAVL(AVLTree & tree)
     
372. {
     
373.      Item min = minAVL(tree);
     
374.      AVLTree x;
     
375.      while (!emptyAVL(tree))
     
376.      {
     
377.            x = deleteAVLNode(tree, min);
     
378.            showAVLTreeNode(x);
     
379.            delete x;
     
380.            min = minAVL(tree);
     
381.      }
     
382. }
     
383. 
     

复制代码

文件: AVL_ADT_user.c

1. 
   
2. /*-----------------------------------------------------------
   
3.         AVL的ADT用户程序
   
4.         Author: QingXiaoming, 12-06, 2007([url]http://www.cublog.com/augustusqing/[/url]
   
5.        您可以自由拷贝,修改，分发这份代码，但请注明原作者
   
6. -------------------------------------------------------------*/
   
7. #include <iostream>
   
8. #include "include/AVL_ADT.h"
   
9. 
   
10. int main(int argc, char *argv[])
    
11. {
    
12.     int i, N = atoi(argv[1]);
    
13.     Item t;
    
14.     int taller;
    
15.     long start, stop;
    
16.     //AVLTree x  = NULL;
    
17.     AVLTree tree = initAVL();
    
18.     int *a = new int[N];
    
19.     start = clock();
    
20.     for (i = 0; i < N; i++)
    
21.     {
    
22.         t = rand();
    
23.         a[i] = t;
    
24.         //std::cout << t << std::endl;
    
25.         insertAVL(tree, t, taller);
    
26.     }
    
27.     //pretravseAVL(tree);
    
28.     //std::cout << std::endl;
    
29.     //midtravseAVL(tree);
    
30.     std::cout << std::endl;
    
31.   
    
32.     for (i = 0; i < N; i++)
    
33.     {
    
34.         t = a[i];
    
35.         //std::cout << t << std::endl;
    
36.         //pretravseAVL(tree);
    
37.         //std::cout << std::endl;
    
38.         deleteAVL(tree, t);
    
39.         //midtravseAVL(tree);
    
40.         //std::cout << std::endl;
    
41.     }
    
42.     //std::cout << "Tree state " << emptyAVL(tree) << std::endl;
    
43.     destroyAVL(tree);
    
44.     std::cout << "Tree state " << emptyAVL(tree) << std::endl;
    
45.     stop = clock();
    
46.     std::cout << stop - start << std::endl;
    
47.     delete []a;
    
48.     return 0;
    
49. }
    
50. 
    

复制代码

augustusqing

好强的模板功底！
拜读。。。。。。