Splay 树

2267 字约 8 分钟

2025-02-01

在本文中，我将介绍 Splay 树，一种与 AVL 树类似但有所不同的自适应二叉查找树。与 AVL 树通过严格平衡因子维护树的高度不同，Splay 树通过伸展操作将最近访问的节点移动到根节点，从而自适应地优化频繁访问的数据。这种灵活性使得 Splay 树在缓存、数据压缩等场景中表现优异。本文将详细讲解 Splay 树的核心原理、操作实现及其与 AVL 树的异同，帮助读者深入理解这一自平衡树结构的独特优势。

什么是 Splay 树？

Splay 树，又名伸展树，是一种自平衡二叉搜索树。它通过伸展（Splay）操作不断将某个节点旋转到根节点的位置，维持整体的平衡，能在均摊时间 $O(\log N)$ 内完成插入、删除、查找操作。

Splay 树由 Daniel Sleator 和 Robert Tarjan 于 1985 年发明。没错，就是你知道的那个 Tarjan。

伸展——Splay 树的核心

伸展（Splay）是 Splay 树这一数据结构的核心，正如树旋转之于 AVL 树。

何为伸展？

假设要对一个搜索树进行一系列的查找操作，被查找频率高的节点就应当经常位于靠近树根的位置。于是干脆采用一种简单的方法，在每次查找之后调整树的结构，将要查找的节点搬到离树根较近的位置。

基于这样的朴素思想，Splay 树应运而生。在每次节点操作中，它会沿着目标节点与树根之间的路径，通过树旋转将其逐渐搬运到树根处。这个过程被形象地取名为伸展。

单旋与双旋

在 Splay 树中，我们把一次普通的树旋转成为单旋。每次伸展操作我们需要将给定节点通过旋转移动根节点的位置。显然，我们可以通过连续的单旋来轻松实现。但这样可能会导致更高的时间复杂度，并且可能无法有效控制树的高度。因此，Splay 树引入了一种特有的双旋操作。

我们将要伸展的目标节点称为 X，记其父节点为 P，祖父结点为 G，并假定它们存在（否则无需进行双旋，最多进行一次单旋）。

为了表述清晰和便于理解，对于单次旋转操作，我们不再区分左右旋转，而是按照节点 X 相对于父节点 P 的位置来判断旋转的方向。

zig-zig

当 X 与 P 同向，即 X 和 P 都是左孩子或都是右孩子时，我们先旋转 P，后旋转 X。这种情况称为 zig-zig。

zig-zag

当 X 与 P 反向，即 X 和 P 分别是不同方向的孩子时，我们连续旋转 X 两次。这种情况称为 zig-zag。

通常，一次伸展操作由若干次双旋与可能的一次单旋构成，其中单旋操作仅发生在最后一次旋转时 P 是根节点，无法满足双旋条件的情况下。

Splay 树的基本操作

查找

Splay 树的查找操作与普通二叉搜索树基本无异，不同之处在与找到目标节点后要将其伸展至根节点处。

插入

Splay 树的插入操作也和二叉搜索树类似，但是在插入节点或者发现节点已经存在后要伸展该节点。

删除

删除操作的实现较为复杂，大致可分为以下几步：

找到要删除的节点，伸展之。
删除伸展后的根节点，切割出左右子树。
伸展左子树的最右节点（或右子树的最左节点）。
此时左子树的根节点没有右儿子，直接将右子树作为左子树的右儿子。

时间复杂度分析

我们用势能法来证明 Splay 树拥有 $O(\log N)$ 的均摊时间复杂度。

势能函数

使用 $T$ 来描述完整的一棵树，用小写字母 $x$ 、 $y$ 、 $z$ 等表示树上的节点。记 $|T|$ 为 Splay 树上的节点数目， $|x|$ 为以 $x$ 为根的子树的节点数目（包括 $x$ ）。

定义如下的势能函数：

\phi (x) = \log |x|

\Phi (T) = \sum_{x \in T} \phi (x)

其中 $\Phi(T)$ 为整棵树的势能函数， $\phi(x)$ 为节点 $x$ 对势能的贡献。

初始时刻， $\Phi (T) = 0$ 。对于任意时刻，都有 $\Phi (T) \ge 0$ 。因此势能函数合法。

单旋的摊还代价

单旋中发生势能变化的只有目标节点 $x$ 及其父节点 $y$ ，因此

\Delta \Phi (T) = \phi (x') + \phi (y') - \phi (x) - \phi (y)

由单旋的性质可知， $\phi (y') \lt \phi (x') = \phi (y)$ ，因此

\Delta \Phi (T) \lt \phi (x') - \phi (x) = O(\phi (x') - \phi (x))

则单旋操作的摊还代价为 $O(1 + \phi (x') - \phi (x))$ ，其中 $O(1)$ 表示旋转本身的复杂度。

由于一次伸展中只有至多一次单旋， $O(1)$ 不会对分析产生影响，我们可以只关心其中的 $O(\phi (x') - \phi (x))$ 。

zig-zig 的摊还代价

zig-zig 中发生势能变化的有操作节点 $x$ ，父节点 $y$ ，及其祖父节点 $z$ ，因此

\Delta \Phi (T) = \phi (x') + \phi (y') + \phi (z') - \phi (x) - \phi (y) - \phi (z)

同样地，有 $\phi (y') \lt \phi (x') = \phi (z)$ ， $\phi (x) \lt \phi (y)$ ，因此

\Delta \Phi (T) \le \phi (x') + \phi (z') - 2 \phi (x)

这里我们需要用到一个小结论： $\phi (x) + \phi (z') - 2 \phi(x') \le - 1$ 。

证明

设 $|x| = a$ ， $|z'| = b$ ，则 $|x'| \ge a + b$ （结合 zig-zig 的过程易得）。

\begin{aligned} \phi (x) + \phi (z') - 2 \phi (x') &= \log |x| + \log |z'| - 2\log |x'| \\ &= \log \left(\frac{|x||z'|}{|x'|^2}\right) \\ &\le \log \left(\frac{a b}{(a+b)^2}\right) \\ &\le \log \left(\frac{a b}{2 a b}\right) \\ &= -1 \end{aligned}

因此， $-(\phi (x) + \phi (z') - 2 \phi(x') + 1)$ 是一个非负数。将上面的式子加上这个非负数，可得

\begin{aligned} \Delta \Phi (T) &\le \phi (x') + \phi (z') - 2 \phi (x) \\ &\le \phi (x') + \phi (z') - 2 \phi (x) - (\phi (x) + \phi (z') - 2 \phi(x') + 1) \\ &= 3 \phi (x') - 3 \phi (x) - 1 \end{aligned}

则 zig-zig 的摊还代价为 $O(1) + O(\phi (x') - \phi (x) - 1)$ 。通过增大我们所加的非负数以及势的单位，可以抵消 $O(1)$ 中的常数。故摊还代价可记为 $O(\phi (x') - \phi (x))$ 。

zig-zag 的摊还代价

其分析过程与 zig-zig 类似，结论不变。

伸展操作的摊还代价

除了最后一次旋转可能增加 $O(1)$ 的代价外，其他旋转操作的摊还代价均为 $O(\phi (x') - \phi (x))$ 。

假设一共执行了 $n$ 次旋转操作， $x_i$ 表示第 $i$ 次旋转后 $x$ 的状态，则伸展操作的总摊还代价为

O(1 + \sum_{i = 1}^{n} (\phi(x_{i}) - \phi (x_{i-1}))) = O(1 + \phi (x_n) - \phi (x_0))

此时 $x_n$ 是树根，故 $\phi (x_n) = \log |T|$ 。

因此，一次伸展操作的摊还代价为 $O(\log |T|)$ 。

与 AVL 树的比较

相比于 AVL 树，Splay 树不需要存储额外的一些节点信息，如树高，对空间的利用率更高。另外，尽管 Splay 树看似需要经常性调整自身结构，但却能保持对数级的均摊时间复杂度，且它没有 AVL 树那样严格的平衡条件，因此在实际应用中通常表现出更优良的性能。

事实上，Splay 树是 AVL 树的自适应形式。

不过，由于 Splay 树的每个操作，哪怕是“只读”的访问，也会改变树的结构。这给在多线程环境下使用 Splay 树带来了挑战。

扩展进阶：自顶向下的操作

Splay 树：均摊时间下的平衡二叉搜索树中给出了一种自顶向下的 Splay 树实现。与本文中所给出的实现方法——先找到节点，然后进行伸展——不同，这种自顶向下的实现在向下查找的过程中，一边查找，一边调整树的结构，不需要进行回溯。

这样实现有两个好处：

我们不需要在节点中维护额外的信息（父节点），代码实现起来更简洁。
在实际应用中，这种方法的运行效率会更好。

参考资料

版权所有

版权归属：SuniRein

本文链接：/article/mdyrqsgl/

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)