关于 Splay
__ryp__
·
2024-12-04 21:10:21
·
算法·理论
整理了一些关于 Splay 的资料，一个简洁美丽而高效的数据结构。
Splay 是最简洁的平衡树之一，支持维护区间信息。相比线段树，其可以动态地删点、加点，更加灵活；相比分块，其复杂度是均摊对数，更加高效。
在形态变化时，Splay 并不通过维护一系列性质来保证树高，而是通过伸展保证均摊复杂度。这让它少了常见平衡树的繁杂分讨，但常数也要大不少。
形态及操作
Splay 首先是一棵二叉搜索树，由许多节点组成。我们在每个节点维护父亲的左右儿子指针，以及键值。如有需要，还可以维护它子树内的信息，如它的子树大小。维护子树大小，可以实现快速查询第 k 大或者某数排名。
Splay 的核心操作是伸展（splay）。伸展某个节点 x，意味着将 x 节点提升到根，同时更新所维护的子树信息。原来的根在伸展后成为某个普通内部节点。伸展操作的均摊复杂度是对数。
如果能够实现伸展操作，就可以方便地进行许多操作：
插入。插入与普通二叉树的插入相同，按照二叉树的遍历方法找到某个叶子节点，将新值插入到该叶子的儿子下。不同的是，在插入某个点后，为了保证复杂度正确，我们要将这个节点伸展到根。
删除。首先将这个节点伸展到根，然后将其与其儿子断开。这时原树分裂成两个子树，考虑合并它们。找到左子树的最大值，由二叉树的性质，这个数一定小于右子树的最小值。因此，我们将 y 伸展到根。这时 y 的右儿子一定空，于是将右子树拼到其右儿子上即可。
查找某个数。按照二叉树的查找方法，一直找到这个数，或者某个叶子。将最后找到的节点伸展到根。
查询排名。首先查找这个数，伸展到根。然后小于其的数数量就是现在根左子树的大小。如果待查询的值不存在，还要考虑根是否小于这个数。
查询第 k 大。和二叉树相同。从根节点开始遍历。如果当前节点 x 左子树的大小，也就是小于 x 的数字数量，大于等于 k，要找的节点在左子树；如果等于 k - 1，那么就是当前节点 x；否则，在右子树，并且 k 减去左子树加上当前点大小。
查询前驱。伸展到根，然后找左子树的最大值，也就是一直向右走。如果查询的值不存在，特判根是否小于待查值。
查询后继。与查询前驱同。
查询区间。设待查询区间为 [l, r]，我们将 l - 1 旋到根，r + 1 旋到根的右儿子，那么根的右儿子的左儿子，其上的信息就是 [l, r] 的信息。
伸展
旋转
现在，我们只需要有效地实现伸展操作，就可完成所需的一切操作。
考虑怎么将某个节点高度提升一。我们称这个操作为旋转。
考虑怎么将 2 提升到 4 的位置。
那样，4 该放到哪里？可以接到 2 的右儿子上。2 的右儿子放到哪里？放到 4 的左儿子上，因为 4 原来的左儿子是 2，现在已经空。其他子树不变。因此，变的只有 2 和 4。
单旋与双旋
伸展操作能不能直接一直向上旋转呢？可以，但复杂度错误。
为了改善复杂度，我们需要引入双旋。
双旋是指，在伸展过程中，如果出现 x 与 x 的父亲同向，不能简单地旋转两次 x，而是要先旋转其父亲，再旋转 x。
我们如果想要将 6 伸展到根，是不是需要双旋？答案是肯定的，因为 4 和 6 都是其父亲的右儿子，属于同向。如果是伸展 3，就不需要了。按照双旋的过程，我们先旋转 4，再旋转 6。也就是，先变成：
后旋转 6
光看上图，可能感觉双旋和单旋没有什么区别，但实际上在复杂度分析时，使用双旋可以保证某个性质，进而保证复杂度正确。
总之，我们已经知道了怎样以正确的复杂度将 x 伸展到根。有关 Splay 的基本操作，就介绍完毕了。
附一份常数和美观程度都不错的实现。
复杂度
势能分析简介
我们发现，Splay 的复杂度来源于两部分，一部分是遍历，另一部分是伸展。让最终遍历到节点马上被伸展到根，就可以把复杂度都算在伸展里，进而只需证明伸展的复杂度。
我们采用势能分析。势能分析是指，引入某个势能函数 \Phi(D)，描述某时数据结构的状态。
设每次操作的代价是 c_i，每次操作后数据结构为 D_i。要证 \sum c_i 有某上界。如果 \Phi(D_n) - \Phi(D_0) = O(F(n))，\Phi(D_n) - \Phi (D_0) + \sum c_i = \sum (c_i + \phi(D_i) - \phi(D_{i - 1})) = O(G(n))，显然 \sum c_i = O(F(n) + G(n))。
这样有什么好处？我们考虑，Splay 等数据结构复杂度分析的难处，在于我们只知道 c_i 的一个很松的上界，而不好直接分析 \sum c_i。实际上，某个大的 c_i 对数据结构的影响也是大的，会导致后续的操作 c_i 更小；换句话说，不会出现所有 c_i 都取到上界的情况。
引入势能函数后，每个很大的 c_i，可以用一个很小的 \Phi(D_i) - \Phi(D_{i-1}) 来平衡。因而可以更方便地放缩，并得到上界。
具体分析
我们设某个节点的势能函数为 \phi(x) = \log \lvert x\rvert（\log 均以二为底；\lvert x\rvert 表示 x 的子树大小），\Phi(D) = \sum \phi(x)。显然的，0\le \Phi(D) \lt n\log n，并且 \Phi(D_n) - \Phi(D_0) = O(n\log n)。我们要证明每次伸展操作的均摊复杂度是对数。
伸展的分解
根据上面对 Splay 的介绍，我们可以将伸展分为三种具体操作。设 x 为待伸展的节点，y 为 x 的父亲，z 为 y 的父亲。
zig，即一次单旋，在 y 为根时候发生。直接旋转 x，其深度减少一。发现这种旋转最多发生一次。
zig-zig，即一次双旋，在 y 和 x 同向时发生。先旋转 y，后旋转 x。x 深度减少二。
zig-zag，即两次对 x 的单选，在 x 和 y 不同向时发生。x 深度减少二。
伸展的过程是数次 zig-zig 与 zig-zag 的组合，加上可能存在的一次 zig。
zig 的分析
旋转的复杂度为 O(1)，势能的变化量为
\phi(x') + \phi(y') - \phi(x) - \phi(y) = \phi(y') - \phi(x) \le \phi(x') - \phi(x)
因此摊还代价是 O(1) + \phi (x') - \phi (x)。
zig-zig 的分析
摊还代价是
\begin{aligned}
& c \\
=& 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \\
=& 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\
\end{aligned}
考虑怎么把 1 去掉，因为如果引入 1，就会导致最终复杂度与旋转次数有关。
有：
\begin{aligned}
2\phi(x') - \phi(x) - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert x\rvert\lvert z'\rvert}) \ge 1
\end{aligned}
这是因为 \lvert x'\rvert \ge \lvert x\rvert+\lvert z'\rvert。注意到不双旋时，此不等式不满足。这也是为什么双旋才能保证复杂度。
用这个不等式代换常数 1，得到
\begin{aligned}
& c \\
\le& 2\phi(x') - \phi(x) - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\
\le& 2\phi(x') - 2\phi(x) + \phi(y') - \phi(y) \\
\le& 3\phi(x') - 3\phi(x) \\
=& O(\phi(x') - \phi(x))
\end{aligned}
成功将常数消去，同时和前面的 \phi(x') - \phi(x) 保持了一致。
zig-zag 的分析
类似的，我们有不等式：2\phi(x') - \phi(y') - \phi(z') = \log (\dfrac{\lvert x'\rvert^2}{\lvert y'\rvert\lvert z'\rvert})\ge 1
\begin{aligned}
& c \\
&= 1 + \phi(x') + \phi(y') + \phi(z') - \phi(x) - \phi(y) - \phi(z) \\
&= 1 + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\
&\le 2\phi(x') - \phi(y') - \phi(z') + \phi(y') + \phi(z') - \phi(x) - \phi(y) \\
&\le 2\phi(x') - 2\phi(x) - \phi(y) \\
&\le 2\phi(x') - 2\phi(x) \\
&= O(\phi(x') - \phi(x))
\end{aligned}
综合
分析得到，zig 的摊还代价为 O(1 + \phi(x') - \phi(x))，而这种旋转最多一次；其他的两种旋转，摊还代价都是 O(\phi(x') - \phi(x))。这样，伸展的总代价就是 O(\log \lvert x'\rvert - \log \lvert x\rvert + 1) = O(\log n)。我们成功证明了伸展的复杂度是摊还对数，由此知道 Splay 的复杂度是正确的。