Avl树实现的续

接着看删除部分，删除部分比插入要更难搞一些。对于删除，同样需要分情况讨论。 
1.如果是在一个平衡节点下删除，只要把这个节点的高度信息修改就可以了 
2.如果是在较长的子树下删除，就把这个节点的高度信息修改成平衡 
以上两种情况都不需要进行旋转。 
3.如果是在较短的子树下删除，除了更新高度信息外，还需要旋转节点。这时又分3种情况讨论。 
3种情况的图如下，直接针对编程就可以了 

 

 

 

与插入一样，删除时不必从树根开始更新，记录一个path_top即可。如果某个节点是平衡的，那么删除不会影响到它以上的节点，如果某个节点下的情况和图1相同，那么删除也不会影响到它以上的节点。这时可以把path_top设为该节点。另外，treep是指向删除节点右子树中最小的节点，如果用中序遍历，就是下个节点，将用它的值来代替删除节点。 

C代码  

1. int avl_delete(node *treep, value_t target)  
2. {  
3.     /* delete the target from the tree, returning 1 on success or 0 if 
4.      * it wasn't found 
5.      */  
6.     node tree = *treep, targetn;  
7.     node *path_top = treep;  
8.     node *targetp = NULL;  
9.     direction dir;  
10.       
11.     while (tree) {  
12.         dir = (target > tree->value);  
13.         if (target == tree->value)  
14.             targetp = treep;  
15.         if (tree->next[dir] == NULL)  
16.             break;  
17.         if (Balanced(tree)  
18.             || (tree->longer == (1-dir) && Balanced(tree->next[1-dir]))  
19.             ) path_top = treep;  
20.         treep = &tree->next[dir];  
21.         tree = *treep;  
22.     }  
23.     if (!targetp)  
24.         return 0;  
25.   
26.     /* adjust balance, but don't lose 'targetp' */  
27.     targetp = avl_rebalance_del(path_top, target, targetp);  
28.   
29.     /* We have re-balanced everything, it remains only to  
30.      * swap the end of the path (*treep == treep) with the deleted item 
31.      * (*targetp == targetn) 
32.      */  
33.     avl_swap_del(targetp, treep, dir);  
34.   
35.     return 1;  
36. }  

这一段代码负责重新平衡树，除了最后一个node更新之外(tree-next[dir] == NULL)，其余的都要更新高度信息，如有必要，还有旋转。 

C代码  

1. node *avl_rebalance_del(node *treep, value_t target, node *targetp)  
2. {  
3.     /* each node from treep down towards target, but 
4.      * excluding the last, will have a subtree grow 
5.      * and need rebalancing 
6.      */  
7.     node targetn = *targetp;  
8.   
9.     while (1) {  
10.         node tree = *treep;  
11.         direction dir = (target > tree->value);  
12.   
13.         if (tree->next[dir]==NULL)  
14.             break;  
15.   
16.         if (Balanced(tree))  
17.             tree->longer = 1-dir;  
18.         else if (tree->longer == dir)  
19.             tree->longer = NEITHER;  
20.         else {  
21.                         // 对比图可以看到，这个是第三幅图的场景  
22.             if (tree->next[1-dir]->longer == dir)  
23.                 avl_rotate_3_shrink(treep, dir);  
24.             else // 第一二幅图  
25.                 avl_rotate_2_shrink(treep, dir);  
26.                         // 这一句的作用，用targetp本身也在旋转过程中时，需要把它更新，targetp作为旋转的顶，而且三幅图里，都是转到&(*treep)->next[dir]  
27.             if (tree == targetn)  
28.                 targetp = &(*treep)->next[dir];  
29.         }  
30.                 // 为什么这里是tree而不是treep?  
31.                 // 是treep也可以，但是旋转后treep是tree的，这样要多遍历一个节点  
32.         treep = &tree->next[dir];  
33.     }  
34.     return targetp;  
35. }  

交换并删除的代码比较简单，如下 

C代码  

1. void avl_swap_del(node *targetp, node *treep, direction dir)  
2. {  
3.     node targetn = *targetp;  
4.     node tree = *treep;  
5.   
6.     *targetp = tree;  
7.     *treep = tree->next[1-dir];  
8.     tree->next[LEFT] = targetn->next[LEFT];  
9.     tree->next[RIGHT]= targetn->next[RIGHT];  
10.     tree->longer = targetn->longer;  
11.   
12.     free(targetn);  
13. }  

最后是后种旋转的代码实现，都比较直观，如果对着图看。 

C代码  

1. void avl_rotate_2_shrink(node *path_top, direction dir)  
2. {  
3.     node D, B, C;  
4.   
5.     D = *path_top;  
6.     B = D->next[1-dir];  
7.     C = B->next[dir];  
8.   
9.     *path_top = B;  
10.     B->next[dir] = D;  
11.     D->next[1-dir] = C;  
12.   
13.     if (Balanced(B)) {  
14.         B->longer = dir;  
15.         D->longer = 1-dir;  
16.     } else {  
17.         B->longer = NEITHER;  
18.         D->longer = NEITHER;  
19.     }  
20. }  
21.   
22. void avl_rotate_3_shrink(node *path_top, direction dir)  
23. {  
24.     node B, C, D, E, F;  
25.     F = *path_top;  
26.     B = F->next[1-dir];  
27.     D = B->next[dir];  
28.     C = D->next[1-dir];  
29.     E = D->next[dir];  
30.   
31.     *path_top = D;  
32.     D->next[1-dir] = B;  
33.     D->next[dir] = F;  
34.     B->next[dir] = C;  
35.     F->next[1-dir] = E;  
36.   
37.     B->longer = NEITHER;  
38.     F->longer = NEITHER;  
39.     if (D->longer == dir)  
40.         B->longer = 1-dir;  
41.     if (D->longer == 1-dir)  
42.         F->longer = dir;  
43.     D->longer = NEITHER;  
44. }