伸展树

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

访问序列例子 ​

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

边界与开放问题 ​

树高可为 $\mathrm{\Theta }(n)$，单次访问也可线性；保证属于整个序列的摊还成本，不是最坏延迟。static optimality、working-set 与 dynamic-finger 是已经建立的特定序列界。动态最优猜想要求相对离线最优动态 BST 的常数竞争比；截至 2026 年 10 月 5 日核对的下面这份预印本，只给出了仍随 $n$ 增长的比值。

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

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

伸展树没有显式平衡字段，其访问界由势能法理路势能法Potential method用数据结构状态势函数的增量调整单步记账，以控制操作序列的总成本。证明：以节点子树大小的对数秩求和为势，zig-zig 与 zig-zag 的旋转成本由秩下降支付。

序列敏感界 ​

固定含 $n$ 个键的树，令 $t(x)$ 为自上次访问 $x$ 后出现过的不同键数，首次访问时可取 $t(x)=n$。Working-set 界按 $O(1+\log (t(x)+1))$ 收费；连续访问同一键时 $t(x)=0$，仍保留常数访问成本。Dynamic-finger 界则按相邻访问键的秩距离 $d$ 收费 $O(1+\log (d+1))$。这两种写法分别描述整段序列的总界，不给每次访问的独立最坏保证；从任意初始树开始时，可以另保留 $O(n\log (n+1))$ 的初始化/初始势费用。

删除可先伸展目标到根，使左右子树分离，再伸展左树最大节点并挂接右树。若搜索未命中，通常伸展最后访问节点以保留 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。沿多次访问相加时，真正望远镜消去的是势函数的前后差 $\mathrm{\Phi }(D_i)-\mathrm{\Phi }(D_{i-1})$，而不是不同访问目标的秩。由此得到 $m$ 次访问的实际总成本 $O(m\log (n+1)+n\log (n+1))$；后一项保留任意初始树的势费用。长度 $n$ 的链上首次访问末端仍可花 $\mathrm{\Theta }(n)$，与这个总界一致。