Treap 与 Splay：随机平衡树与伸展树入门

在 BST、AVL 和红黑树之后，平衡查找树这条线其实还远没有结束。数据结构的有趣之处就在于：同样都是为了避免 BST 退化、维持对数级操作效率，人们并没有只发明一种平衡方法，而是不断尝试不同的设计哲学。Treap 和 Splay，就是其中非常有代表性的两类。

它们之所以值得学，不是因为日常业务里一定会手写，而是因为它们让你真正看见：

平衡可以通过严格规则维护；
也可以通过随机化来“概率保证”；
还可以通过访问自适应，让“常用的东西越来越靠近根”。

这三种路数，分别代表了完全不同的结构思想。所以 Treap 和 Splay 很适合作为“平衡树视野拓展”来理解。

一、为什么平衡树还会继续发展出新变体

因为不同平衡策略的目标侧重并不完全一样。

例如：

AVL 更追求严格平衡；
红黑树更追求工程折中；
Treap 借助随机化降低维护复杂度；
Splay 则强调访问局部性和自适应。

也就是说，“平衡树”不是一个固定答案，而是一类围绕查找效率、更新代价、实现复杂度做权衡的设计家族。

二、什么是 Treap

Treap 这个名字，通常来自 Tree + Heap。它的核心思想非常有意思：

同时把一棵树维护成 BST 和堆。

具体来说，每个节点通常会有两类关键属性：

一个是用于 BST 比较的键值 key；
一个是随机生成的优先级 priority。

然后要求整棵树同时满足：

按 key 看，它是一棵 BST；
按 priority 看，它又是一棵堆。

这就是 Treap 最核心的双重约束。

三、Treap 为什么能保持平均平衡

因为优先级通常是随机生成的。

随机优先级带来的效果是：

节点在树中的形状不再只由插入顺序决定；
整棵树的形状在概率意义上更像一棵随机平衡树；
于是树高通常能保持在对数级的期望范围。

所以 Treap 的平衡不是像 AVL 那样“硬约束出来”的，而是：

用随机化让最坏退化情况变得极不容易发生。

四、Treap 为什么实现上常常比较直观

因为它通常围绕旋转做局部修复：

先按 BST 的方式插入节点；
如果插入后破坏了堆序，就通过旋转把节点往上提；
删除时也可以通过旋转把目标节点下推后再删除。

这让 Treap 看起来像是：

BST 提供顺序性；
堆序和随机优先级提供平均平衡性。

所以 Treap 很适合帮助理解“随机化也可以是一种平衡维护手段”。

五、什么是 Splay

Splay，通常翻译成伸展树。它的核心思想更特别：

每次访问一个节点后，都通过一系列旋转把它伸展到根附近，甚至直接拉到根。

这听起来很激进，但它背后的直觉非常强：

最近访问过的节点，将来往往还会再访问；
经常访问的节点，应该逐渐变得更容易访问；
与其维持严格形状，不如让结构顺着访问模式自适应调整。

所以 Splay 不是追求“任意时刻都平衡”，而是追求“在访问序列整体上保持较好效率”。

六、Splay 的旋转有什么特点

Splay 旋转通常分为几类典型操作，例如：

Zig；
Zig-Zig；
Zig-Zag。

这些名字本质上描述的是：

当前节点和父节点、祖父节点之间的相对位置关系；
然后通过单旋或双旋把目标节点往上提。

虽然具体细节一开始看起来容易绕，但更值得先抓住的是它背后的目标：

不断把刚访问的节点拉高，让它下次更容易被访问到。

七、Splay 为什么说是“自适应”结构

因为它的形状会随着访问模式变化而变化。

例如：

某个节点最近访问得特别频繁；
它就会被不断伸展到靠近根的位置；
于是后续再访问它时，代价会变低。

这说明 Splay 并不试图让所有节点都公平地处在差不多深度，而是更偏向：

让热点数据更近；
让结构自己适应使用习惯。

这和传统严格平衡树的哲学明显不同。

八、Treap 和 Splay 最核心的差别是什么

1. Treap

随机优先级决定平衡；
重点在“概率上的平均平衡”；
查找路径主要由键值结构决定。

2. Splay

不靠随机数；
每次访问都主动调整结构；
重点在“对访问模式的自适应优化”。

所以：

Treap 更像“随机化平衡 BST”；
Splay 更像“会根据使用习惯自我重排的 BST”。

九、Treap / Splay 在什么场景下有启发意义

即使平时不常手写，它们也非常值得学，因为它们代表了两种非常重要的思想：

1. 随机化可以简化复杂平衡维护

这在 Treap 里体现得非常明显。

2. 数据结构可以根据访问行为自适应重组

这在 Splay 里体现得非常明显。

这两种思想，放到更广义的软件系统里也很有启发。例如：

热数据缓存靠前；
热路径优先优化；
用概率方法避免最坏结构。

十、学习 Treap 和 Splay 时最容易踩的坑

1. 把它们当成红黑树 / AVL 的“冷门替代品”

其实更重要的是理解它们代表的不同平衡哲学。

2. 只记旋转步骤，不理解为什么要旋转

旋转的目标并不是炫技，而是维持双重性质或把热点节点提上来。

3. 误以为 Splay 每次都保证严格平衡

它并不追求严格静态平衡，而是追求均摊效率和访问自适应。

4. 误以为 Treap 的随机化只是“碰运气”

它背后是有严密期望复杂度支撑的。

总结

Treap 与 Splay 的价值，不只是因为它们是平衡树家族中的两个成员，而是因为它们把“如何保持查找树高效”这件事，展示成了两条完全不同的思想路线。真正值得先建立起来的，是这些核心认识：

Treap 用 BST 性质维护有序性，用随机优先级维护期望平衡；
Splay 不追求严格静态平衡，而是通过访问后伸展让结构自适应热点；
它们和 AVL / 红黑树相比，体现了不同的平衡哲学和工程取舍；
随机化和自适应访问，都是平衡树设计中非常重要的思路；
真正学会这部分，不是记住几个旋转名字，而是理解“平衡不止一种定义，效率也不止一种保证方式”。

把这一篇理解透之后，后面再去看外部存储结构、并发结构甚至缓存设计时，你会更容易看到：很多系统优化问题，本质上都在回答一个类似的问题，那就是“如何让最常见的访问路径更快”。

参考资源：