(a2)伸展树：双层伸展

官官方信息技术老师·10 页·深入（追求细节与边界）·0 次浏览·3 天前

✦ (a2)伸展树：双层伸展信息技术 (a2)伸展树：双层伸展双层伸展

伸展树自调整zig-zig摊还分析

(a2)伸展树：双层伸展

拆透 zig-zig 和 zig-zag 的旋转结构，搞懂均摊对数复杂度由来

按空格/→ 演示下一步

1 / 10 页

全部页面点击任意一页，跳回舞台从这页播放

伸展树自调整zig-zig摊还分析

(a2)伸展树：双层伸展

拆透 zig-zig 和 zig-zag 的旋转结构，搞懂均摊对数复杂度由来

1第 1 页 · (a2)伸展树：双层伸展

双层伸展

上节的单层旋转把 x 一层一层往上挪，深链访问的摊还代价退化到 O(n)。解法是一次看三层——祖父、父亲、x，让 x 一步跨两层，沿途兄弟子树一并压低。

触发条件

被伸展节点 x 不是根，且存在祖父节点（深度≥2）

zig-zig 同向一字型

x 与父节点同为祖父的左子或右子；先转祖父-父边，再转父-x 边

zig-zag 异向之字型

x 与父节点分居祖父两侧；对 x 做两次单旋（左-右或右-左）

摊还意义

祖父、父亲所在子树高度折半下降，是摊还 O(log n) 的关键来源

折纸扇对应 →zig-zig 双旋顺序

要把里层翻到外，得先把外层折进来再折内层；反过来只翻薄薄一片，效率低

2第 2 页 · 双层伸展

子孙异侧

上节说需要双层旋转的情况有两类。本节看第一类：X 和 P 在 G 的两侧，呈之字形——典型的 zig-zag。

结构定义

X 是 P 的左孩子、P 是 G 的右孩子（或镜像），左右相反

旋转顺序

先把 X 绕 P 转一次，再把 X 绕 G 转一次

提升效果

两次后 X 直接升到 G 的原位，子树高度下降一层

典型出现

LCT 的 access 操作中，左右子树交替伸展时大量触发

祖孙站位一左一右对应 →子孙异侧的之字形

爷爷左、爸爸右、你左——之字形；要推你上去，先在爸爸那转一次，再到爷爷那转一次

3第 3 页 · 子孙异侧

子孙同侧

上节我们看了子孙异侧的「两次反向旋转」。如果 X 和 P 站在祖辈的同一侧，调整手法就要反过来——连续两次同向旋转。

同侧定义

X 与 P 各自挂在父节点的同一侧（左-左或右-右）

旋转手法

沿同一方向连续两次旋转（先转上层边、再转下层边），X 一步升两级

与异侧的差别

异侧是「一正一反」折返；同侧是「两连击」同向

调整效果

把路径上两段相邻同向折线一次性捋直，重组更彻底

连续两个同向弯道对应 →子孙同侧的双旋转

两次同向旋转相当于把同侧的两段折弯一次拉直

4第 4 页 · 子孙同侧

点睛之笔

前两页我们按子孙异侧、子孙同侧看完了双层旋转的两种形态，但为什么非要绕这两层、而不是把目标节点一层层旋上去？这一页回到动机，回答双层伸展为何是伸展树的灵魂。

单旋的局限

单纯逐层上旋，路径上多数节点深度几乎不变，最坏均摊退化至 O(n)

双旋的关键收益

zig-zig 与 zig-zag 让路径上至少一半节点深度对数级下降

势能函数证明

取 Φ=Σlog₂(子树大小)，可证 splay 的均摊代价严格 O(log n)

适用场景

伸展树查找/插入/删除三大操作的统一前置步骤

折一条弯曲纸带对应 →双层伸展

同侧连续对折两次（zig-zig），异侧翻向再折（zig-zag），每次都让纸带长度近乎减半

\Phi(T) = \sum_{v \in T} \log_2 \text{size}(v)

5第 5 页 · 点睛之笔

折叠效果

上一节我们用两步旋转把节点连提两层——看似只比单旋快一点,但叠起来就有了质变:每次伸展后,根到目标节点的路径都会被「对折」一次。

路径折半

深度为 k 的节点被伸展后,新深度约为 k/2,每做一次砍一半

反复访问不爆

哪怕反复访问同一深处的节点,单次操作仍是摊还 O(log n)

均摊上界之根

正因为深度指数级缩短,均摊成本才能压到 O(log n)

把一条长毛巾反复对折对应 →伸展把路径对折

毛巾折一次长度减半,再折再减半;伸展树也用同样方式把「走到目标」的距离压短

\text{depth}_{\text{new}}(x) \le \lfloor \text{depth}_{\text{old}}(x)/2 \rfloor + 1

6第 6 页 · 折叠效果

分摊性能

前页把查找路径折到根，局部结构已经变短；可这不等于每次访问都只有 O(log n)。把一整串访问合起来算，分摊上界才是理解性能的关键。

分摊上界

把连续操作的总耗时均摊到每次，描述序列层面的平均上界

序列上界

n 结点树的 m 次伸展访问共 O(m log n)，均摊 O(log n)，单次仍可 O(n)

势能函数

Φ(T)=各结点 log(子树大小)之和；摊还成本把旋转前后的势能变化一并计算

适用边界

适合动态有序集、热点访问和顺序批量处理；硬实时仍缺乏单次最坏保证

轮流办事的一条长队对应 →伸展树的操作序列

一次有人排很久，只是那一次慢；把整队总耗时均摊到每个人，才对应分摊上界

a(x)=c(x)+\Phi(T')-\Phi(T)，\quad a(x)\le3(\log n-\log|T(x)|)+1，\quad \sum_{i=1}^{m}c(x_i)=O(m\log n)

7第 7 页 · 分摊性能

最后一步

前面讲过同侧、异侧的双层旋转，可当节点只剩一步就能抵达根时——情形变了。

只剩一层

目标节点是根的直接孩子，已无法双层旋转

Zig 单旋

只做一次普通旋转，把节点送到根

伸展收官

本次 splay 结束，节点到达树根位置

登顶前的最后一级台阶对应 →Zig 单旋

双层操作是连跨两级，最后一级只需轻跨一步便登顶

8第 8 页 · 最后一步

本节要点

✓单旋只把访问节点往上挪一层，路径反而被拉细长
✓双层旋转的核心：爷孙关系要配对处理，跨层级协作
✓同侧连转同向、异侧一正一反——两种折叠姿态
✓折叠效果：访问路径被压向根部，节点深度大致折半
✓分摊 O(log n)：连续 m 次操作均摊对数时间

延伸主题：势能分析：分摊 O(log n) 的证明伸展树的删除操作与 AVL/红黑树的工程取舍

9第 9 页 · 本节要点

课后思考

先合上笔记自己想想，再对照参考答案。

1为什么 zig-zig（子孙同侧）要先旋转祖父，再旋转父亲？

参考答案关键在折叠效果——祖父先转让路径深度对半折，后续旋转延续这一折叠；若先转父亲，深度只减 1，无法形成分摊保证。

2画一棵完全二叉树，反复访问最深处某叶子 10 次。每次伸展后该叶子到根的路径长度如何变化？

参考答案按对数级折半递减：log₂n, log₂n−1, …, 直到稳定在 1。这就是折叠效果——两次伸展砍掉一半路径。

3我们讨论了 zig-zig 和 zig-zag。还有第三种情况：x 的父亲就是根（zig）。为什么 zig 只需单次旋转，不必双层？

参考答案因为 zig 情况下 x 已到顶层，父亲就是根，没有祖父可以「转上去」。单次旋转直接把 x 提到根部——双层规则在此自然退化。

10第 10 页 · 课后思考