第 12 章二叉搜索树 (Binary Search Trees)

核心结论

BST 性质：每个节点 x.key 大于左子树所有键、小于右子树所有键——递归定义；inorder 遍历产生有序序列。
基本操作：SEARCH / MINIMUM / MAXIMUM / SUCCESSOR / PREDECESSOR / INSERT / DELETE——都 \(O(h)\)，h = 树高。
插入 vs 删除：插入简单（沿根下降到第一个 NIL 接上）；删除复杂——三种情形：无子节点、单孩子、双孩子。
树高分析：高度 = \(\Theta(\lg n)\) 当树平衡；最坏 = n（链状）；期望 = \(O(\lg n)\)（随机插入）。
随机 BST 的高度：定理 12.4——随机插入 n 个不同键的期望高度 \(O(\lg n)\)；用指示变量 + 指数高度 + Jensen 不等式证明。
BST 作为字典 vs 优先级队列：SEARCH / INSERT / DELETE / MIN / SUCCESSOR / PREDECESSOR 全部 \(O(h)\)——既是有序字典也可作优先级队列。

本章主旨

本章是「搜索树数据结构」的开端——BST 是后续所有平衡搜索树（红黑树、B 树、AVL 树、treap、跳表）的基础。本章四节：(1) §12.1 定义 BST 与中序遍历；(2) §12.2 查询操作（SEARCH / MIN / MAX / SUCCESSOR / PREDECESSOR）——展示 BST 作为「有序字典」的力量；(3) §12.3 插入 / 删除——展示 BST 作为「动态集合」；(4) §12.4 随机 BST 高度分析——证明「平均 O(lg n)」。本章所有操作时间都用「O(h)」而非「O(lg n)」——因为基本 BST 不是平衡的；下一章的红黑树给出「保证 lg n」的变种。

一、核心概念

本章围绕 4 个核心概念展开：从 BST 的定义与性质开始，引入查询操作（SEARCH / MIN / MAX / SUCCESSOR）、插入与删除，最后分析随机 BST 的期望高度。

概念	定义 + 重要性	实现提示
BST 性质与遍历	节点 x 的左子树所有键 ≤ x.key，右子树所有键 ≥ x.key；中序遍历产生有序序列。	§12.1；INORDER-TREE-WALK 递归：左 → 根 → 右；时间 Θ(n)，用代入法证明。
查询操作 (SEARCH / MIN / MAX / SUCC)	SEARCH 沿树根向下比较；MIN / MAX 沿最左 / 最右路径；SUCCESSOR 两种情形——有右子树则取右子树最小；否则沿父指针上溯到第一个「是某祖先左孩子」的节点。	§12.2；所有查询 \(O(h)\)；ITERATIVE-TREE-SEARCH 用 while 循环代替递归（更高效）。
插入与删除	TREE-INSERT 沿查找路径下降到 NIL 接入新节点；TREE-DELETE 用 TRANSPLANT 子程序处理三种情形：no children、one child、two children（后者用 SUCCESSOR 替换）。	§12.3；TRANSPLANT 是关键工具；TREE-DELETE 用「splice successor」处理双孩子情形——比「copy successor’s data」更安全（不会让外部指针失效）。
随机 BST 高度 (定理 12.4)	随机插入 n 个不同键（每种 n! 排列等概率）→ 期望树高 = \(O(\lg n)\)；用指数高度 \(Y_n = 2^{X_n}\) 分析 + Jensen 不等式。	§12.4；E[Y_n] = (1/4)·C(n+3,3) ≤ n³ ⇒ E[X_n] = O(lg n)。

概念

定义 + 重要性

实现提示

BST 性质与遍历

节点 x 的左子树所有键 ≤ x.key，右子树所有键 ≥ x.key；中序遍历产生有序序列。

§12.1；INORDER-TREE-WALK 递归：左 → 根 → 右；时间 Θ(n)，用代入法证明。

查询操作 (SEARCH / MIN / MAX / SUCC)

SEARCH 沿树根向下比较；MIN / MAX 沿最左 / 最右路径；SUCCESSOR 两种情形——有右子树则取右子树最小；否则沿父指针上溯到第一个「是某祖先左孩子」的节点。

§12.2；所有查询 \(O(h)\)；ITERATIVE-TREE-SEARCH 用 while 循环代替递归（更高效）。

插入与删除

TREE-INSERT 沿查找路径下降到 NIL 接入新节点；TREE-DELETE 用 TRANSPLANT 子程序处理三种情形：no children、one child、two children（后者用 SUCCESSOR 替换）。

§12.3；TRANSPLANT 是关键工具；TREE-DELETE 用「splice successor」处理双孩子情形——比「copy successor’s data」更安全（不会让外部指针失效）。

随机 BST 高度 (定理 12.4)

随机插入 n 个不同键（每种 n! 排列等概率）→ 期望树高 = \(O(\lg n)\)；用指数高度 \(Y_n = 2^{X_n}\) 分析 + Jensen 不等式。

§12.4；E[Y_n] = (1/4)·C(n+3,3) ≤ n³ ⇒ E[X_n] = O(lg n)。

二、详细笔记

12.1 BST 定义与中序遍历

What：二叉搜索树是递归定义的有序数据结构——节点的左子树所有键 ≤ x.key、右子树所有键 ≥ x.key。

Why：BST 把「链表的有序性」与「树的二分查找」结合——既能二分查找（O(h)），又支持动态集合的所有操作。

How：

结构定义（§12.1）：每个节点是带 left / right / p 指针的对象；NIL 表示空孩子/父；根节点的 p = NIL。
BST 性质：设 y 在 x 的左子树 → y.key ≤ x.key；y 在 x 的右子树 → y.key ≥ x.key。递归地应用于每个节点。
中序遍历（INORDER-TREE-WALK, §12.1）：

\[\begin{array}{rl} & \textbf{INORDER-TREE-WALK}(x) \\ 1 & \textbf{if } x \neq \text{NIL} \\ 2 & \quad \textbf{INORDER-TREE-WALK}(x.\text{left}) \\ 3 & \quad \textbf{print } x.\text{key} \\ 4 & \quad \textbf{INORDER-TREE-WALK}(x.\text{right}) \end{array}\]

中序遍历产生有序序列（由 BST 性质归纳证）。
复杂度（定理 12.1）：T(n) = T(k) + T(n-k-1) + d（k = 左子树大小）→ 用代入法 T(n) ≤ (c+d)n + c = O(n)。

When：

「有序遍历」需要 → BST（相较散列表的根本优势）。
「中序 + 范围查找 + SUCCESSOR」 → BST 优于散列。
单纯「查找 / 插入 / 删除」无序字典 → 散列表（O(1) vs BST O(h)）。

Example：图 12.1(a) 是一棵平衡的 BST h=2：(key=6) 根；左 (key=2) → 右 (key=5) → 左 (key=5)；右 (key=7) → 右 (key=8)。中序遍历：2 → 5 → 5 → 6 → 7 → 8。中序遍历输出有序——前提是允许重复键（左 ≤ / 右 ≥）。

12.2 查询操作（SEARCH / MIN / MAX / SUCCESSOR / PREDECESSOR）

What：BST 作为「有序字典」的核心能力——五大查询操作。

Why：这些操作的存在让 BST 比散列表更强大——能回答「下一个更大元素」「最小 / 最大」「有序遍历」。

How：

SEARCH（§12.2）：

\[\begin{array}{rl} & \textbf{TREE-SEARCH}(x, k) \\ 1 & \textbf{if } x == \text{NIL } \textbf{ or } k == x.\text{key} \\ 2 & \quad \textbf{return } x \\ 3 & \textbf{if } k < x.\text{key} \\ 4 & \quad \textbf{return } \textbf{TREE-SEARCH}(x.\text{left}, k) \\ 5 & \textbf{else } \textbf{return } \textbf{TREE-SEARCH}(x.\text{right}, k) \end{array}\]

或迭代版（更高效，常用 while 循环）。
MIN / MAX（§12.2）：TREE-MINIMUM(x) 沿 left 走到 NIL；TREE-MAXIMUM(x) 沿 right 走到 NIL；时间 O(h)。
SUCCESSOR（§12.2）：

\[\begin{array}{rl} & \textbf{TREE-SUCCESSOR}(x) \\ 1 & \textbf{if } x.\text{right} \neq \text{NIL} \\ 2 & \quad \textbf{return } \textbf{TREE-MINIMUM}(x.\text{right}) \\ 3 & y = x.\text{p} \\ 4 & \textbf{while } y \neq \text{NIL } \textbf{ and } x == y.\text{right} \\ 5 & \quad x = y \\ 6 & \quad y = y.\text{p} \\ 7 & \textbf{return } y \end{array}\]

两种情形：
- x 有右子树 → 后继是右子树的最小节点。
- x 无右子树 → 后继是「向上回溯到第一个是其父节点左孩子的祖先」(练习 12.2-6)。 PREDECESSOR 类似（对称）。
复杂度定理 12.2：所有查询 O(h)（最坏路径长度）。

When： . 「有序遍历 / 范围查询 / 找最大或最小」 → 用中序遍历 + SUCCESSOR。 . 「找第 i 小」 → 在第 14 章用 OS-tree 增强为 O(lg n)。 . 「找最近公共祖先」 → 在第 21 章用 LCA 算法；本章 BST 是其基础。

Example（SUCCESSOR, 图 12.2）： * 节点 15 的后继：右子树非空 → 右子树最小 = 17。 * 节点 13 的后继：右子树空 → 向上回溯，遇到「13 是 7 的右孩子 / 7 是 6 的右孩子 / 6 是 15 的左孩子」 → 15 是 13 的后继。

12.3 插入与删除

What：TREE-INSERT 沿 SEARCH 路径下降到第一个 NIL 接入新节点；TREE-DELETE 用 TRANSPLANT 子程序处理 0/1/2 个孩子的情形。

Why：BST 的「动态集合」能力——INSERT 与 SEARCH 同模式（下降到 NIL），DELETE 复杂因需要重组树。

How：

TREE-INSERT（§12.3）：

\[\begin{array}{rl} & \textbf{TREE-INSERT}(T, z) \\ 1 & y = \text{NIL} \\ 2 & x = T.\text{root} \\ 3 & \textbf{while } x \neq \text{NIL} \\ 4 & \quad y = x \\ 5 & \quad \textbf{if } z.\text{key} < x.\text{key} \\ 6 & \quad\quad x = x.\text{left} \\ 7 & \quad\textbf{else } x = x.\text{right} \\ 8 & z.\text{p} = y \\ 9 & \textbf{if } y == \text{NIL } \\ 10 & \quad T.\text{root} = z \\ 11 & \textbf{elseif } z.\text{key} < y.\text{key} \\ 12 & \quad y.\text{left} = z \\ 13 & \textbf{else } y.\text{right} = z \end{array}\]

时间为 O(h)：沿 SEARCH 路径下降到 NIL。
TRANSPLANT 子程序（§12.3）：用 v 替换 u 作为父节点的孩子；处理 v = NIL 的情况（替换为 NIL）。
TREE-DELETE（§12.3，图 12.4）：

\[\begin{array}{rl} & \textbf{TREE-DELETE}(T, z) \\ 1 & \textbf{if } z.\text{left} == \text{NIL} \\ 2 & \quad \textbf{TRANSPLANT}(T, z, z.\text{right}) \\ 3 & \textbf{elseif } z.\text{right} == \text{NIL} \\ 4 & \quad \textbf{TRANSPLANT}(T, z, z.\text{left}) \\ 5 & \textbf{else } y = \textbf{TREE-MINIMUM}(z.\text{right}) \\ 6 & \quad \textbf{if } y.\text{p} \neq z \\ 7 & \quad\quad \textbf{TRANSPLANT}(T, y, y.\text{right}) \\ 8 & \quad\quad y.\text{right} = z.\text{right} \\ 9 & \quad\quad y.\text{right}.\text{p} = y \\ 10 & \quad \textbf{TRANSPLANT}(T, z, y) \\ 11 & \quad y.\text{left} = z.\text{left} \\ 12 & \quad y.\text{left}.\text{p} = y \end{array}\]

四种情形：
- z 无左孩子：用 z.right 替换 z。
- z 无右孩子：用 z.left 替换 z。
- z 两个孩子，且后继 y 是 z 的右孩子：直接用 y 替换 z（y.left = z.left）。
- z 两个孩子，后继 y 在 z 的右子树深处：先 splice y（用 y.right 替换 y），再用 y 替换 z。
复杂度定理 12.3：TREE-INSERT / TREE-DELETE 都 O(h)。

When： . 「用后继替换」是删除标准做法——保证 BST 性质维持。 . 「Copy 后继数据」是另一种实现（更简单但可能让外部指针失效——见章末 chapter notes）。

Example（图 12.3）：插入 13 到树（含 15, 6, 7, 17, …）：SEARCH 13 从 18 → … → 到 NIL 位置（在 7 的右孩子处），插入为 7.right = 13，13.p = 7。

12.4 随机构建 BST 的高度分析

What：分析随机插入 n 个不同键（每种 n! 排列等概率）所建 BST 的期望高度，证明 = O(lg n)。

Why：BST 的所有操作是 O(h)，最坏 h = n（链）；若能证明随机建树时 h = O(lg n)（期望），则基本操作平均 Θ(lg n)——与下一章平衡树的最坏 Θ(lg n) 形成对照。

How：

随机 BST 的定义：n 个键按随机顺序插入初始空树；等价于从 n! 排列中等概率选一个。
分析（定理 12.4 证明）：
- 设 Rn = 根的秩（1 ≤ Rn ≤ n 各等概率）。
- 设 Yn = 2^{Xn}（指数高度），X1 = 0（Y1 = 1），X0 = -∞。
- 分解：Yn = 2 · max(Y_{Rn-1}, Y_{n-Rn})。
- 指示变量 Zn,i = I{Rn = i}；E[Zn,i] = 1/n。
- 独立性：Zn,i 与 Y_{Rn-1} 和 Y_{n-Rn} 独立。
- 期望：
  
  \[E[Y_n] \leq \frac{2}{n} \sum_{i=1}^{n} (E[Y_{i-1}] + E[Y_{n-i}]) = \frac{4}{n} \sum_{i=0}^{n-1} E[Y_i] \quad \text{(式 12.2)}\]
- 用代入法证明 E[Yn] ≤ (1/4) · C(n+3, 3) ≤ n³。
- 验证：代入上式得右侧 = 1/n · C(n+3, 4) = 1/n · (n+3)!/(4!(n-1)!) = (1/4) · (n+3)!/(3!n!) = (1/4)·C(n+3,3)。
- f(x) = 2^x 是凸函数，用 Jensen 不等式：2^{E[X_n]} ≤ E[2^{X_n}] = E[Y_n] = O(n³) → E[X_n] = O(lg n)。
复杂度：证明用了「randomly built BST」定义——单纯按随机顺序插入；不适用于「随机 BST」（所有 BST 等概率，练习 12.4-3 证明两者不同）。

When： . 「实践用 BST」→ 红黑树（确定性 O(lg n)），不依赖输入分布。 . 「随机插入」场景 → 期望 O(lg n) 足够（如 quickselect 后的结果）。 . 「最坏 O(lg n)」必须 → 红黑树 / AVL / 跳表。

Example（直觉）：BST h 期望 = O(lg n) 类似 quicksort 期望 nlgn 同样基于「随机选 pivot / 随机插根」——根选大值概率 1/n 导致不平衡，但概率低、对期望影响小。

三、关键图表

本章无独立编号图表

本章核心图（图 12.1-12.4）以「节点 + 指针箭头」展示 BST 的查询路径、插入位置、删除的四种情况。本笔记以伪代码 + 文字描述 + 复杂度公式呈现；原书图见 CLRS 第 4 版第 287-298 页。

核心公式对照表

式编号

内容

BST 性质

x.left ≤ x.key ≤ x.right（递归）

INORDER-TREE-WALK 时间

Θ(n)

TREE-SEARCH 时间

O(h)

定理 12.2

SEARCH / MIN / MAX / SUCCESSOR / PREDECESSOR 都 O(h)

TREE-INSERT 时间

O(h)

TRANSPLANT 时间

O(1)

TREE-DELETE 时间

O(h)

定理 12.3

INSERT / DELETE 都 O(h)

随机 BST 期望高度

O(lg n)（定理 12.4）

式 12.1

E[Zn,i] = 1/n

式 12.2

E[Yn] ≤ (4/n) · Σ_{i=0}^{n-1} E[Yi]

式 12.3

Σ_{i=0}^{n-1} C(i+3, 3) = C(n+3, 4)

E[Yn] 上界

(1/4) · C(n+3, 3) ≤ n³

Jensen 不等式

2^{E[X_n]} ≤ E[2^{X_n}] = E[Y_n]

四、思维导图

mindmap
  root((第 12 章 二叉搜索树))
    BST性质
      递归有序
      中序遍历
      Θ(n)
    查询
      SEARCH
      MIN/MAX
      SUCCESSOR
      PREDECESSOR
      O(h)
    插入
      沿路径下降
      O(h)
    删除
      0孩子
      1孩子
      2孩子用SUCCESSOR
      TRANSPLANT
      O(h)
    高度分析
      最坏n
      随机O(lg n)
      指数高度
      Jensen不等式
    角色
      字典
      优先级队列
      有序集合

五、重点与易错点

BST 所有操作 O(h) 而非 O(lg n) — 基本 BST 不是平衡的，h 最坏 n；平均 O(lg n)；第 13 章红黑树给出最坏 O(lg n)。
TREE-SEARCH 优先用迭代版 — 迭代无栈开销，多数编译器生成代码更高效。
SUCCESSOR 两种情形缺一不可 — 有右子树用 min(right)；否则向上回溯。常见错误是「忘了无右子树的情形」。
TREE-DELETE 中「把后继数据复制到 z 再删后继」是错误实现 — 容易让外部指向 z 的指针失效（指向已删除节点）；CLRS 第 4 版改用 splice 方式删除 z 本身。
TREE-DELETE 情形 (c) vs (d) 的区分 — (c) 是后继 = z.right，直接替换；(d) 是后继在更深处，需要先 splice 后继再用之替换。
SUCCESSOR 在「键重复」时的定义 — 与无重复时不同；左 ≤ / 右 ≥ 的 BST 性质使中序遍历先出现于左，最终给定定义。
BST 与最小堆的性质不同 — BST 左 ≤ 根 ≤ 右；最小堆仅根 ≤ 孩子（不约束左右大小关系）；不能用最小堆做中序有序。
BST 不能用最小堆代替 O(lg n) 排序 — 最小堆查找任意值是 O(n)；BST 查找 = O(h)。
BST 排序的成本 — 插入 n 个元素建 BST = Θ(n²) 最坏；随机建树期望 = Θ(n lg n)；最佳 = 已排序输入 = Θ(n)（退化为链表）。
「随机 BST」与「randomly built BST」不同（练习 12.4-3）— 后者按随机顺序插入；前者要求所有 n 节点 BST 等概率——后者是本章定义。
E[Yn] = O(n³) 而不是 O(n²) — 看似松，但代入法只要求 (1/4)·C(n+3,3) ≤ n³/(24/24) 这个界；Jensen 把立方转化为 lg 上界。
BST 不支持 SELECT（第 9 章）/ RANK 原始版本 — 需要 OS-tree 增强（§14.1）才能 O(lg n) 找第 i 小。
BST 树高近似 O(lg n) — 对随机输入；实际中常用随机化 BST 让最坏变为罕见。
替代品（平衡树）：AVL 树（更严平衡）、红黑树（章 13，常数小）、跳表（实现简单、并发友好）、B 树（章 18，外存）。

补充：与其他章节的衔接

第 6 章（堆）：堆 = 完全二叉树 + 父 ≤ 孩子（不约束左右）；BST = 任意二叉树 + 左 ≤ 根 ≤ 右。两者各有所长。
第 9 章（中位数与顺序统计）：中位数 = 第 n/2 小；BST 中需要 OS-tree 增强（第 14 章）才能 O(lg n) 找。
第 13 章（红黑树）：红黑树是「自平衡 BST」——保证 h ≤ 2 lg(n+1) ≈ O(lg n)；本章 BST 是其前身。
第 14 章（扩充数据结构）：BST 是扩充的理想基础——加 size 字段得 OS-tree、加 color 字段得红黑树。
第 18 章（B 树）：B 树是多路搜索树——BST 的推广，针对磁盘存储优化（少 I/O）。
第 24 章（最短路径）/ 第 25 章（所有对最短路径）：图算法中常用红黑树做「priority queue」（O(lg n) DECREASE-KEY）。

第 12 章 二叉搜索树 (Binary Search Trees)

核心结论

一、核心概念

二、详细笔记

12.1 BST 定义与中序遍历

12.2 查询操作（SEARCH / MIN / MAX / SUCCESSOR / PREDECESSOR）

12.3 插入与删除

12.4 随机构建 BST 的高度分析

三、关键图表

四、思维导图

五、重点与易错点

补充：与其他章节的衔接

第 12 章二叉搜索树 (Binary Search Trees)