伸展树

伸展操作 ​

先按普通二叉搜索树公理库二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。搜索目标节点或最后访问节点，再重复旋转到根：父为根时做一次 zig；节点与父同为左孩子或同为右孩子时做 zig-zig，先转祖父再转父；方向相反时做 zig-zag，两次围绕节点旋转。split$(x)$ 先伸展 $x$，再断开一侧；join$(L,R)$ 伸展 $L$ 的最大键后接上 $R$。

Access lemma ​

令 $s(v)$ 为子树大小、$r(v)=\log s(v)$，势为 $\mathrm{\Phi }=\sum _{v}r(v)$。一次伸展访问 $x$ 的摊还旋转成本满足

$$\hat{c}\le 3(r(\mathrm{root})-r(x))+1=O(\log n).$$

zig-zig 同时显著缩短两层祖先链，是望远镜估计成立的关键；只把节点逐层单旋虽能移到根，却没有相同序列界。插入、删除可归约为常数次 access、split、join，因此摊还 $O(\log n)$。

访问序列例子 ​

若依次访问有序键 $40,41,42$，第一次可能沿长路径伸展 $40$，但其邻近区域被带到树顶，随后两个访问路径迅速缩短。更一般地，working-set 界让最近访问过且期间不同键较少的元素便宜，dynamic-finger 界让相邻秩访问便宜；这比“常用键靠近根”的口号更精确。

边界与开放问题 ​

树高可为 $\mathrm{\Theta }(n)$，单次访问也可线性；保证属于整个序列的摊还成本，不是最坏延迟。static optimality、working-set 与 dynamic-finger 都已证明，但“与任意离线最优 BST 相差常数”的动态最优猜想不能当作定理。重复键、未命中搜索后伸展哪个节点、删除如何 join 都需固定语义。

序列敏感界 ​

若键 $x$ 自上次被访问后出现过 $t(x)$ 个不同键，working-set theorem 给本次访问 $O(\log (t(x)+1))$ 摊还成本；刚访问过的热点因而接近常数。Dynamic-finger theorem 以上一次访问键 $y$ 与 $x$ 的秩距离控制 $O(\log (|rank(x)-rank(y)|+1))$。这两条都比单纯 $O(\log n)$ 更强，却仍是整段序列的摊还陈述。

删除可先伸展目标到根，使左右子树分离，再伸展左树最大节点并挂接右树。若搜索未命中，通常伸展最后访问节点以保留 access lemma；什么也不伸展会改变后续序列性质。

一次访问怎样偿还旋转 ​

设访问前路径为 $8\to 4\to 6\to 5$。伸展 5 时先对 4、6、5 做 zig-zag，把 5 提到 8 的孩子，再做一次 zig 成为根；中序次序始终为 $4<5<6<8$，因此旋转改变形状却不改变字典语义。访问结束后，刚访问的 5 在根部，路径上的其他节点也被重新分成较浅的两侧。

Access lemma 用秩 $r(v)=\log s(v)$ 记子树权重，单次伸展的摊还代价至多

$$3(r(\text{new root})-r(x))+1.$$

沿一串操作相加时中间秩差望远镜消去，才得到 $O(\log n)$ 摊还访问。它并不限制一次伸展的旋转数；一条长度 $n$ 的链上首次访问末端仍可能花 $\mathrm{\Theta }(n)$。

参考资料

• Daniel Sleator, Robert Tarjan, Self-Adjusting Binary Search Trees, JACM, 1985.
• Robert Tarjan, Sequential Access in Splay Trees Takes Linear Time, Combinatorica, 1985.