# 课前零食：让刚访问的点靠近你 > Splay 的口头禅很大胆：我不保证每一次都快，但我会把刚被你找过的节点拉到眼前。它不像 FHQ Treap 那样给每张卡发随机优先级，而是每次访问后认真整理桌面。今天先只学这件事：旋一下，到底保住了什么，又为什么要旋两下。 ## 本节目标 学完后，你能： - 说明 BST 旋转为何不改变中序顺序； - 在纸上区分 zig、zig-zig、zig-zag 三种 Splay 步； - 手动把一个被访问的节点伸展（splay）到根，检查父子指针与子树大小； - 从查找、插入、删除三个朴素需求出发理解“访问后伸展”的接口； - 正确表述 Splay 的复杂度：单次可能线性，操作序列摊还 O(log n)。 ## 前置知识与课前自测 前置：二叉搜索树、左右儿子、父指针、子树大小。还没有接触 Lazy 标记也可以。 1. BST 的中序遍历为什么是升序？ 2. 把一条边的父子关系旋转后，节点本身的键会被交换吗？ 3. 若总是访问一棵链最深处的节点，一次操作的旋转次数可能是 O(n) 吗？
先答再看：自测答案 1. 每个节点左子树键更小、右子树键更大，递归展开即为升序。2. 不交换键，只改局部指针。3. 可能；Splay 承诺的是一串操作的平均账，而不是每次都给最坏对数界。
## 互动规则：每一次旋转都要写“中序证据” 在纸上先画这棵普通 BST： ~~~text 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 的右边： ~~~text 旋前： 旋后： p x / \ / \ A x → p C / \ / \ B C A B ~~~ 因为 A < p < B < x < C，旋前旋后中序都是 A,p,B,x,C。 ![一次旋转只改局部边，却保留中序](../插图/11-平衡树/00-Splay-01-旋转不改中序.svg) > 停顿 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。 ![三种局部情形，不是三段咒语](../插图/11-平衡树/00-Splay-02-zig的三种节奏.svg) > 停顿 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。后一种接口会在“文艺平衡树”中暴露区间：先把左边界伸到根，再把右边界伸到它的右儿子位置。 ~~~text 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](../../互动程序/11-平衡树/00-让刚访问的点靠近你.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 不是“能转就该转”。 ## 总结与自检 1. 一次旋转为什么不改变 BST 的中序？ 2. zig-zig 与 zig-zag 的判断依据是什么？ 3. 删除根时为何可用左树最大点接上右树？ 4. Splay 的 O(log n) 是单次还是摊还结论？
自检答案 靠三块子树的键范围重接；看 x 与父亲相对方向是否相同；它没有右儿子且右树全比它大；是整个操作序列的摊还结论。
## 一周预热安排 - 第 1 天：画一次左旋、一次右旋，并在两图下写同一份中序。 - 第 2 天：对三种祖孙关系分别标出旋转顺序。 - 第 3 天：手做 find 7 和 add 6，检查 parent 与 size。 - 第 4 天：运行互动程序，再用 check 追一遍四份账本。 - 第 5 天：先完成[把一段话翻过来](00-课前零食-把一段话翻过来.md)，再进入[Splay 正式课](03-Splay伸展与区间暴露.md)。