# 课前零食：从排好队到会分身的树

> 这一份零食专门给 FHQ Treap 准备。正式课一开口就是 `split/merge`，确实像有人把你带到乐高城堡前，只递来两块奇形零件说“拼吧”。今天我们从最笨的队伍开始，一块一块看它们为什么会出现。

## 本节目标

学完后，你能：

- 比较无序数组、有序数组、普通 BST 在动态有序集合上的优缺点；
- 同时说出 Treap 的 BST 键值不变量和随机优先级堆不变量；
- 从“按键切开”和“把两段接回去”的需求发明 `split` 与 `merge`；
- 手动追踪 `pull`、按值 `split`、`merge`、插入、删除一个重复值和第 $k$ 小；
- 知道 FHQ Treap 给的是期望 $O(\log n)$，而非无条件的最坏界。

## 前置知识与课前自测

前置：数组、二分查找、递归、二叉树、随机数的基本直觉。

1. 排好序的数组中查一个值很快，为什么在中间插入一个新值仍可能慢？
2. 把递增键依次插入普通 BST，会长成什么形状？
3. 一个节点若知道左右子树分别有多少元素，怎样判断第 $k$ 小在左、自己还是右？

<details><summary>答案</summary>

1. 后面元素都要整体右移，最坏 $O(n)$。2. 一条链，查找和插入退化到 $O(n)$。3. 设左子树大小为 `L`、本节点重复数为 `cnt`：$k\le L$ 去左；$L<k\le L+cnt$ 就是自己；否则去右并令 $k-=L+cnt$。

</details>

## 互动规则：今天先别急着相信树

这节要用同一组数反复做实验：

$$
S=[4,2,7,5,2].
$$

请在纸上画四栏：`结构里存了什么`、`本次操作看了/搬了哪些元素`、`操作后仍必须成立的性质`、`下一步还缺什么`。每读到“停顿”时先停下来；不要把折叠区当成自动播放按钮。

我们的贯穿任务是依次执行：插入 `6`、删除一个 `2`、求 `rank(6)`、求第 `3` 小。它们不是题目，而是用来观察结构是否真的在工作。你要反复问自己：**我现在维护的是一串数、一个顺序，还是一棵带摘要的树？**

## 从零搭框架：先把人脑会做的事拆开

### 第 0 步：把“有序集合”翻译成四种动作

先不许说 Treap，也不许说 `split`。对一个能重复的整数集合，写下下面四句话各自真正需要的信息：

| 动作 | 人脑最直接的做法 | 若没有顺序，最先卡在哪 |
|---|---|---|
| `insert(x)` | 把 `x` 放进某个容器 | 放哪儿才能仍有序？ |
| `erase_one(x)` | 找到一个 `x` 并删掉 | 怎么确认只删一个？ |
| `rank(x)` | 数有多少数严格小于 `x` | 要把所有数都看一遍吗？ |
| `kth(k)` | 排序后取第 `k` 格 | 每次都重新排序吗？ |

> 停顿 0：在 $S$ 中执行 `rank(6)`。请先圈出严格小于 6 的元素，并写下你看了几张“数卡”。

<details><summary>展开：最暴力账本</summary>

小于 6 的是 `4,2,5,2`，所以排名是 5（排名从 1 开始）。无序数组必须看 5 张卡；求第 3 小还要排序或反复找最小值。这里的第一个瓶颈不是“不会比较”，而是每次询问都把同一批大小关系重算了。

</details>

### 第 1 步：先试两种数组，让代价亲自出现

**无序数组**把 `6` 直接追加，几乎不用移动；但 `rank(6)` 和 `kth(3)` 都要重新认识全体成员。**有序数组**先把 $S$ 写成：

```text
下标:  1  2  3  4  5
数值:  2  2  4  5  7
```

现在插入 `6`。请在纸上画一个空格，并用箭头表示谁要右移。

> 停顿 1：二分能很快找到 `6` 应在 `5` 和 `7` 之间。那为什么插入仍不是对数复杂度？这一步到底移动了哪几格？

<details><summary>展开：找到位置不等于完成插入</summary>

`6` 应放在第 5 格，原来的 `7` 必须从第 5 格搬到第 6 格。这个例子只搬 1 个元素；若插入最小值，后面所有元素都要右移。二分查找只解决“问哪里”，没有解决“给它腾位置”。

数组实验给出第一个设计要求：**希望保留有序性，同时插入/删除只改少数局部连接，而不是搬一大段连续内存。**

</details>

### 第 2 步：把“左边更小、右边更大”画成路口

二叉搜索树（Binary Search Tree, BST）把一个数放在节点上。对键 `4`，小于它的数永远向左，大于它的数永远向右；相同键先暂时记在同一张卡的 `count` 里。请按顺序插入 `4,2,7,5,2`，每一步只回答两个问题：

1. 比较当前键后，下一步只能去左还是只能去右？
2. 到空位置或相同键时，哪一项局部信息要改变？

建议把每个节点画成卡片：

```text
key = 4     count = 1
left = ?    right = ?
```

> 停顿 2：在你画出的 BST 中，找 `6` 会经过哪些键？插入第二个 `2` 时，为什么“另建一个同键节点”和“把 `count` 加一”都可行，但后续规则必须统一？

<details><summary>展开：BST 已经省掉了什么</summary>

找 `6` 会经过 `4→7→5`，最后落在 `5` 的右侧。BST 每次比较都能排除一整侧子树，所以若树矮，操作只需走一条根到叶路径。重复值若合并成 `count`，`size` 必须把 `count` 全算进去；若分开建节点，则每个节点贡献 1。两种账本都能用，混用时第 $k$ 小必错。

</details>

### 第 3 步：请你亲手把 BST 攻击成一条链

重新从空树依次插入 `1,2,3,4,5,6`。不要跳步，画出每条新边。然后在表中填写：

| 插入到 | 需要比较几次 | 新节点深度 | 树高 |
|---|---:|---:|---:|
| 1 | 0 | 0 | 0 |
| 2 |  |  |  |
| 3 |  |  |  |
| 6 |  |  |  |

> 停顿 3：这棵树和有序数组的“从左走到右”相比，真的躲开线性代价了吗？若想修复它，**绝不能**破坏哪一件事？

<details><summary>展开：新的账本要求</summary>

它变成向右的链；插入第 6 个数要比较 5 次，高度也是 5。我们必须保住 BST 的键值顺序，否则排名与二分路线都没了；但还要让“谁更靠近根”不再由输入先后顺序独裁。于是需要第二把、与键无关的尺子来决定树形。

</details>

### 第 4 步：给每张键卡发一张随机优先级卡

现在用下面这组**固定优先级**做纸上实验，先别把它当随机数：

| 键 `key` | 2 | 4 | 5 | 7 |
|---|---:|---:|---:|---:|
| 优先级 `priority` | 35 | 60 | 83 | 20 |

约定“大优先级在上”。请先回答：最高优先级是谁？它的左边只能放哪些键，右边只能放哪些键？然后在左右两边重复同样问题。

> 停顿 4：不看下方答案，画出整棵树，并在每条边旁写两句证词：一条关于键大小，一条关于优先级大小。

<details><summary>展开：两条不变量第一次同时落地</summary>

根是 `5/83`。左侧键为 `2,4`，其中优先级更高的 `4/60` 做左孩子，`2/35` 是它的左孩子；右侧是 `7/20`。中序读出 `2,4,5,7`，所以键值有序；每个父亲优先级更大，所以满足堆序。

这不是“先按优先级排序再插入”的技巧，而是同时维护两条不变量：键决定中序，优先级决定根。随机发优先级时，递增键也不再必然做成一条链。

</details>

### 第 5 步：没有 `split` 时，插入到底在重复做什么

想把 `6` 放进刚才的树。你当然可以沿 `5→7` 找位置，再想办法让优先级关系恢复；但请换一种描述：我们真正想要的是把旧集合切成“比 6 小”“等于 6”“比 6 大”三堆，处理中间那堆，再按原顺序接回去。

这句话就是 FHQ Treap 的框架，不是代码技巧：

```text
输入集合
    ↓ 按一个边界切开
几块各自仍合法的树
    ↓ 只处理目标块
按键范围正确地接回
```

> 停顿 5：对边界 `x=4`，把上一步的树切成两棵。根 `5` 应去左树还是右树？既然根去右树，哪一侧子树完全不用递归？

<details><summary>展开：这正是 split 的递归方向</summary>

`5>4`，所以根和它的右子树（键都大于 5）一定属于右树；只有左子树可能混有 `≤4` 和 `>4` 的键，才需继续切。到 `4` 时，`4≤4`，它和左子树整体进入左树，继续切它的右子树。递归只沿一条可能跨边界的路径走。

</details>

## 问题动机：队伍既要有序，又要经常插队

动态有序多重集常问：插入/删除一个数、某数排名、第 $k$ 小、前驱后继。三个朴素选项各有一处疼：

| 结构 | 擅长 | 动态时的瓶颈 |
|---|---|---|
| 无序数组 | 末尾插入 | 排名、第 $k$ 小要扫描/排序 |
| 有序数组 | 二分、按下标取数 | 中间插删要搬很多元素 |
| 普通 BST | 按键走左/右 | 恶意或递增插入会变成链 |

![有序数组插入需要搬动尾部](../插图/11-平衡树/00-Treap-01-数组与退化树.svg)

我们希望像 BST 一样按键找位置，又希望树高不会总被输入顺序欺负。Treap 的做法非常俏皮：键 `key` 决定中序顺序，另发一张独立随机的优先级 `priority` 决定谁更靠近根。键管排队，优先级管谁坐树顶；两位领导分工，不抢麦。

## 步步式引导

### 1. 两条不变量如何同时存在

Treap 同时满足：

1. **BST 不变量**：左子树键不大于当前键，右子树键不小于当前键（重复值的精确约定必须全程统一）；
2. **堆不变量**：本讲取“大优先级在上”，父亲 `priority` 大于等于孩子。

给每个键独立随机优先级后，键的中序顺序固定，树形等同于这些键按优先级建出的笛卡尔树（Cartesian tree）。随机优先级让任一键出现在很深位置的概率很小，所以树高与随机 BST 同阶，期望 $O(\log n)$。

![键值保持中序、优先级决定树顶](../插图/11-平衡树/00-Treap-02-双不变量.svg)

这里“随机”只影响复杂度，不影响集合内容正确性。若随机源很差或面对能预测优先级的对手，树仍可能长歪；别把“期望”听成“永远不会翻车”。

### 2. 发明 `split`：按键把一棵树变成两棵

设 `split(root, x)` 返回 `(a,b)`，其中 `a` 所有键 `<=x`，`b` 所有键 `>x`。观察根：

- 若 `root.key<=x`，根和左子树必在 `a`；只需继续切右子树，把切出的左半接回 `root.right`；
- 否则根和右子树必在 `b`；只需继续切左子树，把切出的右半接回 `root.left`。

```text
split(root, x):
    if root is null: return (null, null)
    if root.key <= x:
        (middle, right) = split(root.right, x)
        root.right = middle
        pull(root)
        return (root, right)
    else:
        (left, middle) = split(root.left, x)
        root.left = middle
        pull(root)
        return (left, root)
```

你没有“重建”任何树，只改递归路径上的一条孩子指针。其余子树原封不动，BST 和堆性质仍成立。

### 3. 发明 `merge`：已排好前后关系的两棵树接回去

`merge(a,b)` 的前提是：`a` 所有键都不大于 `b` 所有键。谁应做根？优先级更高者。若 `a` 的根优先级更高，`a.left` 不动，只需把 `a.right` 和 `b` 继续合并；否则对称处理。

![split 先切开，merge 再按优先级接回](../插图/11-平衡树/00-Treap-03-分裂合并.svg)

```text
merge(a, b):
    if a is null: return b
    if b is null: return a
    if a.priority > b.priority:
        a.right = merge(a.right, b)
        pull(a)
        return a
    else:
        b.left = merge(a, b.left)
        pull(b)
        return b

pull(node):
    node.size = size(node.left) + node.count + size(node.right)
```

`pull` 每次孩子变动后立刻重算。它很朴素，却是排名和第 $k$ 小不会悄悄坏掉的账房先生。

### 4. 所有操作都变成“切、处理、接”

为了清晰处理重复值，这里令一个节点有 `count` 个相同键。插入/删除键 $x$ 时，先切出 `<x`、`=x`、`>x` 三块：

```text
(less, at_least) = split(root, x - 1)
(equal, greater) = split(at_least, x)

insert x:  equal.count += 1, or equal = new_node(x)
erase one x: if equal exists: equal.count -= 1; remove it if count becomes 0
root = merge(less, merge(equal, greater))
```

正式课会采用“重复值各建一个节点”的统一写法；两种方案都可以，但不要把 `count` 的 `size` 公式和“每个节点只算 1”混在一起。

## 纸上模拟：把“切、处理、接”写成可检查的流水线

下面不许只在脑中说“切一下”。仍从中序多重集 `[2,2,4,5,7]` 开始，执行 `insert(6)`。每一格先自己填，再核对。

| 阶段 | 你应写下的键集合 | 这一阶段允许改什么 | 需要保持什么 |
|---|---|---|---|
| 初始 |  | 无 | 中序有序、每个 `size` 正确 |
| `split(root,5)` | `less` / `at_least` | 递归路径的孩子指针 | `less≤5<at_least` |
| `split(at_least,6)` | `equal` / `greater` | 同上 | `equal=6`，其余大于 6 |
| 新建节点 |  | `count` 或新节点 | 新节点是合法单点 Treap |
| 两次 `merge` |  | 连接边与 `pull` | 左树键范围不越过右树 |

<details><summary>展开：插入 6 的完整账本</summary>

第一次切后 `less=[2,2,4,5]`、`at_least=[7]`；第二次切后 `equal=[]`、`greater=[7]`。新建 `6` 后，先合并 `6` 与 `[7]`，再合并 `[2,2,4,5]` 与结果。无论优先级使根具体长成什么样，中序必须是 `[2,2,4,5,6,7]`。每一处孩子指针改变后都调 `pull`，否则某个祖先仍误以为子树只有旧大小。

</details>

接着从 `[2,2,4,5,6,7]` 删除一个 `2`，并求第 3 小。请把这两个问题拆开：

1. 删除一个 `2` 时，三次切分后的 `equal` 里应有多少个元素？`count` 从几变成几？
2. 假设当前根为 `5`，左子树元素数为 3；第 3 小首先向哪边走？再假设左孩子为 `4`、它左子树大小为 2，第 3 小落在哪里？

<details><summary>展开：别跳过 size 的含义</summary>

`equal` 是一张 `key=2,count=2` 的卡；删一个后变成 `count=1`，不是把整张卡丢掉。第 3 小在根 `5` 处满足 $3\le left\_size$，先去左；在 `4` 处满足 $left\_size+1=3$，答案为 4。每次走向一侧，都是依据已被 `pull` 维护的“这一整块有多少元素”。

</details>

## 核心知识：每次递归都在维护哪些账

`split` 的返回值满足键范围分界；`merge` 的输入满足整体键序；二者只让高优先级根处在上方，因此保留堆序。每次改孩子后 `pull`，所以 `size` 始终等于子树元素总数。于是沿 `left_size` 走第 $k$ 小时，丢弃的元素数恰好正确，不会漏也不会重。

每个基本操作只沿一条期望对数高的递归路径走，故插入、删除、排名和第 $k$ 小期望 $O(\log n)$，空间 $O(n)$。若题目要求严格最坏 $O(\log n)$，要看红黑树、AVL 等确定性结构；FHQ Treap 不假装有这张证书。

## 实现指南

- 统一 `split` 边界：本篇是左边 `<=x`、右边 `>x`。若改成 `<x`/`>=x`，所有插删公式都要一起改。
- 节点编号/指针为 0 或 `None` 时，`size(空)=0`；每次改完 `left/right` 后再 `pull`。
- 随机优先级应使用质量较好的、独立的生成器；`rand()` 低位和固定可预测模式都不理想。
- `kth(k)` 前检查 $1\le k\le size(root)$；递归深度在极端退化时可能危险。
- 调试时打印中序序列（应有序）和每个节点优先级（父亲应不小于孩子）；两条不变量分开查，定位快很多。

## 互动小实验室

运行 [从排好队到会分身的树.py](../../互动程序/11-平衡树/00-从排好队到会分身的树.py)。程序先要求你预测有序数组的搬动和优先级根，再使用固定种子的随机优先级构建同一棵树；因此每次树形一致、便于复盘。启动日志会插入一组小数并打印 `split/merge/pull`；之后可以输入：

- `+ x` / `- x`：插入或删除一个整数；
- `rank x`：查询严格小于 `x` 的元素数加一；
- `k k`：查询第 `k` 小；
- `show`：打印侧着的树、中序序列和每个节点的 `size`。

建议先执行 `+ 6`，猜一猜它被切到哪一边；再 `- 2` 两次，观察重复值的 `count` 如何影响 `size`。树会“分身”只是指针改了归属，不会偷偷复制数据，放心玩。

## 扩展与联系

把 `split` 的依据从键改成子树大小，就得到下一节的隐式 Treap，可维护序列区间；给节点加 Lazy 标记可支持区间翻转。Splay 用旋转把最近访问点伸到根，适用思想不同；ODT 则依赖输入契约，不能当作平衡树的安全替代品。

## 总结与自检

1. `merge(a,b)` 为什么一定要先保证所有 `a` 的键不大于所有 `b` 的键？
2. `split` 时为什么只递归到一侧孩子？
3. `pull` 若漏调一次，第 $k$ 小为什么可能错误？
4. 随机优先级改变的是正确性还是复杂度保证？

<details><summary>自检答案</summary>

否则接回去会破坏 BST 中序；根和一整侧子树的归属已由键比较确定；祖先的 `size` 不再等于真实元素数；它不改变有序集合内容，只影响树高的期望界。

</details>

## 一周预热安排

- 第 1 天：比较有序数组插入和递增 BST 的形状。
- 第 2 天：给 4 个键随手发优先级，画出同时满足两条不变量的树。
- 第 3 天：手做一次 `split(root, x)`，在每一步标注左右键范围。
- 第 4 天：手做一次 `merge`，每次选择优先级更高的根。
- 第 5 天：运行互动程序并做插删、排名、第 $k$ 小；随后进入[FHQ Treap 正式课](01-FHQ-Treap按值分裂与顺序统计.md)。