自调整数据结构

访问改变结构 ​

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

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

开放边界 ​

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

Working-set 参数计算自上次访问该键之后出现过的不同键数，不是间隔操作数或全局频率。例如序列 $(a,b,c,a)$ 的最后一次访问 a 对应集合 $\{b,c\}$，参数为 2；连续访问同一键时参数为 0，收费式中的常数项仍承担一次访问。首次访问与初始结构还需按具体定理计入初始化费用。缓存自适应索引还必须把重排成本计入，不能只展示热点移近后的查询。

伸展步骤的状态演化 ​

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

在由根 1 开始的右链 $1\to 2\to 3\to 4$ 中访问 4，先对 2、3、4 做两次同向旋转，再对根 1 做一次 zig，共三次旋转使 4 成为根；随后访问 3 只在根附近操作。若依次访问 $1,4,1,4$，树反复调整，某些单步仍线性，但总成本由势能约束。状态变化既是加速来源，也是尾延迟来源。

Access lemma 的证明图像 ​

令 $s(v)$ 为子树大小、$r(v)={\log }_{2}s(v)$，势为 $\mathrm{\Phi }=\sum _{v}r(v)$。以实际旋转数加势变化定义摊还成本理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。。每个双旋步骤至多为 $3(r^{\prime }(x)-r(x))$，可能出现的最后一次 zig 则至多为 $1+3(r^{\prime }(x)-r(x))$。沿同一次伸展把秩增量望远镜相加，得到 $1+3\log (s(root)/s(x))$ 的 access 界，其中大小取自访问前。最后单旋的常数项不能省略。 Working-set 等更强界还需选择带权大小，不由基本 access lemma 自动得到。

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

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

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