Splay

Splay

局部性：刚刚被访问的数据可能很快地再次被访问 能否利用局部性加速？ 对于 BST，能否将刚刚访问过的节点调整到根？可以，通过旋转实现 调整后如何保证复杂度？

若直接采用直接旋转的方法将访问节点调整到根，在最坏情况下（单链），均摊复杂度可以达到 $\Omega (n)$，且可以一直出现。

Splay 操作

修改为每次旋转时上溯两层，从祖父开始进行旋转：

• 双旋：若 $v$ 和 $p$ 相对位置与 $p$ 和 $g$ 相对位置不同，将 $v$ 调整为根只有一种方法，即将 $g$ 和 $p$ 分别作为 $v$ 的左右子树，此时与逐层旋转没有区别。
• 单旋：若 $v$ 和 $p$ 相对位置与 $p$ 和 $g$ 相对位置相同，先对 $g$ 进行旋转，再对 $p$ 进行旋转。此时 $p$ 变为 $g$ 的父亲，并且直观上子树倾斜方向与原本相反。如此一来，直观上讲，在将 $v$ 调整为根时，路径上的节点会调整相对位置，使得调整后的高度降低（相比单层上溯，有些节点从路径上转移到了另一边的子树上）
• 若 $v$ 没有祖父，则直接旋转到根，只会出现一次 可以证明 Splay 操作的均摊复杂度为 $O(\log n)$

势能

$$\Phi (S)=\sum _{v\in S}\log (size(v))=\sum _{v\in S}\log V$$

直观上讲，越平衡的树，势能越小

• 单链时最大，$\Phi (S)=O(n\log n)$
• 满树时最小，$\Phi (S)=O(n)$ 考虑连续的 $m$ 次操作，$m\gg n$ 记 $A^{(k)}=T^{(k)}+\Delta {\Phi }^{(k)}$，则

$$A-O(n\log n)\le T=A-\Delta \Phi \le A+$$

若能证明 $A=O(m\log n)$，则必有 $T=O(m\log n)$ $A^{(k)}$ 是 $v$ 的若干次 Splay 操作的累积，分三种情况，可以证明 $A_i^{(k)}<3(ran{k}_i(v)-ran{k}_{i-1}(v))$，则 $A^{(k)}=O(\log n)$

实现

• 查找：将目标节点或最终搜索到的节点 splay 到根
• 插入：插入前总是会经过查找，此时 $e$ 的邻近者 _p 被转移到根，插入 $e$ 作为根后再将 _p 和它的一颗子树调整为 $e$ 的子树即可
• 删除：先进行查找，将 $e$ 的邻近者转移到根，若查找失败，直接退出，若查找成功，删除 $e$，在右子树中再次查找 $e$，此时会将右子树中最小的节点 splay 到根，将左子树接入即可

总结

• 无需记录高度和平衡因子，编程实现简单
• 均摊复杂度为 $O(\log n)$
• 局部性强时效率更高，假设多次访问 $k$ 个数据，连续的 $m$ 次查找只需 $O(m\log k+n\log n)$ 时间，均摊每次 $O(\log k)$
• 若反复顺序地访问一个子集，均摊成本仅为常数
• 可能出现单次最坏情况，效率降为 $O(n)$，不适用于瞬时效率敏感的场合