风过叶落
几个月前，小魚兒 同学在OIBH上提出了一种新型平衡二叉搜索树——DST（Double Size Tree，昵称SST，具体意义参见 小魚兒 的SST《正式版》）。最近几个月里我对DST进行了较为深入的研究分析，并对其理论复杂度作出了证明。在这里把成果拿出来与大家分享，希望可以对DST的推广作出贡献。
约定：在本文中，结点A代表一棵二叉搜索树中的某个结点，T(A)表示以结点A为根的一棵子树，S(A)表示这棵子树的结点个数，H(A)表示这棵子树距离根节点最远的结点与根结点之间的距离，即树的高度; Key[A]表示结点A的关键字，Left[A]表示结点A的左孩子，Right[A]表示结点A的右孩子。
一、DST中结点的插入与删除。
DST的插入与删除与普通二叉搜索树类似，只不过在插入或者删除完成之后利用一个maintain过程维护它的平衡（maintain过程将在下面讲到）。在这里近仅对插入和删除做一点简单说明，然后直接给出伪代码。
（1）插入操作
插入操作的基本思想是，每次比较待插入结点与当前结点的关键字，如果前者较小，就递归地插入到左子树中，否则就插入到右子树中。
插入操作的伪代码如下：
| 1 | Insert(k,p) |
| 2 | S[p] ← S[p]+1 |
| 3 | If p=Nullnode then |
| 4 | p←Newnode(k) |
| 5 | Exit |
| 6 | If Key[p]>k then Insert(k,Left[p]) |
| 7 | else Insert(k,Right[p]) |
| 8 | Maintain(p,Key[p]>k) |
BST的删除操作有许多种实现方法，其中每一种都可以用在DST的删除中。这里只提供一种，思想是先找到待删除结点，然后用左子树中关键词最大或者右子树关键词最小的结点替代根结点，最后后再把最值结点删除。这样可以使删除后的DST相对更加平衡。
删除操作的伪代码如下：
| 1 | Delete(k,p) |
| 2 | S[p] ← S[p]-1 |
| 3 | If Key[p]>k then Delete(k,Right[p]) |
| 4 | else |
| 5 | If Key[p]=0 then |
| 6 | If S[p]=0 then p=0 |
| 7 | else |
| 8 | If S[Left[p]]>=S[Right[p]] then |
| 9 | Key[p]←maximum(Left[p]) |
| 10 | Delete(Key[p],Left[p]) |
| 11 | else |
| 12 | Key[p]←minimunm(Right[p]) |
| 13 | Delete(Key[p],Right[p]) |
| 14 | else delete(k,Right[p]) |
| 15 | Maintain(p,ture) |
| 16 | Maintain(p,false) |
（1）DST的旋转
在介绍具体算法之前，有必要明确一下二叉搜索树保持平衡的方法——旋转。
图 1
一棵如上图左所示的二叉树可以通过左旋Left-Rotate（A）变成图右所示的结构，同样的，右面的二叉树也可以通过右旋Right-Rotate（B）变成图左所示的结构。
和其他平衡树一样，DST通过旋转来维持平衡。在这里我们定义两种“组合旋转”。
如下图所示，仅对T(A)做一次左旋或者右旋操作，叫做对T(A)进行“简单旋转”。
图 2
如图3所示，对T(Left[A])做一次左旋操作，然后对T(A)做一次右旋操作；或者对 T(Right[A])做一次右旋操作，然后对T(A)做一次左旋操作，叫做对T(A)进行“复杂旋转”。
图 3
由于这两种组合旋转分别包含的两种操作是对称的，我们可以将它们放在一起考虑而不至于遗漏某些情况。许多平衡树如AVL和SBT等的平衡调整都是基于这两种操作的，DST也是如此。
（2）DST的平衡条件以及DST的定义
当一棵平衡树T(A)满足如下条件，我们就认为T(A)是平衡的
这个条件被称为DST的平衡条件，在本文中简称平衡条件。
而DST则是递归定义的：当且仅当T(A)满足平衡条件并且T(Left[A]) 和 T(Right[A])都是DST时，我们认为T(A)是一棵DST。
（3）DST的平衡维护（maintain）以及维护的时间复杂度
在一棵DST（设为T(A)）中插入或者删除节点有可能会导致它不再平衡，这时需要利用maintain过程对T(A)进行维护。
首先给出maintain过程的伪代码：
| 1 | Maintain(p,flag) |
| 2 | If flag then |
| 3 | If S( Left[p] )<= S( Right[p] ) *2 +1 then exit |
| 4 | else |
| 5 | If S ( Left [ Lfet[p] ]) |
| 6 | Right_Rotate(p) |
| 7 | else |
| 8 | If S( Right[p] )<=S( Left[p]) *2 +1 then exit |
| 9 | else |
| 10 | If S ( Right[ Right[p] ] ) |
| 11 | Left_Rotate(p) |
| 12 | Maintain (Left[p],false) |
| 13 | Maintain (Left[p],true) |
| 14 | Maintain (Right[p],false) |
| 15 | Maintain (Right[p],true) |
从而导致T(A)不平衡的情况，而对称的情况可以得到类似的结论。
①如图2，当时，我们对T(A)进行一次简单旋转（右旋）。
②如图3，当时，我们对T(A)进行一次复杂旋转（左旋左子树，右旋整个子树）。
可以证明，这样旋转之后，整棵子树一定是平衡的。但是我们不能保证旋转后的左右子树也是平衡的，所以需要对左右子树进行维护。因为对于一棵子树的操作不会影响它的兄弟子树和它的父亲，所以没有必要再次对T(A)进行维护。
由于每次旋转之后T(A)所有结点的深度和至少减少了1 [2]，而这个深度和是的。因此建立一棵DST至多进行了次旋转，所以，对于T(A)的每个结点，插入或者删除它的均摊时间复杂度是。而插入一个结点共调用了次 maintain 操作，所以每次 maintain 的均摊时间复杂度是。
（4）DST的最坏高度
在以上的论述中，我们得到了DST支持的所有操作的时间复杂度都依赖于它的高度的结论，下面将给出DST的最坏高度是的证明。
令表示一棵高度为h的DST所拥有的最小的结点数。首先，很容易得到。其次根据树高的定义，一棵高度为h的DST至少拥有一棵高度为的子树，那么这棵子树的大小至少是。根据DST的平衡条件，它的另一棵子树的大小至少是，于是我们得到如下的等式
也即
所以。
也就是说一棵拥有n个结点的DST的最坏高度。这样我们就证明了DST的高度是的，尽管它的最坏高度可能会比SBT或者AVL的略大一点。
于是我们又可以得到更进一步的结论：DST的插入删除操作理论时间复杂度都是，这是可以令人满意的。同时，由于DST的高度是，普通二叉搜索树支持的最大（maximum），最小（minimum），排名（rank），第K大（select），前驱（pre），后继（suc）都可以在时间内完成。
三、DST在实践中的时间效率
对SBT、SBT退化版、AVL和DST进行极限数据的测试。共10组数据，每组数据范围（操作次数）都在上下，其中一组是峰状数据，一组是顺序数据，其余为随机数据（所进的操作也是随机产生的）。可以得到如下结果
而如果进行小数据测试——数据规模从到均匀分布，可以得到另外一组结果：
两组结果对比可以看出，DST更适合于较小的数据范围，而一般信息学竞赛中的范围多在左右，正适合于DST的使用。
注：本测试结果仅供参考，如果需要请用其他类型的数据测试。个人认为测试的最终结果会是所有平衡树在时间上都相差不多。
四、DST的优势
DST是一种非常优秀的数据结构，它支持普通BST的所有操作，而且与传统BST相比，DST具有更低的编程复杂度（仅比普通BST多一个maintain过程），也具有与传统BST不相上下的速度。本文中给出证明也是为了说明DST的高效并不是一个简单的巧合。另外，在维护一棵DST平衡时甚至可以不对子树进行维护，而这种做法对实践中时间效率的影响非常小，可以认为是安全的。这使得DST非常灵活易用，在时间紧迫的信息学竞赛中使用尤为合适。
五、DST与SBT
DST与SBT同属于利用子树大小（或者说size域）维护平衡的二叉搜索树，它们具有许多相似的性质，比如上文提到的 maintain 的时间复杂度。DST的删除过程也可以不用调用maintain 过程维护，这样同样可以保证的时间复杂度。作为一种新平衡树，SBT的意义在于给世界提供了一种平衡树新的思路：用子树大小维护平衡；而DST的意义则在于提醒我们：可能存在许多这样依赖于子树大小的平衡树，它们的代码很简单，时间效率却很高。BST的世界也许还有很多更好的算法等待我们去探索、挖掘。
参考
[1] 小魚兒 DST《讨论版》、《初步证明》、《正式版》
[2] 陈启峰 《Size Balanced Tree》
[3] 陈启峰 《Size Balanced Tree中文译版》，译者：BambooLeaf 竹子的叶子
[4] Wiki http://en.wikipedia.org/wiki/Avl_tree
[5] sqybi 《The Magic Splay》
附：
[1][2]的证明将在下面给出。但是由于这部分证明比较枯燥，大部分是简单的一次不等式的代换，没有特殊需要（比如怀疑我的证明是否正确）不必深究。证明会尽可能地详细，为了保持证明思路的连贯性，部分证明将使用分析法。
当插入，删除操作引起
………………………………………… ①
时，T(A)不满足平衡条件。
（1）这时如果S(C)和S(D)满足
………………………………………………… ②，
我们对T(A)进行一次简单旋转，使这棵子树从左图的结构变成右图的结构。
由于在旋转前T(B)符合平衡条件，我们可以得到
……………………………………………… ③，
而旋转对T(C)以及T(D)都没有影响，所以旋转后上式仍然成立。这时有很显然的
……… ④。
将①、②式以及恒等式（旋转前）联立消去S(B)和S(D)，我们可得到
于是将上式与②式相加并将恒等式（旋转后）代入可得
………………………………… ⑤。
从④⑤式我们可以看出旋转后的T(B)符合平衡条件。
然后将①、③式以及恒等式（旋转前）联立消去S(B)和S(C)，我们可以得到
在上面的证明中我们已经说明T(C)没有受到旋转的影响，于是T(C)是一棵DST，满足平衡条件。这样我们就证明了旋转后的DST至多有一棵子树不平衡，并且只能是右子树的左孩子比右孩子大的不平衡，这样也说明了文中maintain 的写法对于这种情况是成立的。
然后是旋转前后的深度和，对比旋转前后树的形态可以知道
说明这种情况符合文中的结论。
（2）这时如果S(C)和S(D)满足
…………………………………………………… ⑥，
那么我们对T(A)进行一次复杂旋转，得到旋转后的T(D)。
先证明整个T(D)符合平衡条件。
那么我们要证明旋转后
将旋转后恒等式以及代入以上两式可知原式等价于
………………………………… ⑦
………………………………… ⑧
由于我们已知旋转前
联立以上两式，得到
………………………………………… ⑨
把⑨式和相加可知⑦式成立是显然的。
然后是⑧式。因为⑨式成立，所以我们只需证明
即
又旋转前有
……………………………………⑩
所以只需证
即
而这个式子是显然成立的，因为旋转前有
这样我们就证明了整个子树符合平衡条件，而且文中的maintain过程对于这种情况也适用。
然后仍然是旋转前后的深度和。⑥式和⑨式可以告诉我们
同样的观察可以得到
其中的“1”表示结点A在旋转前后的深度变化。
这就证明了这种情况也符合文中的结论。
联系（1）中最后的结论，我们就完成了对maintain过程均摊复杂度的证明。下载本文
