📚 覆盖：第 14–20 讲 · 重点：题 4、6、8、12、15 是本单元的核心证明。

第一部分：二分查找（第 14 讲）

题 0（6 分）⭐

(a) 闭区间写法的循环条件为什么必须是 lo <= hi？写成 < 会漏掉什么？ (b) 给出一个会死循环的二分写法并指出根因。"lo = mid 配上取整"这条口诀为什么成立？ (c) 半开区间的 LowerBound 中，为什么是 hi = mid 而不是 hi = mid - 1？ (d) 只用 LowerBound 实现：存在性、前驱、后继、等于 x 的个数、[l,r] 内元素个数。 (e) 对"分割数组最小化最大段和"写出可行性判定，并证明它关于 cap 单调。 (f) 寻找峰值的数组并不有序，为什么还能二分？由此说说二分的真正前提。

第二部分：二叉搜索树（第 15 讲）

题 1（4 分）

(a) 有序字典比普通字典多了哪五类操作？各举一个真实场景。 (b) 下面这棵树满足"每个节点大于左孩子、小于右孩子"，它是 BST 吗？为什么？

        8
      ╱   ╲
    3      10
      ╲
       12

(c) 写出正确的 BST 验证函数。

题 2（5 分）

(a) 依次插入 [50, 30, 70, 20, 40, 60, 80]，画出结果树，写出中序遍历。 (b) 删除 50（有两个孩子），画出用后继替换和用前驱替换两种结果。 (c) 为什么后继一定没有左孩子？ (d) 总是用后继会带来什么长期问题？

题 3（4 分）

(a) 无右子树的节点如何求后继？说明它为什么正确。 (b) 按升序插入 n 个键会得到什么树？为什么这个输入模式在工程中很常见？举三个例子。

题 4（5 分）⭐

(a) 随机 BST 的期望高度是多少？期望节点深度呢？ (b) 为什么"随机 BST 期望 O(log n)“不足以让我们放心使用朴素 BST？给出三条理由。 (c) 随机 BST 的期望深度常数 1.39 与随机化快排的 1.39 为什么是同一个数？

第二部分：AVL 与红黑树（第 16–17 讲）

题 5（5 分）

(a) 证明旋转保持 BST 性质。 (b) 在 rotateRight(y) 中为什么必须先 update(y) 再 update(x)？ (c) 依次插入 [10, 20, 30, 40, 50, 25] 到 AVL 树，画出每步结果并标出旋转类型。

题 6（6 分）⭐

(a) 写出高度为 h 的 AVL 树的最小节点数 N(h) 的递推式。 (b) 说明它为什么是斐波那契数列，推出 h ≤ 1.44 log₂ n。 (c) 为什么 LR 情形不能用单旋修复？画图说明。 (d) 证明 AVL 插入后至多需要一次单旋或一次双旋。

题 7（4 分）

(a) 为什么 AVL 删除可能需要 O(log n) 次旋转而插入只需 O(1)？ (b) 红黑树的删除只需 ≤ 3 次旋转。这为什么让 Linux CFS 调度器选择红黑树？ (c) AVL 高度 1.44 log n vs 红黑树 2 log n，n = 10⁶ 时各是多少层？为什么实测差距不明显？

题 8（7 分）⭐

(a) 用 2-3-4 树的语言解释红黑树的五条规则，特别是规则 ④ 和 ⑤。 (b) 定义黑高，证明"以 x 为根的子树至少有 2^{bh(x)} − 1 个内部节点”。 (c) 由此推出 h ≤ 2 log₂(n+1)，指出用到规则 ④ 的地方。 (d) 新节点为什么总是染成红色？ (e) 用 2-3-4 树重述插入修复的三种情形。

题 9（4 分）

(a) 左倾红黑树加了什么额外约束？换来了什么、付出了什么？ (b) 手工执行 LLRB 依次插入 [S, E, A]，画出每步的树与颜色。 (c) LLRB 插入的三个 if 顺序为什么不能交换？

第三部分：B 树与外存（第 18 讲）

题 10（6 分）

(a) 外存模型与 RAM 模型的关键差别是什么？ (b) 存 10⁹ 条记录，红黑树和 B 树（t = 128）各需要几次磁盘 I/O？请算出来。 (c) 推导 B 树高度上界 h ≤ log_t((n+1)/2)。 (d) 半满约束保证了什么？没有它会怎样？

题 11（5 分）

(a) B 树插入为什么采用"向下时提前分裂满节点"而不是"插完向上修复"？ (b) B+ 树相对 B 树的两个改动分别解决什么问题？哪个对数据库更关键？ (c) 为什么用随机 UUID 做 InnoDB 主键是坏主意？ (d) 什么是回表？覆盖索引为什么能避免它？

题 12（5 分）⭐

(a) LSM 树用什么换什么？画出它的层级结构。 (b) 为什么 LSM 必须配布隆过滤器？ (c) 数据全在内存中，为什么 B 树可能仍优于红黑树？ (d) 为什么 Go 生态流行的有序 map 实现是 B 树而不是红黑树？

第四部分：随机化平衡（第 19 讲）

题 13（6 分）

(a) 跳表的期望层数、期望空间与 p 的关系是什么？p = 1/4 与 1/2 各有什么取舍？ (b) 用"倒着走查找路径"的方法推导期望查找代价 Θ(log n)。 (c) 为什么跳表比平衡树更容易做并发？举一个平衡树的具体困难。

题 14（6 分）

(a) 证明：给定互异的 key 与互异的 priority，Treap 的形状唯一。 (b) 为什么随机优先级的 Treap 等价于随机顺序插入的 BST？这个等价为什么重要？ (c) 写出 split 与 merge，说明如何在 O(log n) 内删除整个区间 [a, b)。 (d) 把 Treap 改成"按子树大小 split"能得到什么结构？

题 15（4 分）

(a) 伸展树的摊还 O(log n) 用什么势能函数？ (b) 什么是工作集性质？它在什么场景下有价值？ (c) “读操作也要写树"会造成什么问题？

第五部分：增强（第 20 讲）

题 16（8 分）⭐

(a) 增强方法论的四个步骤是什么？为什么第 3 步最关键？ (b) 判断以下增强信息是否可维护，说明理由：子树大小 / 子树键的和 / 子树的中位数 / 子树中不同值的个数 / 子树的最大右端点。 (c) 实现 Select(i) 时，进入右子树为什么要 i -= size(left) + 1？ (d) 区间树的查找每步只走一个方向，证明它不会漏掉重叠区间（分两种情形）。 (e) 树状数组的 i & (-i) 是什么？为什么 Sum 只循环 O(log n) 次？ (f) 为什么树状数组不能直接求区间最大值而线段树可以？

参考解答

题 0

(a) 闭区间 [lo, hi] 在 lo == hi 时仍含一个元素，必须检查。写成 < 会在区间缩到单个元素时直接退出，漏掉它——这是最常见的二分 bug。

(b)

for lo < hi {
    mid := lo + (hi-lo)/2   // 下取整
    if a[mid] < x { lo = mid + 1 } else { lo = mid }  // ✗
}

当 hi == lo+1 时 mid == lo，走 lo = mid 分支区间不缩小 ⟹ 死循环。根因永远是某个分支没让区间严格变小。 口诀成立的理由：lo = mid 意味着 mid 可能是答案、不能排除，此时若 mid 取下界就可能等于 lo 而原地踏步；上取整保证 mid > lo，于是 lo = mid 必然前进。对称地 hi = mid 需要 mid < hi，即下取整。

(c) 半开区间 [lo, hi) 中 hi 是"第一个被排除的位置”。a[mid] >= x 时 mid 本身仍是候选答案，不能排除，故收缩到 hi = mid（区间变成 [lo, mid)，mid 之后的都排除，mid 保留在下一轮的候选边界上）。

(d)

i := LowerBound(a, x)
存在性：        i < len(a) && a[i] == x
前驱(< x)：     i-1（i > 0 时）
后继(> x)：     UpperBound(a, x)
等于 x 的个数： UpperBound(a,x) - LowerBound(a,x)
[l,r] 内个数：  UpperBound(a,r) - LowerBound(a,l)

(e) 判定：贪心地从左往右装，装不下就开新段，统计段数 segs，可行 ⟺ segs <= k 且 max(a) <= cap。

单调性证明：设 cap 可行，取 cap′ > cap。原来满足"段和 ≤ cap"的分割方案，其每段和也 ≤ cap′，故该方案在 cap′ 下依然可行，段数不变 ≤ k。∎ 于是可行性序列形如 F…F T…T，可二分。

(f) 因为二分只需要一个能安全排除一半的判据，不需要全局有序。a[mid] < a[mid+1] 时处于上坡，右侧必存在峰值（要么一路升到边界成为峰，要么中途下降形成峰）；反之左侧（含 mid）必有峰。⭐ 二分的真正前提是"能安全排除一半"，而非"有序"。

题 1

(a) Min/Max（排行榜首位）、Predecessor/Successor（时间序列的前一条记录）、RangeQuery（WHERE age BETWEEN 20 AND 30）、有序遍历（ORDER BY）、Rank/Select（“我排第几名"“第 100 名是谁”）。

(b) 不是 BST。12 位于 8 的左子树中，但 12 > 8，违反了"左子树所有键 ≤ 根"这一全局条件。BST 性质是递归的、涉及整棵子树，不是父子间的局部条件。

(c) 传递上下界：

func check(x *Node, lo, hi int) bool {
    if x == nil { return true }
    if x.Key <= lo || x.Key >= hi { return false }
    return check(x.Left, lo, x.Key) && check(x.Right, x.Key, hi)
}

题 2

(a)

            50
          ╱    ╲
        30      70
       ╱  ╲    ╱  ╲
      20  40  60   80
中序：20 30 40 50 60 70 80

(b) 用后继 60 替换 ⟹ 根变 60；用前驱 40 替换 ⟹ 根变 40。两者都合法。

(c) 后继是 minimum(z.Right)，即右子树中最小的节点。若它有左孩子，那个左孩子会更小，与"最小"矛盾。

(d) 总是从右子树取后继会让树逐渐向左倾斜。经典的 Hibbard 删除问题：反复随机插入删除后，树高会从 Θ(log n) 恶化到 Θ(√n)。缓解办法是随机选择前驱或后继。

题 3

(a) 向上回溯，直到某个祖先 p 满足"当前节点是 p 的左孩子”，p 就是后继。正确性：中序遍历中，访问完 x 及其整棵子树后，下一个访问的正是"x 所在的最近一个左子树的父节点"。

(b) 得到一条右斜链（退化成链表），高度 n−1，所有操作 Θ(n)。常见场景：① 按时间戳插入日志；② 按自增 ID 从数据库批量导入；③ 从已排序文件建索引。朴素 BST 恰好在最常见的输入模式下退化。

题 4

(a) 期望高度约 4.311·ln n ≈ 2.99 log₂ n；期望节点深度约 2 ln n ≈ 1.39 log₂ n。⚠️ 两个常数都是以自然对数给出的，换算成 log₂ 时要乘 ln2 ≈ 0.693，别把 4.311 直接当成 log₂ 的系数。

(b) ① 真实输入不是随机排列（有序、近乎有序、周期性是常态）；② 删除破坏随机性——Hibbard 删除后树不再是随机 BST，高度退化到 Θ(√n)；③ “期望"这里是对输入分布的假设，不是算法自带的保证（对比第 4 讲中"期望"与"平均情况"的区别）。

(c) 因为随机 BST 的构建过程与随机化快排的划分过程是同构的：BST 的根 ↔ 快排的主元，左右子树 ↔ 两侧递归。同一个随机过程，自然给出同一个常数。

题 5

(a) 旋转前后中序遍历序列不变（α x β y γ），而"中序序列有序"等价于 BST 性质，故性质保持。

(b) 因为 update 依赖孩子的高度。旋转后 y 变成了 x 的孩子，必须先算出 y 的新高度，x 的高度才能算对。顺序颠倒会让 x 用到 y 的旧高度。

(c)

插入 10, 20     ⟹  10—20（右斜）
插入 30         ⟹  RR 失衡，左旋 10  ⟹  20 为根，左 10 右 30
插入 40         ⟹  平衡
插入 50         ⟹  30 处 RR 失衡，左旋 30  ⟹  20 为根，右子树 40（左 30 右 50）
插入 25         ⟹  20 处 RL 失衡（右-左）：先右旋 40，再左旋 20
                    ⟹ 30 为根，左 20（右 25），右 40（右 50）

题 6

(a) N(0)=1, N(1)=2, N(h) = 1 + N(h−1) + N(h−2)。

(b) 这与斐波那契同构：可证 N(h) = F(h+3) − 1。由 F(k) ≈ φ^k/√5：

n ≥ φ^{h+3}/√5 − 1  ⟹  h ≤ log_φ(√5(n+1)) − 3 ≈ 1.4405 log₂ n + O(1)

(c) LR 情形下 z 的左孩子 y 是"右重"的。直接右旋 z 后，y 的右子树（含 x）成为 z 的左子树，高度关系没有改善，仍然失衡。必须先左旋 y 把 x 提上来，转成 LL 形态，再右旋 z。

(d) 插入前 z 子树高 h+1，插入后 h+2（失衡）。旋转后子树高度恢复为 h+1——与插入前相同，因此 z 的所有祖先看到的子树高度没变，不可能再失衡。故至多一次修复。∎

题 7

(a) 删除后旋转可能使子树高度减少 1（而插入后旋转是恢复到原高度）。高度变化会传播到父节点，导致祖先也可能失衡，需一路修复到根。

(b) CFS 是极端修改密集的负载：每次时间片结束都要取最小、更新 vruntime、重新插入。红黑树"删除 ≤ 3 次旋转"极有价值（重染色只是写一个位，远比旋转便宜）；而查找慢一点无关紧要——内核额外缓存了最左节点指针，取最小是 O(1)。

(c) AVL 约 29 层（1.44×20），红黑树约 40 层。实测差距不明显是因为两者都远超缓存容量，真正的瓶颈是每层一次缓存未命中，29 次和 40 次未命中的差别远小于理论上的比例暗示。这正是 B 树存在的理由。

题 8

(a)

• ① 红 = “与父节点同属一个 2-3-4 节点”
• ② 根是黑：根所在 2-3-4 节点的代表
• ③ nil 哨兵黑：统一边界处理
• ④ 无连续红：一个 2-3-4 节点最多 3 个键（2 条红边），且不能串成链
• ⑤ 黑高相同：⭐ 对应 2-3-4 树"所有叶子同深度”——黑节点数就是 2-3-4 树的高度

(b) 对高度归纳。叶子时 bh = 0，节点数 0 = 2⁰−1 ✓。否则 x 的每个孩子黑高为 bh(x) 或 bh(x)−1，由归纳假设各至少 2^{bh(x)−1}−1 个：

节点数 ≥ 2(2^{bh(x)−1} − 1) + 1 = 2^{bh(x)} − 1                ∎

(c) 由规则 ④（无连续红），根到叶路径上红节点数 ≤ 黑节点数，故 bh(root) ≥ h/2。代入 (b)：n ≥ 2^{h/2} − 1 ⟹ h ≤ 2log₂(n+1)。∎

(d) 插红色只可能破坏规则 ④（连续红），不会破坏规则 ⑤（黑高）。插黑色则一定破坏黑高。破坏一条比破坏两条容易修。

(e)

• 情形 1（叔叔红） = 目标 2-3-4 节点已是 4-节点 ⟹ 分裂，中间键升到父节点 ⟹ 问题上移两层
• 情形 2、3（叔叔黑） = 目标是 2-节点或 3-节点 ⟹ 就地吸收，变成 3-节点或 4-节点，不向上传播

题 9

(a) 额外约束：红链接只能是左链接。换来了插入修复只需三个 if（代码量减到标准红黑树的约 1/5）；付出：删除仍需 moveRedLeft/Right 等辅助操作，且树略高于标准红黑树。

(b)

插入 S：      S(黑，根)
插入 E：      S(黑)，左孩子 E(红)
插入 A：      E—A 连续左红 ⟹ 右旋 S ⟹ E(黑) 左 A(红) 右 S(红)
              ⟹ 左右都红 ⟹ flipColors ⟹ E(红→根置黑) 左 A(黑) 右 S(黑)

(c) 顺序有严格语义：① 先把右倾红链接转成左倾（保证形态规范）；② 再处理连续左红（把它平衡成 4-节点）；③ 最后分裂满节点。打乱顺序会让某些形态无法被后续的 if 识别。

题 10

(a) RAM 假设所有内存访问代价相同；外存模型以块（大小 B） 为传输单位，代价 = 块传输次数，CPU 计算免费。因此"读 1 字节"和"读 B 字节"代价相同。

(b) 红黑树 2 log₂ 10⁹ ≈ **60** 次；B 树（t=128，每节点约 250 键）log₂₅₀ 10⁹ ≈ **4** 次。且根与第二层通常已缓存，实际磁盘 I/O 约 1–2 次。

(c) 深度 i 的节点至少 2t^{i−1} 个（根至少 2 个孩子，其余至少 t 个）：

n ≥ 1 + (t−1)Σ_{i=1}^{h} 2t^{i−1} = 2t^h − 1  ⟹  h ≤ log_t((n+1)/2)

(d) 半满约束保证每个节点至少有 t 个孩子，从而树高是 log_t n。没有它，节点可以只有 1 个键，树会退化成链。

题 11

(a) “提前分裂"使插入变成单趟向下（single pass），不需要回溯。对磁盘结构至关重要——回溯意味着重新读已写出的块。

(b) ① 数据只存叶子：内部节点纯索引，扇出更大、树更矮；② 叶子链表相连：范围查询变成顺序 I/O。第二个对数据库更关键，因为绝大多数查询是范围查询，而顺序 I/O 比随机 I/O 快两个数量级。

(c) 随机 UUID 使插入位置随机分布，导致大量页分裂和碎片；自增 ID 让插入总在最右侧叶子，几乎不分裂。另外 UUID 更长，会让所有二级索引变大（二级索引叶子存主键）。

(d) 二级索引叶子只存主键，按二级索引查询后需要再查一次聚簇索引拿完整行，这叫回表。若查询需要的列全部包含在二级索引中（覆盖索引），就不用回表。

题 12

(a) 用读放大换顺序写。结构：MemTable（内存跳表）→ 写满冻结、顺序刷盘成 SSTable → 后台 compaction 逐层归并，每层容量 ×10。

(b) 一次查询可能要检查多个层的多个 SSTable。布隆过滤器让"这个 key 一定不在这个 SSTable 里"的判断变成 O(k) 的内存操作，避免无谓的磁盘读——这是把读放大压下来的关键手段。

(c) 内存也有块结构（缓存行 64 B、页 4 KB）。B 树节点占几条缓存行，节点内的顺序比较是缓存友好的；红黑树每层一次指针追逐、一次缓存未命中。实测 B 树常快 2–3 倍。

(d) 同上——缓存表现更好，且实现比红黑树简单得多、更容易写对。红黑树的位置是内核和标准库（那里有人已经写对了）。

题 13

(a) 期望层数 1/(1−p)；期望空间 n/(1−p) 个指针。p = 1/2 时层数 2、空间 2n、查找步数少；p = 1/4 时层数 1.33、空间 1.33n（比红黑树的 2n 还省），代价是每层要多走几步。Redis 用 0.25。

(b) 倒着走查找路径：在任意位置，路径要么向左（该节点在这层继续存在，概率 p），要么向上（概率 1−p）：

C(k) = (1−p)(1+C(k−1)) + p(1+C(k))  ⟹  C(k) = k/(1−p)

层数 Θ(log n) ⟹ 期望查找 Θ(log n)。

(c) 跳表的修改只影响局部指针（每层做一次链表插入），容易做无锁或细粒度锁。平衡树的旋转会重构整棵子树的结构，并发时必须锁住整棵子树，且旋转期间树处于不一致状态，读者可能看到错误结构。

题 14

(a) 优先级最大的必须是根（堆性质），其余节点按 key 与根比较唯一地分到左右子树（BST 性质），对两棵子树递归即可。归纳得形状唯一。∎

(b) 优先级的大小顺序就相当于插入顺序（优先级最大 = 最先插入 = 成为根）。因此随机优先级 ↔ 随机插入序列。重要性：随机 BST 的期望高度 O(log n) 这个结论可以直接搬过来，且与 key 的实际插入顺序无关——把"输入是随机的"这个我们控制不了的假设，换成了"随机优先级"这个我们完全控制的东西。

(c) 见第 19 讲。删除区间 [a,b)：split(t, a) 得 (L, M)，split(M, b) 得 (Mid, R)，丢掉 Mid，merge(L, R)。三次 O(log n) 操作。

(d) 得到一个支持 O(log n) 随机访问 + O(log n) 任意位置插入删除的序列结构——即 rope，文本编辑器用它。这解决了数组（插入 O(n)）和链表（访问 O(n)）各自的缺陷。

题 15

(a) Φ = Σ_v log(size(v))（所有节点的子树大小的对数之和）。

(b) 最近访问过的元素下次访问更快（因为被转到了根附近）。在访问有局部性时（80/20 分布），实际性能可以优于任何静态平衡树——缓存、词法分析器、路由表都有这个特点。

(c) ① 并发极不友好：读操作也修改结构，无法用读写锁并发读；② 只读缓存场景失效：本以为是只读的操作会产生写放大（脏页、cache line 失效）；③ 多线程下需要全局锁。

题 16

(a) ① 选基础结构；② 确定额外信息；③ 验证信息能由孩子的信息 O(1) 推出；④ 实现新操作。第 3 步最关键，因为它是"可维护性定理"的前提——满足它才能保证插入、删除、旋转后都能在 O(log n) 内维护，不改变原有复杂度。

(b)

(c) 因为进入右子树后，“第 i 小"的语义要相对于右子树重新计数。左子树的所有节点（size(left) 个）加上当前节点（1 个）都排在右子树之前，所以要减掉。

(d)

• 情形 A（走左，因 x.Left.Max ≥ lo）：设左子树中右端点最大的区间是 j。若 j 与 [lo,hi] 不重叠，由 j.high ≥ lo 必有 j.low > hi。BST 性质保证右子树中所有区间的 low ≥ x.low ≥ j.low > hi，右子树全部不可能重叠 ✓
• 情形 B（走右）：左子树中所有区间的 high ≤ x.Left.Max < lo，全部结束于 lo 之前，不可能重叠 ✓ ∎

(e) i & (-i) 是 i 的最低位的 1（lowbit）。Sum 每次 i -= lowbit(i) 剥掉一个最低位的 1，而 i 的二进制中最多有 log₂ i 个 1，故循环 O(log n) 次。

(f) 树状数组的 RangeSum(l,r) = Sum(r) − Sum(l−1) 依赖减法（逆元），而 max 没有逆元——知道 max[1..r] 和 max[1..l−1] 推不出 max[l..r]。线段树的每个节点直接存对应区间的聚合值，查询时把区间拆成 O(log n) 个节点区间再合并，只要运算满足结合律即可。