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

Neil Brown精妙的avl实现

最近在复习数据结构，看到avl树，这样比较复杂的数据结构通常都很搞人。于是上网，找到一个实现看，写这代码的老外叫Neil Brown，一个大胡子，我们知道，在国外，开发人员的水平经常和胡子的多少成正比。还看到他在blog中说，这个代码打算用在linux kernel里，自然不会是普通代码了。 
我拿下来，狠看一阵才看懂，不得不说，这个代码很多地方的实现是很精妙的，和教材上只是为了让你理解概念的代码，区别很大。 
这个实现有一个特点，就是没有一般树实现中的left和right指针，作者用一个数组next[2]来表示，next[0]就是左子树，next[1]就是右子树，然后每个节点也不保存当前的层高，这个是教科书的做法，int longer:2，极其省俭的表示了是左子树长（值为0)，还是右子树长(值为1)，或者当前节点上这颗树是平衡的(值了-1)。 

C代码  

1. /* 
2.  * Usage:  avl3  list of integers ... 
3.  * 
4.  * Each integer will be checked to see if it is currently in 
5.  * the AVL tree.  If not, it will be inserted. If so, it will 
6.  * be deleted.  The tree starts out empty and the final tree is 
7.  * printed (on its side) in an ASCII-art style 
8.  */  
9.   
10. #include   
11. typedef int value_t;  
12.   
13. #define LEFT 0  // 表示左节点，或者左子树长  
14. #define RIGHT 1 // 表示右节点，或者右子树长  
15. #define NEITHER -1 // 以当前节点为根的子树是平衡的  
16. typedef int direction; //重定向一个，表示操作是在左子树还是右子树上  
17. // 树节点的定义  
18. typedef struct node_s {  
19.    value_t        value;  
20.    struct node_s *next[2];  
21.    int            longer:2;  
22. } *node;  
23. #define Balanced(n) (n->longer < 0) // 平衡时值了-1  

这里开始精妙了，我们平时的tree查找是怎么写的，target小于当前节点就下到左子树 
继续找，大于就下到右子树继续找，这里就用一个direction next_step = (target > tree->value)得到了接下来操作的方向。next[next_step]就是接下来要查找的节点 

C代码  

1. node avl_find(node tree, value_t target)  
2. {  
3.     while (tree && target != tree->value) {  
4.         direction next_step = (target > tree->value);  
5.         tree = tree->next[next_step];  
6.     }  
7.     return tree;  
8. }  

作者不大喜欢single rotation和double rotation这样的说法，他把旋转分为两种，一种是2旋，就是single rotation，这个时候用数组的优势就出来了，不用把相似的single rotation写两遍，传入的dir值不同就可以了。 

 

C代码  

1. static node avl_rotate_2(node *path_top, direction dir)  
2. {  
3.     node B, C, D, E;  
4.     B = *path_top;  
5.     D = B->next[dir];  
6.     C = D->next[1-dir];  
7.     E = D->next[dir];  
8.   
9.     *path_top = D;  
10.     D->next[1-dir] = B;  
11.     B->next[dir] = C;  
12.     B->longer = NEITHER;  
13.     D->longer = NEITHER;  
14.     return E;  
15. }  

这里是三旋转，也就是double rotation. 
 
注意旋转后面third变量的作用，third表示新入节点在C还是在E上。如果在E上，独立的C的高度必小于A，因为在E上还没有插入新节点时，C只比A高1,而且C上有D，F垫底，所以独立的C的高度要减2,所以独立的C比独立的A高度小1。 

C代码  

1. static node avl_rotate_3(node *path_top, direction dir, direction third)  
2. {  
3.     node B, F, D, C, E;  
4.     B = *path_top;  
5.     F = B->next[dir];  
6.     D = F->next[1-dir];  
7.     /* note: C and E can be NULL */  
8.     C = D->next[1-dir];  
9.     E = D->next[dir];  
10.     *path_top = D;  
11.     D->next[1-dir] = B;  
12.     D->next[dir] = F;  
13.     B->next[dir] = C;  
14.     F->next[1-dir] = E;  
15.     D->longer = NEITHER;  
16.   
17.     /* assume both trees are balanced */  
18.     B->longer = F->longer = NEITHER;  
19.   
20.     if (third == NEITHER)  
21.         return NULL;  
22.     else if (third == dir) {  
23.         /* E holds the insertion so B is unbalanced */   
24.         B->longer = 1-dir;  
25.         return E;  
26.     } else {  
27.         /* C holds the insertion so F is unbalanced */  
28.         F->longer = dir;  
29.         return C;  
30.     }  
31. }  

插入新节点后已经，树已经不平衡了，需要重新计算节点上的longer值。 

C代码  

1. /*************************************************** 
2.  * INSERTION                                       * 
3.  ***************************************************/  
4. static inline void avl_rebalance_path(node path, value_t target)  
5. {  
6.     /* Each node in path is currently balanced. 
7.      * Until we find target, mark each node as longer 
8.      * in the direction of target because we know we have 
9.      * inserted target there 
10.      */  
11.     while (path && target != path->value) {  
12.         direction next_step = (target > path->value);  
13.         path->longer = next_step;  
14.         path = path->next[next_step];  
15.     }  
16. }  

这里是插入新节点后使树重新平衡的全过程，包括旋转节点和更新高度信息。path_top是更新的起点。如果path_top节点是平衡的，不需要旋转，更新高度信息即可。如果在较短和路径上插入，也不需要旋转，还是更新高度信息，path_top变成平衡的，然后对插入的那棵树更新高度信息。如果在较长的路径上插入，就需要旋转了，first和second表示两次的操作方向，如果相同，就是2旋转，否则是3旋转，这时要注意third变量，如果C和E都为空，那么third变量就是NEITHER，不需要特殊处理，否则，third就传入3旋转的函数，用于下面更新高度信息。 

C代码  

1. static inline void avl_rebalance_insert(node *path_top, value_t target)  
2. {  
3.     node path = *path_top;  
4.     direction first, second, third;  
5.     if (Balanced(path))   
6.         ;  
7.     else if (path->longer != (first = (target > path->value))) {  
8.         /* took the shorter path */  
9.         path->longer = NEITHER;  
10.         path = path->next[first];  
11.     } else if (first == (second = (target > path->next[first]->value))) {  
12.         /* just a two-point rotate */  
13.         path = avl_rotate_2(path_top, first);  
14.     } else {  
15.         /* fine details of the 3 point rotate depend on the third step. 
16.          * However there may not be a third step, if the third point of the 
17.          * rotation is the newly inserted point.  In that case we record 
18.          * the third step as NEITHER 
19.          */  
20.         path = path->next[first]->next[second];  
21.         if (target == path->value) third = NEITHER;  
22.         else third = (target > path->value);  
23.         path = avl_rotate_3(path_top, first, third);  
24.     }  
25.     avl_rebalance_path(path, target);  
26. }  

avl_insert是插入接口，这里又有一个技巧，对于avl树，不用从根节点上开始更新高度信息。开始更新高度信息的起点，是path_top。如果查找的一路上下来，每个节点都是平衡的，那么只能从根上开始更新，否则，从第一个不平衡的节点开始更新。插入完成后，再调用avl_rebalance_insert来平衡树。 

C代码  

1. int avl_insert(node *treep, value_t target)  
2. {  
3.     /* insert the target into the tree, returning 1 on success or 0 if it 
4.      * already existed 
5.      */  
6.     node tree = *treep;  
7.     node *path_top = treep;  
8.     while (tree && target != tree->value) {  
9.         direction next_step = (target > tree->value);  
10.         if (!Balanced(tree)) path_top = treep;  
11.         treep = &tree->next[next_step];  
12.         tree = *treep;  
13.     }  
14.     if (tree) return 0;  
15.     tree = malloc(sizeof(*tree));  
16.     tree->next[0] = tree->next[1] = NULL;  
17.     tree->longer = NEITHER;  
18.     tree->value = target;  
19.     *treep = tree;  
20.     avl_rebalance_insert(path_top, target);  
21.     return 1;  
22. }  

明天再写删除的，太晚了。