00-课前零食-让刚访问的点靠近你.md 12 KB
课前零食：让刚访问的点靠近你
Splay 的口头禅很大胆：我不保证每一次都快，但我会把刚被你找过的节点拉到眼前。它不像 FHQ Treap 那样给每张卡发随机优先级，而是每次访问后认真整理桌面。今天先只学这件事：旋一下，到底保住了什么，又为什么要旋两下。
本节目标
学完后，你能：
- 说明 BST 旋转为何不改变中序顺序；
- 在纸上区分 zig、zig-zig、zig-zag 三种 Splay 步；
- 手动把一个被访问的节点伸展（splay）到根，检查父子指针与子树大小；
- 从查找、插入、删除三个朴素需求出发理解“访问后伸展”的接口；
- 正确表述 Splay 的复杂度：单次可能线性，操作序列摊还 O(log n)。
前置知识与课前自测
前置：二叉搜索树、左右儿子、父指针、子树大小。还没有接触 Lazy 标记也可以。
- BST 的中序遍历为什么是升序？
- 把一条边的父子关系旋转后，节点本身的键会被交换吗？
- 若总是访问一棵链最深处的节点，一次操作的旋转次数可能是 O(n) 吗？
先答再看：自测答案
1. 每个节点左子树键更小、右子树键更大，递归展开即为升序。2. 不交换键，只改局部指针。3. 可能；Splay 承诺的是一串操作的平均账，而不是每次都给最坏对数界。互动规则：每一次旋转都要写“中序证据”
在纸上先画这棵普通 BST：
10
/ \
5 15
/ \ / \
3 7 12 18
贯穿任务是依次做：查找 7、插入 6、删除 10。纸上分四栏：对象（当前节点和三块子树）、状态（parent、left、right、size）、动作（本轮绕谁旋转）、账本（中序和父指针是否仍正确）。每次旋转后，把中序写一遍；这有点笨，但能抓到大多数 Splay 第一版的幽灵 bug。
从零搭框架：先让“常访问”变成一个真实问题
第 0 步：BST 已经会找路，但它不记得你常走哪条路
从根查找 7：比较 7 与 10，向左；比较 7 与 5，向右；找到 7。若接下来又查 7、又查 7，每次仍要走同样两条边。对很深的节点，重复走路比比较本身更烦。
停顿 0：如果现在连续查找 7 五次，普通 BST 会总共经过哪些节点？哪一段路径被反复走了五遍？
展开：我们想改变的是树形，不是键的顺序
每次都经过 10→5→7。把 7 放近根能减少以后访问它的路径；但不能直接把数值 7 与 10 交换，否则 BST 的中序顺序会坏。我们只能重新接局部边，同时保住所有键的左小右大关系。第 1 步：只旋一条边，先证明中序没变
设 x 是 p 的右儿子，x 的左子树叫 B；p 的左子树叫 A，x 的右子树叫 C。对 p 做一次左旋，x 上来、p 下去，B 从 x 的左边转为 p 的右边：
旋前： 旋后：
p x
/ \ / \
A x → p C
/ \ / \
B C A B
因为 A < p < B < x < C，旋前旋后中序都是 A,p,B,x,C。
停顿 1：若 x 是 p 的左儿子，应该用左旋还是右旋？B 在旋转后应该挂到 p 的哪一侧？请用不等式检查，而不要靠镜像记忆。
展开：镜像规则从键范围推出
x 为左儿子时做右旋；x 的右子树 B 比 x 大、比 p 小，所以旋后 B 成为 p 的左子树。真正要记的是 B 的键范围，而不是“图向哪边倒”。第 2 步：只把 x 一次次旋上去，哪里不够好
假设 x、父亲 p、祖父 g 连成同向链，例如 x 是 p 的左儿子且 p 是 g 的左儿子。若只旋 x 一次，p 会被拉下，但长链的整体形状没有得到充分压缩。Splay 的规定是：先旋 p 绕 g，再旋 x 绕 p；这叫 zig-zig。
若 x 和 p 方向相反，例如 x 是 p 的右儿子、p 是 g 的左儿子，则连续旋 x 两次；这叫 zig-zag。若 p 就是根，只剩一次 zig。
停顿 2：在初始树中，x=7、p=5、g=10。它属于哪一种？第一转绕谁，第二转绕谁？请画出两次后的根。
展开：7 是 zig-zag
7 是 5 的右儿子，而 5 是 10 的左儿子，方向相反。先让 7 绕 5 左旋，再让 7 绕 10 右旋，7 成为根。中序仍为 3,5,7,10,12,15,18；只是以后访问 7 不必再经过 10、5。第 3 步：把三种情形写成一个循环
Splay 的目标可以是根，也可以是某个指定父亲 goal。后一种接口会在“文艺平衡树”中暴露区间：先把左边界伸到根，再把右边界伸到它的右儿子位置。
splay(x, goal):
while parent[x] is not goal:
p = parent[x]
g = parent[p]
if g is goal:
rotate(x) # zig
else if x and p are both left children,
or both right children:
rotate(p); rotate(x) # zig-zig
else:
rotate(x); rotate(x) # zig-zag
每次 rotate 前后，都要更新被移动的两个节点的 size；若以后加了翻转等 Lazy 标记，还要先从祖先到 x 依次 push，免得逻辑左右与指针左右不一致。
问题动机：访问并不总是随机的
红黑树、AVL 等结构每次都努力保持严格高度界；Splay 换了一个愿望：最近访问的点、相近键或经常使用的区间，应该逐渐靠近根。它的优势不是“每次比别人少一转”，而是允许一次访问花较多旋转，换取随后很多次访问变便宜。
因此绝不能把“查找 7 后 7 在根”误解为一个小优化；它是所有操作完成后统一执行的自调整规则。
步步式引导：查、插、删都先把对象拉到手边
1. 查找：即使没找到，最后访问点也有价值
按 BST 规则走到 x 或空指针。若找到了 x，就 splay(x, null)。若没找到，最后停在某个叶边附近，也可把最后访问的节点伸根；它正是新键将来插入的邻居。
2. 插入：先按 BST 放入，再伸到根
最直白的入门实现：普通 BST 插入新叶 x，设置 parent，再 splay(x, null)。这样根必是 x，左右子树天然分别存比 x 小和比 x 大的键。重复键的处理需统一：可存 count，也可规定同键向一侧走；本节实验室用无重复集合，避免把两个变量混在一起。
3. 删除：先把待删点变成根
找到 x 并 splay 到根，断开左树 L 和右树 R。若 L 非空，取 L 的最大节点 m；在 L 内把 m splay 到根，它不会有右儿子，再把 R 挂为它的右儿子。若 L 为空，R 直接成为新根。
停顿 3：为什么“左树最大点”没有右儿子？把 R 接到它右边后，BST 键范围为什么仍正确？
展开：删除不是把两个任意根硬粘
L 中没有比最大点 m 更大的键，所以 m 没有右儿子。L 的所有键都小于 x，R 的所有键都大于 x，也就都大于 m；将 R 作为 m 的右树既保持中序，也不遗漏任何节点。核心知识：正确性和复杂度的边界
旋转只改变 A,p,B,x,C 五块的连接，键范围证明保证中序不变；连续旋转因此始终保留 BST。每次 splay 循环都让 x 向目标父亲靠近，最终停止。若维护 size，每次改变孩子后由下而上 pull，size 仍等于左右子树节点数加一。
Splay 的访问引理以子树大小定义势能，说明任意 m 次操作总时间为 O(m log n) 的量级（更精细表述可包含初末势能项）。单次访问一条长度 n 的链仍可能 O(n)。所以它适合摊还保证，不能拿来应对题面明确要求每次最坏 O(log n) 的接口承诺。
实现指南
- rotate(x) 前要知道 p、g，以及 x 是 p 的左还是右；修改 g 到 p 的那条边时不要漏掉“p 原来是根”的情况。
- 每次改 child 都同步 child.parent；根的 parent 必须是 null/0。
- 推荐写 is_right(x) 只比较 parent[x].right 是否等于 x；不要靠键值猜方向。
- pull 的顺序是先 pull 被拉下去的 p，再 pull 上来的 x。
- 若有 Lazy，先把从根到 x 的祖先链收集起来，自顶向下 push；否则 kth 和区间暴露会在反转后的逻辑序列上走错。
- 递归深度不是 Splay 的实现需求，旋转版通常更适合避免深链递归。
纸上模拟：把 7 伸上来，不跳过任何一条指针
从初始 BST 查到 7 后，填表：
| 阶段 | x 的父亲 | x 的祖父 | 情形 | 本轮后根 | 必须 pull 谁 |
|---|---|---|---|---|---|
| 开始 | |||||
| 第一次旋转后 | |||||
| 第二次旋转后 |
展开：一份最小可检查轨迹
开始时 p=5、g=10，是 zig-zag。第一次 rotate(7) 后，7 成为 10 的左儿子、5 成为 7 的左儿子；第二次 rotate(7) 后，7 为根、10 为右儿子。每次先 pull 被放低的节点，再 pull 7；最后中序和原来完全相同。再自己插入 6：普通 BST 会把它放在 5 的右侧、7 的左侧。把 6 splay 到根之前，先预测它会经历 zig-zag 还是 zig-zig；若你能根据左右方向而非死记答案判断，就已经握住 Splay 的骨头了。
互动小实验室
运行 让刚访问的点靠近你.py。它从同一棵小 BST 出发，先请你预测查找 7 的两次旋转，再打印每个 zig、zig-zig、zig-zag。可输入：
- find 7：查找并把最后访问点伸到根；
- add 6：插入后伸展新点；
- del 10：删除一个键，观察两棵子树如何重新接回；
- show：查看侧视树、中序和 size；
- check：检查 parent、BST、中序、size 四份账本。
建议先执行 find 7，再 show；然后在纸上预测 add 6 的第一个祖孙形状。树会动，键的排序不会动，这正是游戏规则。
扩展与联系
- FHQ Treap 也维护有序集合，但靠随机优先级和 split/merge；Splay 靠访问后的旋转，两者都不应被简化成“另一个模板”。
- 双哨兵、按排名 kth、区间翻转会把 Splay 变成序列结构；下一份零食会从一句话如何倒过来开始。
- Splay 的动态最优性猜想很有名，但不需要把它当作已证明事实；本课只使用已知的摊还对数访问界。
- 若操作完全离线、没有动态插删，数组、Fenwick 或线段树常更简单；Splay 不是“能转就该转”。
总结与自检
- 一次旋转为什么不改变 BST 的中序？
- zig-zig 与 zig-zag 的判断依据是什么？
- 删除根时为何可用左树最大点接上右树？
- Splay 的 O(log n) 是单次还是摊还结论？