自调整数据结构

序列模型 ​

对访问序列 $\sigma =(x_1,\dots ,x_m)$，研究总成本 $C(\sigma )$，而非每次统一最坏成本。结构在访问后重排，让未来成本依赖最近性；分析用势能法公理库势能法Potential method用数据结构状态势能的变化修正实际成本以界定均摊成本。让昂贵调整与潜能下降抵消。

Working-set 界按自上次访问 $x_t$ 后出现的不同键数 $w_t$ 收费 $O(\log (w_t+1))$；dynamic-finger 依相邻访问秩距离；static optimality 与知道频率后的最佳静态树比较。这些是不同定理。

访问改变结构 ​

伸展树访问后把键旋到根。连续访问同一键，第一次可能沿长度 $n$ 的链，之后为常数；move-to-front 链表则把命中项移到表头。两者都利用序列局部性。

单次延迟仍可 $\mathrm{\Theta }(n)$，树高也可线性。短序列可能只支付调整来不及受益。随机平衡依随机优先级，静态最优树依预知频率，都不是访问驱动的自调整。

开放边界 ​

“与任何离线 BST 常数竞争”的动态最优性是一个特定而开放的比较基准，不能附给所有自调整结构。只证明 working-set、dynamic-finger 或 access lemma 时，应准确报告对应定理。

Working-set 参数计算自上次访问该键之后出现过的不同键数，不是间隔操作数或全局频率。例如序列 ((a,b,c,a)) 的最后一次访问 a 对应集合 ({b,c})，参数为 2。缓存自适应索引还必须把重排成本计入，不能只展示热点移近后的查询。

伸展步骤的状态演化 ​

访问节点 $x$ 后重复三种情形：父为根时做一次 zig；$x$ 与父同为左孩子或同为右孩子时先旋祖父再旋父，称 zig-zig；方向相反时先旋父再旋祖父，称 zig-zag。每步保持 BST 中序不变，最终 $x$ 成根。更新不需要颜色、高度等显式证书。

在键链 $1<2<3<4$ 中访问 4，两次同向旋转压缩路径；随后访问 3 只在根附近操作。若依次访问 $1,4,1,4$，树反复调整，某些单步仍线性，但总成本由势能约束。状态变化既是加速来源，也是尾延迟来源。

Access lemma 的证明图像 ​

令 $s(v)$ 为子树大小、$r(v)=\log s(v)$，势为 $\mathrm{\Phi }=\sum _{v}r(v)$。每个伸展步骤的摊还成本可由 $O(1)+\mathrm{\Delta }\mathrm{\Phi }$ 上界为常数倍 $r^{\prime }(x)-r(x)$；沿路径求和望远镜，单次 access 摊还 $O(\log n)$. Working-set 等更强界还需选择带权大小，不由基本 access lemma 自动得到。

势可能在一次操作后大幅下降，所以实际线性成本仍可有对数摊还；把势能项丢掉就会错误得到最坏界。

与随机平衡和静态最优的对照 ​

Treap 在创建节点时随机决定形状，不因访问改变；最优静态 BST 假设频率已知，构建后固定；自调整结构从序列在线学习局部性，却为重排付费。三者的“常用键较浅”来源不同，概率和比较基准也不同。

参考资料

• Daniel Sleator, Robert Tarjan, “Self-Adjusting Binary Search Trees,” JACM, 1985.
• Sleator, Tarjan, “Amortized Efficiency of List Update and Paging Rules,” CACM, 1985.