今天的几点感悟

今天实在很无聊，一点也不想工作，我不知道我这个人在无聊的时候除了思考还能干些什么，不过想到快30了还没有一点作为就一身冷汗，说什么也没有用，除了继续思考之外没有任何退路。

突然想到了AVL树和红黑树，都知道这两种树的复杂度到了变态的境界，都知道红黑树比AVL树的统计性能好，都知道AVL树和红黑树的插入简单和删除困难，这些信息在任何的教科书上都有论述，我看了很多书，但是没有一本书讲为什么会这样，于是我今天就花了一点时间思考了一下，先说说为何红黑树比AVL树性能好吧，如果按照常规的，按照两棵树的性质来进行数学推理的话，它们操作的时间复杂度是一样的，可是按照信息论，越是信息量大的东西越是难以维持，越想构建严格的东西越是耗费精力，AVL树比红黑树更加严格，因此它必然要耗费额外的时间来维护这种严格，而这种额外的花费正是花在了每次操作中，比如插入，删除等等，对于查找，可能AVL树更加好一些，因为AVL树严格的平衡性使树的高度尽可能低，这样就可以减少平均查找的最短路径，而红黑树中子树间的高度差可以接近两倍，这样就增加了树高，这对于查询是很不利的，可是红黑树又不至于退化到一个线性链表的地步，于是红黑树在决定平衡的树和线性链表这种绝对不平衡的树之间取得了很好的折中，虽然AVL树也进行了折中，毕竟它也不是绝对平衡的，可是它还是过于严格，没有像红黑树那样恰到好处，绝对平衡的二叉树和绝对不平衡的线性链表是两个极端，前者维护了大量的信息，但是操作复杂，后者不需要维护任何信息可是操作简单，可是这里的操作还要看什么操作，像插入这种操作一部分是依赖于查询的，它的另一部分就是平衡信息的维持，如果说一个节点比较懒惰，它只看好平衡二叉树的查找性能而快速插入二叉树中，这时它什么也不管了，不再维护平衡信息，那么这棵树随着这种不负责任的节点越来越多的插入，这棵树最终就会退化到一个线性链表，系统不会任其这么做，于是不能任凭节点没有任何代价的插入，于是每个节点在插入时都要承担一些平衡信息维护的工作，如果按照平衡树的概念，那么插入的时间复杂度都是O(logN)，不管每次插入需要维护多少平衡信息都是这样，只要你去做了，就有希望完全平衡，而完全平衡的时间复杂度就是O(logN)，算法都是按照最值进行计算的，只要你去尽力维持平衡，那么就按照完全平衡的时间复杂度算，仅仅因为有可能完全平衡，前面说过努力的太多就会使得操作更耗时，努力过少又会使得将来查找失去优势，于是就有一个权衡，红黑树做好了这个权衡，提供了最好的最坏性能，真的很佩服红黑树的设计者，竟然能想出用红黑节点来处理平衡问题，黑节点做平衡限制，而红节点则尽力反抗这种限制，其实就是黑节点给了红节点一个活动的范围，这个范围使用于树中的所有红节点，使得在不得不进行平衡操作的时候才进行，又是一个延迟的偷懒算法。

对于上述的论述，直接结论就是红黑树比AVL树有更好的统计性能，AVL树必须在更小的范围内进行平衡操作，不过如果数据分布的比较随机，那么AVL树的性能可能会更好，但是对于组织的比较有序的数据，红黑树就比较好了，因为红黑树不对称，它会偏向某些范围内的节点。对于插入比删除复杂这个问题是很容易理解的，因为平衡树是按照插入来构建的而不是靠删除来构建的，这是第一，第二就是平衡树的平衡操作用旋转来完成，所谓平衡就是削减高度变为宽度，毕竟不能无故丢掉节点，问题就在于不管是插入还是删除都是用平衡操作来维持平衡的，插入可能使树增高，而平衡使树降低，一升一降，正好抵消，而删除会使树降低，平衡又使树降低，连续降低就可能越来越不平衡，这就是原因。

一切都是哲学，我们现在可能无法知晓设计者当初的想法，可是我们可以天马行空的设想我们自己的理由，我们如果勤奋而不是聪明的话，那么我们就可以设计出自己的算法，然后在将来也让别人不知道我们自己是怎么想的。好了，如果说上面的问题比较深奥的话，那么下面的问题是比较轻松地，就是数组和指针的区别。

教科书里都在说数组实际上是个指针，学生们听的多了就会觉得数组和指针是一样的，可是教科书并没有反过来说指针就是数组，因此必须明确知道这二者的区别，实际上数组就是一个数据类型，把它类比成结构体就比较好理解了，如果我写了下列定义：

typedef struct{

int iValue;

int iSend;

}Class,*PClass;

那么只要学过C语言的人看到了PClass都会知道它是个指针，代表一个结构体，而结构体内部各个字段在内存中都是连续的，数组也是这样，无非就是用[]运算符代替了上面的typedef的定义，数组无非就是和上面的*PClass类似的定义，数组也可以看做一个结构体，里面的数据内存中连续，这是很显然的，真如上面的例子一样，而指针呢，它只是一个基本数据类型，在32位机器上是一个32位的无符号数字，代表一个地址，而char *代表的地址处的数据在遇到/0的时候结束本次的char *指向的数据的定义，仅此而已。

快睡觉了，看了一篇负载均衡的论文，大致讲一个依据贪心算法的近似算法的数学证明，妈的困死了，不写了...