二叉搜索树（BST）是很实用的一种数据结构，通常用于实现集合的维护和查询功能。
这里就讨论几种常见的BST，并对它们在实际情况中的性能表现进行测试。
一颗BST是指一颗空树或满足一下性质的二叉树：
- 如果根节点的左儿子不为空，则它的键值小于根节点的键值；
- 如果根节点右儿子不为空，则它的键值大于根节点的键值；
- 根节点的左右子树都是BST。
下面给出BST的一些基本操作的实现。
这里使用$size$记录以该节点为根的子树大小；使用$count$记录维护的集合中有多少个元素和它的键值相等；$T$表示键值的数据类型，要求它能进行大小比较；$nil$是为了方便自己定义的逻辑空节点。
上面的代码中，除了删除操作以外都很好理解。删除操作的思路是如果x没有子树就直接删除它，否则找一个别的节点来代替x。
设树高为$h$，那么BST的基本操作均可在$\mathcal{O}\left(h\right)$的时间内完成。
虽然上面有大量的代码，但在应用中可以根据实际情况实现需要的功能，不必全部都有。
虽然BST的效率看上去不错，但是实际上它却极易退化成一条链，使得效率变得很低。
但是BST的形态是由插入删除的操作序列决定的，这往往是不受控制的。所以必须通过别的方法改变BST的形态。
一个通用的方法是旋转，它可以在保证BST的性质不受破坏的前提下改变它的形态。
旋转分为两种：左旋和右旋。也可以把它们理解为逆时针旋转和顺时针旋转。
下面给出代码。
有许多平衡BST利用旋转来保证其复杂度。
在平衡BST中，首先介绍树堆（Treap）。它的思想是随机化，对每个节点另外记录一个优先级，这个优先级是在节点构造时随机生成的。Treap除了要保证BST的性质外，还要使优先级满足二叉堆（这里假设是小根堆）的性质。这样做虽然不能使所有形态的可能性平均分布，但比一般的BST要好很多（期望$\mathcal{O}\left(\log_2 n\right)$），而且代码也十分简单。
插入操作和BST一样，只是插入完以后如果破坏了堆性质要把新节点往上旋转知道满足性质。
对于删除操作，如果节点左右儿子中有空节点，那就和BST一样用儿子来代替就行了。否则要把节点不断向两个子节点中较小的那个旋转，直到出现有空子节点的情况。
下面给出代码。
接下来是伸展树（Splay），它的代码也并不复杂，而且可以支持其他的平衡BST没有的功能——序列的分裂与合并，这在处理序列维护问题时非常有用。
Splay比BST要多一个操作：伸展操作。它的作用是通过旋转把一个节点伸展到根。
插入时只须把新插入的节点伸展到根，删除时则把要删除的节点伸展到根再删除。
这样感觉会很慢的样子，然而期望复杂度还是$\mathcal{O}\left(\log_2 n\right)$的。。
这里只给出伸展操作的代码。
注意这里并不是一次一次地旋转，而是每一次循环都旋转两次，这被称为双旋。考虑如果Splay变成了一条链，那么如果去伸展它最底层的那个节点，那么如果单旋伸展完后还是一条链，而双旋则不会。
现在考虑序列维护的问题。把序列中每个元素的下标当作键值，假设把名次为k的元素伸展到根，那么以序列的第k个元素为分界线，根的左儿子是前半部分序列，右儿子是后半部分。利用这样的操作可以完成绝大多数的序列维护。
最后提一下红黑树，这个东西其实并不是很有用。代码比前两种平衡BST要复杂得多，效率没有明显改进（它是保证$\mathcal{O}\left(\log_2 n\right)$，前两者是期望），功能也没有Splay多。唯一用处似乎就是装B。
不过，红黑树的统计性能要比其他平衡BST好，所以C++ STL中的set等集合类是使用它来实现的。（什么是统计性能呢？我也不知道，网上是这么说的。。。）
这里就不给出实现方法和代码了，想了解的话自行看《算法导论》去，里面讲得很详细，还有复杂度证明。
现在讲了4种BST了，但是它们的效率到底怎么样呢，就要测试一下才知道了。
测试机配置：AMD速龙860K 四核 3.7GHz 8G内存
测试环境：Windows 10 企业版 Build 10586 x64
测试对象：实现Tyvj1728中所有要求的4种BST（C++，指针实现，加读入优化）
测试数据：随机构造50个测试点，每个测试点$10^6$次操作，数据格式同Tyvj1728。
测试工具：CCR Plus
| 总用时 | 代码长度 | |
| BST | 133.12s | 4793B |
| Treap | 140.88s | 5482B |
| Splay | 144.29s | 5992B |
| 红黑树 | 132.89s | 7678B |
最终结果中，红黑树因其复杂度保证，速度最快。Treap和Splay稍稍落后，同时因其复杂度是期望的，所以在测试时不同测试点间用时浮动较大。但这些都没什么关系，在正常使用中基本感觉不出来，这里是因为操作次数非常多才会有明显的差异。至于BST，因为是随机数据，而且不用像另外3个一样进行额外的操作，所以用时较少，但实际中它的复杂度极易被卡到$\mathcal{O}\left(n^2\right)$，不推荐使用。
评论 (0)
