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

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

为什么STL中的string没有实现operator const char*

std::string（我们就默认是std::basic_string吧）没有直接实现operator const char*，而是用一个c_str()函数来实现这个转换，我过去一直对STL这个舍近求远的做法不大理解，不过最近碰到一个应用场景，说明了这个做法的合理性。 

Java代码  

1. const char* foo()  
2. {  
3.     .......  
4.     // 这里正确的写法是str.size()?str.c_str():0;  
5.     return str.size()?str:0;  
6. }  

如果std::string实现了operator const char*,在这个三元运算符内就会产生一个微妙的问题，就是编译器在进行计算的时候，并不是选择自动对str进行const char*的转型操作，而是选择了对所有参与运算的变量进行类型提升，这里类型提升怎么样提？这里自然是把做为构造函数的参数，来构造一个临时的string对象，在效率上用户可能无法接受，在某些特殊的场景还可能引起程序的错误。不明显的隐式转换，这只是一个例子，无数的陷井还程序中，让后期的调试苦不堪言。 

如果对象是用户自定义，最好选择尽量在构造函数前加explicit，来禁掉通过隐式转换来不明不白地调用拷贝构造函数，创建临时对象。我看了basic_string的定义，构造函数没有加explicit关键字，那么就选择了禁掉operator const char*。 

Book review of "Time Management for System Administrators" (1)

"Time Management for System Administrators"是我第一次读时间管理方面的书,应该来讲还是感触比较深.读了也有两个月了,可真正的时间管理一直没有用起来. 虽然用了google日历,感觉也就是做做样子,而且也不太坚持.可见很多时候,并不是求不着道,而是道在那儿,人却不去理会.

此书是写给系统管理员的,不过程序员也可以在中间学到很多东西.作者在前言里说"This book is not for programmers. Beta readers told me that programmers should find this book extremely useful, but I feel that programmers have different issues and therefore deserve their own book."

我大概总结下我觉得书中对于程序员有用的地方,不过想要养成新习惯,重要的不是知道新习惯如何如何好,而是坚持使用新习惯.据说培养一个新习惯只要1个月,但是这一个月一定要坚持,不然就前功尽弃.我们身上的坏习惯都太多了,每天改掉一点,一个月,就会有巨大的提高.

首先,时间管理的原则是:1.一个管理工作(PDA或者纸笔);2.为那些重要的工作节省脑力;3.使用例程,并坚持它们;4.培养习惯和个人原则;5.在"项目时间"里保存专注;6.在工作以外的社会生活也坚持使用.

对于完成工作,专注非常之重要.SA想要专注并不大容易,因为时时有人找.但程序员一般都会有一些个人空间,帮助进入专注状态.工作中的干扰,最好可以完全避免,因为一但手头的工作被打断,你重新上手的时间可能比你完成剩余工作的时间更长.保存专注还有一些小帖士,比如保持桌子和电脑桌面的清洁,消除办公室里让你分心的东西,禁掉IM,邮件通知等等.同时,注意自己在一天的哪个时间段内最容易专注,在那个时间段内做优先级比较高的工作.最后,因为一天的早上人和事都比较少,可以考虑早点去公司,在那一段时间完成工作.

对于分配的任务,不要认为可以就用大脑记着,一定要用时间管理工具记下来.而且只有记录下来,才可以进行方便的计划,而不是被干扰打断.

大部分人每天的工作都是很无聊的,可以说是例行公事,但是如果例行公事都做不好,就不要考虑做别的更有意义的事情了.将那些琐碎的工都编排起来,记录为每日的例行公事,这样你就不会遗漏,而且也不用每天想有哪些琐碎的事要做.

人的生活是个不断的循环,也可以说是螺旋着上升吧.(也可能是原地转圈,或者说干脆是下降).时间管理也是一个管理循环的系统.时间管理的工具有三个特点,方便携带,可靠,和便于管理.因此,具体来说,时间管理系统的组成元素是这几样.日历,人生目标,每日计划,包括Todo list和Schedule.每天早上,用十分钟来计划自己这一天,检查日历,Todo list,置定Schedule.

.NET学习手记(1)-.NET之前的洪荒年代

如果我没有记错，微软是在2002年的2月14号,就是情人节那天，将.NET推到世人面前的，现在2009年了，.NET已经发展了7年，版本已经到3.5，4.0也马上要推出了。这个时候，我才开始学习.NET，作为一个Windows程序员，应该深感羞愧才对。

程序员不管学习什么，有条重要的途径都是看书。我在项目并用不上.NET时，只好先比看书起，陆陆续续开始看相关的书。国人写的＜你必须知道的.NET>，老外写的。现在在看的有<.NET本质论＞和，计划中的有，还有微软的sscli也打算研究。

我计划写这篇笔记很久了，我的计划是首先谈为什么要有.NET，结果刚开始看＜.NET本质论＞时，就发现Don Box非常清楚和深刻地讲了这个问题。Don Box提到.NET Framework从根本上讲提供了两个核心的集成技术：CLR和XML Web Service，后者我不大了解,没有接触。对于CLR，他则指出，CLR is better COM.

就我个人的理解，.NET的出现，是给机器与程序员之间增加了一层抽象形。原来的层次是 机器－＞操作系统API－＞程序员。Windows的API这个集合极大，是不可能完全掌握的怪物，作为补救，微软推出了MFC啊,WinInet啊之类库，但是这些都只是一层薄薄的封装，谈不上抽象层。而.NET，则是插入操作系统API和程序员之间的一个巨大的抽象层。从概念到编程语言，都是全新的。

另一个来源的支柱就是COM，在.NET之前，COM是Windows平台上支柱型的编程模型。但是COM的问题和它的好处一样多。首先就是复杂，COM是一种二进制接口，基于C＋＋的二进制模型，要求使用者至少得非常熟悉C＋＋。即使如此，在学习COM的过程中，依然会有无数的障碍。Joe甚至认为，COM让微软失去了整整一代程序员。

再者，COM没有实现继承，虽然微软认为，COM强制接口与实现分离，且只提供接口继承，是为了程序员好，但是它又提供了包容与聚合两种所谓的对象复用的方法，结果上就有一条，COM aggregation and COM containment are for identity tricks,not code reuse。

COM对象的生命期依赖于引用计数，而非真正的垃圾收集。我个人觉得引用计数总会给人一种资源管理就安全了的错误感觉，从而忽略了循环计数这种常见却难于发现的情况。而对于复杂一点的系统（如果还经常改变的话），想避免这个问题真的很难。

COM的套间，则是一个典型的提供策略非而机制的例子。STA吧，初看起来感觉是很好很强大，但是实际使用中，发现它简直是死锁之源（至少是假死）。

Don Box书中还提到了其它COM的弱点，比如tlb和IDL没有什么关系，COM不能定义依赖关系。其实，COM设计的时候，考虑的效率，而非易用，采取最小原则，需要最少的统一的 C++ 实现方式。这种方式，当时是必须的，现在看起来却不大合适。

总的来讲，CLR出现之前，的确是个洪荒年代，等我再看阵书，再接着谈感想。

怎样在Linux中文环境下使用drScheme

sili@sili-laptop:~$ LANG=C drscheme
这样启动，就可以正常输入了.