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

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