我在wiki上发现了N种平衡树。。不得不感叹数据结构的博大精深。。
AVL和SBT实际上思想上差不多。。
都是运用某种数值将树平衡起来。。
AVL是高度。。SBT是大小。。
在AVL中两棵子树高度不会差太多（从而保证大小不差太多）。。
SBT中大小不会差太多。。
甚至我感觉SBT就是简化版的AVL。。
因为其中左孩子大小不小于右边的两个孙子大小的规定
太像高度不差一了。。

Treap比较NB。。它利用了随机树是平衡的
所以用了一种tree+heap的方法动态产生随机树。。
但树高度就不怎么样了。。
但他是最好写的。。

红黑树是用节点的颜色来是树中任意两条路径长度不差2倍。。
所以也是平衡的。。不过总是让我感觉太精巧和复杂了。。
不知是怎么想出来的。。算法导论上有。。就不多说了。。

2-3树更诡异。。它跟AA树是同构的。。
他一个节点可以是普通的2节点。。就是两个孩子。。
也可以是3节点。。就是说3个孩子。。
一般的节点存一个值。比如是x。。
将子树分为<x和>x的。。
而3节点存两个值x,y。。
将子树分为<x,(x,y),>y三个部分。。
然后在插入的时候如果2节点变成3节点了。。没事。。
如果3节点变4节点了。。就分裂一下。。把中间那个提上去。。。。
2-3树高度是严格logn的。。不过3节点很多。。
查起来也差不多是2logn的。。。

2-3-4树。。就是说不但有2，3节点。。还有4节点。。搞死人的东西。。
跟2-3树差不多。。

splay。。我最喜欢的。。它主要就是每次访问到一个节点。。就把它转成根。。
算是最NB和自然的数据结构了。。不过就是太慢了。。
个人感觉是最好写的。。这家伙的长度一般是3-4*logn。。

红黑树有一个很BT的特点就是维护的时候最多旋转2次。。。所以stl就用这个了。。
而AA树是红黑树的一个变种。。规定左边的孩子不能为红色。。所以维护的时候可能转的
更多。。但似乎是AA树更快一点。。不过stl追求的是稳定。。

Scapegoat tree是让两个孩子的大小都小于a*父亲的大小。。
维护起来很诡异。。每次都是找一个最高的那个不满足的顶点。。
直接暴力重建成近完全2叉树。。均摊是logn的。。