伸展树

伸展把本次访问路径整体重排，而不维护颜色或高度证书。zig-zig 与 zig-zag 让被访问节点上升的同时压缩其祖先路径；子树秩势记录这次重排积累或释放的结构能量，所以单步可线性，整段访问仍有对数摊还和更细的序列敏感界。

访问序列例子 ​

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

边界与开放问题 ​

树高可为 $\mathrm{\Theta }(n)$，单次访问也可线性；保证属于整个序列的摊还成本，不是最坏延迟。static optimality、working-set 与 dynamic-finger 都已证明，但“与任意离线最优 BST 相差常数”的动态最优猜想截至 2026 年 8 月 10 日仍未解决。

2026 年 7 月 20 日的一份 arXiv v1 预印本给出了显著的新上界：伸展树相对离线最优动态 BST 为

竞争，并称这是首个 $o(\log n)$ 的通用竞争比。它把已知差距从对数级压到近双对数级，却仍不是常数竞争比，因此没有解决动态最优猜想；在形成稳定的同行评议结论前，本页把它明确标为预印本结果。重复键、未命中搜索后伸展哪个节点、删除如何 join 仍都需固定语义。

伸展树没有显式平衡字段，其访问界由势能法公理库势能法Potential method用数据结构状态势能的变化修正实际成本以界定均摊成本。证明：以节点子树大小的对数秩求和为势，zig-zig 与 zig-zag 的旋转成本由秩下降支付。

序列敏感界 ​

若键 $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)$ 记子树权重，单次伸展的摊还代价至多

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