Not so bad

KingSoft announced the openSource of defense software today (http://code.ijinshan.com). No matter what the purpose they have, it's a big thing in our industry.

But I saw a post http://www.cnblogs.com/MichaelPeng/archive/2010/12/02/1893999.html , criticized the quality of the source code.

But I just think it's not so bad. I checked several abstract class. I found that all the abstract class have such form.

class IInterface {
virtual void method1() = 0;
virtual void method2() = 0;
...
};

It means that they only use abstract class as a interface (just like Java's interface), never mix up with its implementation. All the abstract classes with an "I" as a prefix, only have pure virtual functions. It's a good habit. KingSoft can deliver so many products through their source code's quality is very good, but as we can see, it's not so bad.

restart from here

Let's restart from here.

It's a shame to look back to the old articles I posted. Poor understanding about .NET and the history of computer software platform. Life before .NET is not primitive society, I just ignore other operating systems (like Unix/Linux) and other language platforms (like Java). Now I'm not a windows programmer, and I know that I have a lot of things to learn.

I started so many topics, but I never finished even one (included my another blog hosted on Javaeye). I must change it. I plan to write my blog with my pity English every Saturday night. So, let's just restart from here.

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

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