第12章 二叉搜索树 — 章节汇总

章节概览

本章系统介绍了二叉搜索树（Binary Search Tree, BST）——一种支持动态集合操作的有序数据结构。BST利用二叉树的层次结构，使得搜索、插入、删除等字典操作在 $O(h)$ 时间内完成（$h$ 为树高）。与散列表不同，BST天然支持有序操作（最小值、最大值、前驱、后继、范围查询），但最坏情况下可能退化为 $O(n)$。本章为第13章红黑树（保证 $O(\lg n)$ 最坏情况）奠定基础。

---

12.1 什么是二叉搜索树

小节	核心主题	关键结论
12.1 什么是二叉搜索树	BST定义、BST性质、中序遍历	中序遍历输出有序序列

核心思路：BST是一种二叉树，满足BST性质：对任意节点 $x$，左子树中所有节点的关键字 $\le x.\text{key}$，右子树中所有节点的关键字 $\ge x.\text{key}$。这是一个对整个子树的递归约束，而非仅对直接孩子的约束。

核心定理：

• 定理12.1：若 $x$ 是 $n$ 个节点的BST的根，则 INORDER-TREE-WALK(x) 输出关键字递增序列（数学归纳法证明）

---

12.2 查询二叉搜索树

小节	核心主题	关键结论
12.2 查询二叉搜索树	搜索、最小/最大值、前驱/后继	所有操作 $O(h)$ 时间

核心思路：BST的查询操作利用BST性质进行”二分导航”——每一步根据比较结果选择进入左子树或右子树，将搜索空间减半。

核心操作：

• TREE-SEARCH / ITERATIVE-TREE-SEARCH：搜索关键字为 $k$ 的节点
• TREE-MINIMUM / TREE-MAXIMUM：沿左/右边界下降到底
• TREE-SUCCESSOR / TREE-PREDECESSOR：两种情况——有右子树时取右子树最小值；无右子树时沿父指针上溯直到”左拐”

---

12.3 插入和删除

小节	核心主题	关键结论
12.3 插入和删除	TREE-INSERT、TRANSPLANT、TREE-DELETE	所有操作 $O(h)$ 时间

核心思路：

• 插入：从根出发沿BST性质找到合适的叶位置，将新节点挂在父节点下
• 删除：三种情况——无子节点（直接删除）、单子节点（用子节点替换）、双子节点（用后继替换，通过 TRANSPLANT 辅助操作实现）

关键设计决策：CLRS第4版使用 TRANSPLANT 方法实际替换节点 $z$（而非旧版的”复制后继key到 $z$“方法），保证外部指针不会失效（stale pointers问题）。

---

本章核心知识点

BST操作复杂度汇总

操作	时间复杂度	说明
搜索 (TREE-SEARCH)	$O(h)$	递归或迭代
最小值 (TREE-MINIMUM)	$O(h)$	沿左边界下降
最大值 (TREE-MAXIMUM)	$O(h)$	沿右边界下降
前驱 (TREE-PREDECESSOR)	$O(h)$	两种情况
后继 (TREE-SUCCESSOR)	$O(h)$	两种情况
插入 (TREE-INSERT)	$O(h)$	找叶位置+挂载
删除 (TREE-DELETE)	$O(h)$	三种情况
中序遍历	$\Theta (n)$	输出有序序列

BST vs 散列表 vs 二叉堆 对比

特性	二叉搜索树	散列表	二叉堆
搜索	$O(h)$，最坏 $O(n)$	$O(1)$ 期望	$O(n)$（不支持）
插入	$O(h)$	$O(1)$ 期望	$O(\lg n)$
删除	$O(h)$	$O(1)$ 期望	$O(\lg n)$
最小/最大	$O(h)$	不支持	$O(1)$
前驱/后继	$O(h)$	不支持	不支持
有序遍历	$\Theta (n)$（中序）	不支持	不支持
范围查询	$O(k+h)$	不支持	不支持
最坏保证	无（退化时 $O(n)$）	无（最坏 $O(n)$）	$O(\lg n)$
有序性	天然有序	无序	部分有序（堆性质）

BST删除三种情况

情况	条件	操作	复杂度
无子节点	$z.\text{left}=\text{NIL}$ 且 $z.\text{right}=\text{NIL}$	TRANSPLANT(T, z, NIL)	$O(1)$
单子节点	仅有一个子节点非NIL	TRANSPLANT(T, z, z.left) 或 TRANSPLANT(T, z, z.right)	$O(1)$
双子节点	两个子节点均非NIL	$y=\text{SUCCESSOR}(z)$；若 $y\ne z.\text{right}$ 先 TRANSPLANT(T, y, y.right)；再 TRANSPLANT(T, z, y) 并重接子树	$O(h)$

---

与前序章节的知识关联

前序章节	关联方式
第11章 散列表	散列 $O(1)$ 期望 vs BST $O(h)$ 的设计取舍；散列不支持有序操作，BST天然支持
第10章 基本数据结构	10.3节有根树的表示（p/left/right 指针）是BST节点结构的基础
第6章 堆排序	二叉堆 vs 二叉搜索树：同为二叉树但性质不同（堆：父≥子；BST：左<根<右）
第7章 快速排序	随机构建BST的期望路径长度与快速排序的比较次数相同（问题12-3）
第5章 概率分析	随机BST的期望高度分析依赖概率分析技术

---

学习路线

第12章学习路径：
  12.1 什么是二叉搜索树（BST定义→BST性质→中序遍历→定理12.1）
    → 12.2 查询二叉搜索树（搜索→最小/最大→前驱/后继→循环不变式证明）
      → 12.3 插入和删除（TREE-INSERT→TRANSPLANT→TREE-DELETE三种情况）

学习建议

本章是数据结构部分的基石章节。12.1 重点理解BST性质的”子树全局约束”（不是仅约束直接孩子）。12.2 重点掌握 TREE-SUCCESSOR 的两种情况分析和 ITERATIVE-TREE-SEARCH 的循环不变式证明。12.3 是本章最难的部分，TRANSPLANT 辅助操作和删除的三种情况（特别是情况3a和3b的区别）需要反复推敲。学完本章后，对比第11章散列表理解两者的设计取舍，同时为第13章红黑树（解决BST退化问题）做好准备。

二叉搜索树