连续查询同一个深层节点时，普通搜索树会反复走同一条长路径。Splay 在访问后把该节点旋转到根，使紧接着的同键查询只检查根。这个局部效果容易观察，但不能由此断言任意访问都很便宜：把一条链的尾节点第一次移到根，本来就需要线性代价。

本篇考虑固定的 n 个不同整数键，只做查找和重排。输入是初始二叉搜索树与 q 次查询；输出是每次是否存在，树内集合始终不变。失败搜索把最后访问到的节点伸展到根，空树直接返回失败。成本先数旋转，再把沿搜索路径的比较计入同阶时间；不在同一个常数公式中混用两种成本。

双旋与连续单旋不同

访问节点x有父亲p和祖父g时，根据三者相对方向选择两次旋转。x与p同为左孩子或同为右孩子是zig-zig，先旋转p与g，再旋转x与p。方向相反是zig-zag，先旋转x与p，再旋转x与g。若x只剩父亲，则执行一次zig结束。

每次旋转保持中序键序，访问节点每轮至少向上移动一层，所以过程终止且集合不变。子树大小按06的孩子依赖顺序重算；实现若保存parent指针，还必须同步祖父到新根、被转移孩子到新父的链接。

不能把zig-zig替换为“总是让x与它当前父亲旋转”。两种过程都可能把x移到根，却产生不同树形。下面的势能不等式依赖标准双旋形态，正确查找结果本身不足以证明相同摊还界。

一次双旋如何得到界

给每个节点固定正权重w，令s(x)为x子树权重总和，定义实数秩r(x)=log₂s(x)，势能为所有节点秩之和。权重是分析工具，程序不必保存；为避免与06的查询接口混淆，本节的r不是元素排名。撇号表示某一步旋转后的量。

旋转只改变x、p、g的子树，其余节点的秩不变。一次zig-zig有实际成本2，而且r′(x)=r(g)。消去相同项后，摊还成本为

c^=2+r′(p)+r′(g)−r(x)−r(p).\widehat c=2+r'(p)+r'(g)-r(x)-r(p).

因为r′(p)≤r′(x)、r(p)≥r(x)，可得

c^≤2+r′(x)+r′(g)−2r(x).\widehat c\le2+r'(x)+r'(g)-2r(x).

zig-zig前x的子树与旋转后g的子树是两个不相交区域，二者权重和不超过s′(x)。由对数凹性，或由ab≤((a+b)/2)²，得到

r(x)+r′(g)≤2r′(x)−2.r(x)+r'(g)\le2r'(x)-2.

代回即有摊还成本不超过3(r′(x)−r(x))。这里的常数2来自两个不相交区域的权重平均，不是“树比较平衡”的直觉描述。

zig-zag也先消去r(g)=r′(x)。旋转后的p与g子树不相交，故r′(p)+r′(g)≤2r′(x)−2；再用r(p)≥r(x)，得到

c^≤2(r′(x)−r(x))≤3(r′(x)−r(x)).\widehat c\le2(r'(x)-r(x))\le3(r'(x)-r(x)).

最后一次zig成本为1，只改变x与p。由r′(x)=r(p)及r′(p)≤r′(x)，可得摊还成本不超过1+r′(x)−r(x)，也就不超过1+3(r′(x)−r(x))。

访问引理不等于单次最坏界

沿同一次伸展把各步相加，x的秩变化望远镜消去。设初始根为t，访问点为x，以旋转数c计费，得到访问引理

c+Φafter−Φbefore≤3log⁡2s(t)s(x)+1.c+\Phi_{after}-\Phi_{before} \le3\log_2\frac{s(t)}{s(x)}+1.

空树单独处理，不在公式里取log0。非空树中w>0保证所有子树权重为正。一次成功搜索的访问节点数等于原深度加1，旋转数等于原深度；失败搜索最后访问点亦如此。每个节点做常数次键比较，因此比较与旋转合计只改变常数阶。

令每个权重为1，则1≤s(x)≤n，每次摊还成本为O(log(n+1))。对任意初树的q次访问，真实总成本还要加上初始势能减最终势能：每个秩位于0到log₂n之间，所以

∑ci=O(qlog⁡(n+1)+nlog⁡(n+1)).\sum c_i=O(q\log(n+1)+n\log(n+1)).

不能删掉任意初树带来的初始项，再声称第一次访问也只需对数时间。若另有已证明的初始化成本或指定初始势能，可以把初始化纳入整段操作序列重新分析；这不是把单次最坏成本变小。

本篇没有随机选择，因而该结论是摊还界，不是期望界。一次链尾访问可以是Θ(n)，后面的同键访问却是常数；序列中的便宜操作与势能变化共同解释成本，不需要假定查询“平均分布”。

热点实验怎样读

运行 python3 examples/advanced-algorithms/check_splay.py，原始结果在 examples/advanced-algorithms/results/splay.json。本次18192次小集合穷举查询通过；n=127的集合上分别重放1270次循环均匀访问与63/64/65热点访问，访问节点总数为6304与2969，旋转总数为5034与1699。这是两个指定序列的操作计数，不是耗时或普遍加速比。1024节点右链首次查询最大键，实际访问1024节点、旋转1023次，给出了单次线性代价的直接实例。配套检查契约区分证明和有限数值核对。固定集合的验证必须分别检查查找答案、中序集合、parent链接和子树大小，再用实测旋转数核对本篇势能不等式。浮点计算log时只允许舍入容差，不能用宽松误差掩盖旋转错误。

重复热点查询可观察第一次之后节点处于根；把热点换成另一节点，成本会重新分配。这只能说明指定访问序列的结构演化。静态最优、工作集或动态最优是不同命题，本篇没有从一次热点测量推出它们。

失败搜索同样重要：若实现只在命中时伸展，一直查询大于所有键的值会反复扫描同一条右链。把最后访问点伸展后，下一次相同失败查询可在新根附近结束。这个边界既检查实现是否与分析对象一致，也展示“返回False正确”不代表成本契约已满足。

实现构造时排序并拒绝重复键，预处理最坏O(n log(n+1))，建平衡树或链另需O(n)。节点空间O(n)，查找和旋转使用parent指针迭代，额外工作空间O(1)；测试器全树检查和势能重算各需O(n)，不计入容器查找成本。单位字长假设与06一致，任意大整数比较须另计位长。

练习

  1. 从键1到5组成的右链开始搜索5，画标准zig-zig步骤，计算每步单位权重势能。比较实际旋转数与访问引理右侧，说明为什么总有界不要求每个步骤都便宜。
  2. 让实现不伸展失败搜索的最后节点，在同一右链上反复搜索6，与原实现比较访问节点总数。两者答案是否相同？哪项前提被破坏？

参考资料