阔别已久的技术文：关于BST

好久没发专业相关的文了，之前太寂寞了 T_T
其实我邮箱里面还积攒了几篇的，不过由于写得太长了所以还没写完……
& 其实这篇比较弱小……
---------------------------------------------------------------------------------------

OK。言归正传。BST = Binary Search Tree，
学过数据结构之后其实很久没碰到过了，不过其作为各种变形的祖先，作用还是非常大的。
在BST上可以定义查找、插入、删除等一系列动态操作，但复杂度跟tree的高度h有关，为O(h)。
因此如果在插入顺序做手脚，可以使得其h推化成节点个数n，这样很不好。

因此有关它的各种拓展就出来了。最早的应该是AVL树吧。
即所谓高度平衡的二叉查找树。通过保证叶子的最大高度与最小高度之差不超过1来确保平均复杂度控制在O(lgn)内。
同时它貌似也是第一个提出旋转概念的树，因此意义还是蛮大的。
（题外话：以前刚学data structure时，觉得AVL巨难无比，今天重新看起来，对比起红黑树等，还是非常简单的……）

接下来有红黑树，伸展树，treap等其它好的BST，待我一一道来 ....

红黑树很复杂，bug大牛很不推崇，不过其实其原理很简单。
通过保证其红黑属性（天知道作者怎么想出来的），来使得树的高度不超过2lg(n+1)，因此使得动态操作的复杂度早O(lgn)内。
因为它还是一颗二叉树，所以基本操作都有。但是就是每次操作完可能需要一些额外的东西来保证红黑属性的维持。
主要就是插入和删除。它们基本上也是通过旋转并着色来维持红黑属性的。
CLRS上的《数据结构的扩张》里都是基于RBtree的拓展，在rbtree的基础上找到集合第i小的元素等。

treap很好玩。它结合了最小堆以及BST的特点。这也是名字的由来：tree+heap=treap. 好玩。
即在BST的基础上，对于每个插入的node，赋予一个随机的priority。并且按照堆的定义对树进行组织。
因此它既是BST又是min heap。具体来说：
(1) 对于每个node，它的左子女的key不比它大，右子女的key不比它小。 // 保持了BST属性
(2) 对于每个node，它的左右子女的weight都比它大。 // 最小堆属性。
每次插入跟常规BST插入一样，但是可能会破坏heap属性，因此要通过旋转来恢复堆属性。
可以证明，这个操作能在O(lgn)时间内完成。
有一个属性是非常有趣的：对于一个集合S，如果每个元素对应的priority确定不变，
那么有且只有一棵对应的treap。这可以通过堆+BST属性来证明。
总的来说treap思想很简单，很实用 ，我喜欢 :)
CLRS上说它是LEDA内的字典的实现。

splay tree据说没有红黑树那么复杂。它的平摊复杂度能达到O(lgn)，在实际应用中performence很好。
主要原理是：当每次查询一个node时，把它旋转到root，在旋转时要注意尽量使树平衡。
因此这样做的话，能使得可以无视查询的具体次序。
试想：即使每次查询都是查询深度最大的node，在若干次后总能使树平衡，这时高度为lgn，因此查询复杂度成为O(lgn)。
所以说它的amortized complexity可以打到O(lgn)。
splay tree还能用于帮助实现动态树（dynamic tree），此处略。

另外还有相当多的平衡二叉树，包括带权平衡树，k邻居树，跳表，B树等。
如果要把它们写完，则这篇文章估计又躺在email draft里了……因此这次对于BST的复习归纳还是暂告一段落吧……