• 引言
• Treaps
• AVL trees
• splay trees
• Red-black trees
• B-trees
• skiplist
• summary

引言

众所周知，二分搜索树的搜索时间取决于树的高度，但一个具有n个节点的二叉树，高度既可能是令人满意的\(\lg n\)， 也有可能是高度倾斜的 \(n\)，此时二叉树退化为链表，搜索速度捉急。那么一个自然的想法即是改造原来二叉树的结构和操作，从而使得这棵树不管在哪种意义下（可能是最差情形的上界，可能是期望，可能是极大概率，也可能是平摊分析来看），其分枝比较平衡，树高保持在 \(\lg n\) 的数量级。

下面我们将看到几种实现以上目标的树的结构，我将不去关注算法的细节，而是描述这些结构的基本想法，和到底在什么意义上实现了树的平衡。此外，对于查询，插入和删除这些操作，究竟在什么程度和意义上上是 \(\lg n\) 进行更细致的说明，以使这几种树结构的优缺点更加明了。如果本来对这些树的结构和实现不太了解，可能本文阅读起来会有些困难。

Treaps

第一个最简单的模型叫做树堆，很明显是结合了树和堆的特点。不过我们还是先从最简单的二叉树出发，看一下如何改造静态的二叉树，使其平衡。这里的静态的意思是提前给定二叉树的所有节点值，之后我只关心二叉树构建和查询这两者的实现。而对于和动态有关的插入删除不予考虑。考虑提前给定的一组节点值，事实上，只需把其随机打乱，然后再按照正常的二叉树构建方法（从第一个元素开始各自执行二叉树的插入算法）构建即可。通过一些证明（需要用到 Jessen 不等式和树高期望的递推），可以得到 \(E(h)=O(\lg n)\)，事实上更严格的证明可以得出 \(E(h)\approx 2.9882\lg n\)。因此这一随机化算法得出的二叉树的高度从期望的意义上满足了我们的要求。当然这一改造虽然简单无痛，但不是动态的。当我们再向这棵树里插值时，随机性就消失了，除非你愿意包括进这个新元素，全部随机混排，重新建树，当然这样插入的时间也会从 \(\lg n\) 变为 \(n\lg n\)，这当然是不可接受的。而不全部重排，随机就没有意义了，因为之后动态插入的元素，是用户决定的，每次插入一个，online 的特性使得树没有机会随机这些元素。一旦用户是按照排序好的元素依次插入，很快这棵树就重新变得倾斜。

于是动态解决的方案就是树堆了。这一方案的亮点就是，怎么动态的解决随机排序的问题。答案是，每插入一个元素，就随机赋值一个数，我们可以叫这个数优先级。这样每个节点就有两个信息，原来的值和插入时被随机赋予的优先级数字。对于值来看，结构仍是一个二叉树，而对于优先级来看，结构则是一个堆。当插入新值时，先加入随机的优先级信息，然后按照普通的二叉树算法插入到某个尾巴上，再让该节点按堆的算法一样“上浮”，由于这些上浮算法利用的都是一些可以保持二叉树性质的旋转操作，最后我们就得到了一个每节点两个值，一个满足树一个满足堆的树堆。删除算法也类似，对于这些操作，我们都可以先按照树操作来做，最后用堆的上浮下沉对树的结构进行一些旋转调整，这一过程既不破坏二叉树的性质又满足了堆的性质。因此其插入删除的节点上浮下沉操作时，恰好树与堆的要求相一致，所以实现起来非常简单（尤其和下面某些神一样 case by case 的数据结构比），而操作的复杂度的期望都是树高，也即 \(\lg n\)。当然如果足够倒霉，还是无法排除树超级偏的可能性。

和下面一些更精致的结构相比，树堆实现起来这么简单必定有着很多 tradeoff。首先就是随机化算法的特性，只能从期望上保证树平衡，无法绝对排除树高是\(\Theta(n)\)的情形，这也将导致各类操作的复杂度都跟着增加。其次就是树结构的再调整，可以继续区分旋转操作和赋值操作，在树堆中旋转操作的复杂度就是 \(\lg n\) 和下面一些以赋值操作为主，只有常数数量级的旋转操作的算法相比还是会慢很多。比起赋值，旋转除了操作更慢以外，还会直接锁住正经过这些节点附近的查询。相反赋值操作，改变每个节点的额外属性，完全不影响同时的其它基于二叉树的查询操作。因此从以上两方面看，每个操作所需的旋转越少越好，树堆在这方面是比较差的。

AVL trees

AVL 树的定义是二叉树中任意节点的左子树和右子树的高度差不超过1。根据该定义，很明显整个 AVL 树保证了平衡性，树高是 \(\lg n\)。因此每个节点都多维护一个高度数据，代表以该节点为根的树的高度。这样一棵树基于二叉树，显然查找，遍历等操作一模一样。对于插入和删除操作，分为两个部分，首先按照普通的二叉树的算法来插入和删除节点，然后沿对应节点上溯进行平衡检查。若发现破坏AVL树定义的区域，进行rebalancing的操作。所谓 rebalancing 就是基于初次出现不平衡为止节点的形态，分类进行的双旋转或单旋转。这类旋转可以保持二叉树特性的同时，调平了两侧树高度差。在插入操作时，至多一次旋转（将双旋转视为一次）就可以调平树。但删除元素时则至多需要树高量级的旋转，也即\(\log n\)。其删除时的调平比较复杂，可以参考这里。因此 AVL 树仍有一部分操作需要多于常数次的旋转来恢复，这也是 AVL 树相比红黑树的一个劣势。但至少AVL树是个确定性算法，我们可以保证最差情形的 \(O(\lg n)\) 复杂度。

splay trees

严格的说 splay tree 不是典型意义的平衡树，因此放在这里更多的是为了比较的完整。splay tree 就是一棵普通的二叉树，区别是每次一个节点得到访问，就会把该节点通过一系列保持二叉树性质的旋转，转到根节点处。这样下次再访问该节点时会变得更快。这种操作被称为伸展。这对于有一定局域性的访问序列有着明显的查询加速作用。这种将查询节点旋转上移到根节点的操作，同时兼具了一定使树倾向于平衡的附加buff。即使查找失败，失败之前的那个节点也会被伸展到根节点上。插入操作时，先按照普通二叉树的算法插入成叶子，在伸展到树根。甚至删除操作，也要把待删除节点伸展到树根再删除（删除根节点后，将左树的最大值节点伸展上来作为新的根节点）。这样一棵树，由于没有保证树的平衡，最差情形所需的操作时间都是\(\Theta(n)\)。

不过我们也可以某种程度上定量刻画伸展操作对树的平衡的贡献，通过合适的势函数（所有节点包含子树大小的对数和），我们可以证明在最坏情形，平摊分析的意义下，以上操作的平摊时间复杂度均为\(O(\lg n)\)，具体证明可以参考这里。当然即使 splay tree 平摊时间是对数复杂度，其每次操作所需要的大量旋转，还必须旋转到根为止，这使得伸展树的旋转次数比树堆还多，实践上是较慢的。但由于伸展树具有刚被访问过的节点会接近树根的额外特性，可能在部分场景下会有特定使用需求。

Red-black trees

红黑树可以说是各方面比较均衡，在实践中主流被采用的平衡二叉树实现了。当然其缺点也很明显，就是实现起来比较复杂，边边角角的分类处理太多。红黑树每个节点除了值之外，需要额外维护一个bit的颜色数据（红或者黑）。红黑树将原始二叉树叶子最后的空指针们称为叶子，以方便统一处理。红黑树的定义包括：根和叶子黑色，红色的父亲黑色，从某个节点到不同子叶子经过的黑色节点一样多。事实上我们将会在下节看到，通过将每个红色节点与其父节点合并，我们就得到了一棵2-3-4树，这是B树的一种特例。

红黑树考虑到定义，很明显最长的树枝也超不过最短的2倍，树高最差情形处于\(\lg n\)的数量级。查询操作和普通的二叉树一致。而插入和删除操作，很可能破坏掉红黑树的定义，因此需要通过各种花式旋转和重染色来变回一棵红黑树。虽然这里的恢复操作相当繁琐，但值得欣慰的是，其中的大部分操作是重新染色，这种赋值需要的时间常数较小，而且重染色完全不影响接下来的查询同步进行。而开销较大的旋转操作，插入和删除算法都可以保证做到\(O(1)\) 次，这也正是红黑树的实现比前边几种都复杂很多，却最为广泛的实用的原因。

B-trees

B 树虽然是平衡树，但不属于二叉树。一棵m阶的B树每个内部节点都有\(ceil [m/2]\)到m个孩子。而节点将存储子节点数目减1的key，用来分流。B 树由于子节点变多树高会进一步降低到\(O(\log_m n)\)的量级，极大减少了查询次数。这种次数的减少，虽然是和二叉树在同一数量级，内存中的比较可能区别不明显，但如果是硬盘 IO，B 树的优势完全是压倒性的。这也是关系型数据库选择B树（或其变形）作为底层实现的原因。其中 \(m=4\) 的B树就是2-3-4树，这对应了恰好每个节点都会有2，3或者4个子节点，这一结构实际和上文的红黑树完全等价。

B 树的插入操作比较简单，由于每个节点的关键字数目的限制，插入之后超限将会引起对应节点的分裂和中间关键字的上升，递归该过程，就会重新恢复一棵符合定义的B树。删除操作也不复杂，删除元素之后（如不是叶子节点还有一个提升前序的过程），如果对应节点元素数跌出下限，那么要么向兄弟节点借元素，要么直接和兄弟节点合并（取决于兄弟节点元素的多少），以此递推即可。

B 树还有一些变形，包括将非叶子节点的关键字都处理为索引，从而将所有具体信息的指针都存储在叶子一层的 \(B^+\) 树，和增加兄弟节点指针的\(B^*\) 树等，这里就不再赘述。

skiplist

跳跃表和树没什么关系，但其做的事情也是动态集合的查询，实现的功能和复杂度都大致相同，因此也简要的包括在这里作为对比。跳跃表由元素渐渐变少的一堆链表构成。由于其插入算法以\(1/2\)的概率提升节点，可以在此基础上得出期望和较大概率的意义下，跳跃表高度和操作的时间复杂度数量级也都在 \(\lg n\)，和一颗平衡二叉树对外的行为基本一致。但是跳表的实现非常简单，同时插入删除操作几乎对后续同时进行的其它查询没什么影响，简洁优雅强大还快的飞起，这一数据结构已经变的越来越流行。很多非关系型的数据库选择了跳跃表而非红黑树来实现相关的数据结构。这么强自然有其 tradeoff，每个元素有\(1/2\)的概率上升，因此每个元素从期望的意义上都会被存两次。虽然空间复杂度的数量级和平衡树们没什么区别，但空间复杂度的常数应该要比优化过的平衡树大一些。

summary

最后，奉上关于不同平衡树性能和复杂度比较的表格一张，留给太长不看的读者们。其中我把 B 树的合并分裂等会锁住后续查询的结构变动也记做了旋转。

EOF