第12章 二叉搜索树
导读
二叉搜索树（Binary Search Tree, BST）是一种重要的数据结构，它支持高效的查找、插入、删除操作。在平衡的情况下，这些操作的时间复杂度为O(log n)。二叉搜索树不仅是许多高级数据结构（如AVL树、红黑树）的基础，也是理解树形结构和递归算法的重要载体。
本章将详细介绍二叉搜索树的定义、性质、基本操作以及遍历方法。我们还将讨论二叉搜索树的优缺点，并引出平衡树的概念。
核心概念详解
12.1 二叉搜索树的定义
二叉搜索树性质：
设x是二叉搜索树中的一个节点：
- 如果y是x左子树中的一个节点，则y.key ≤ x.key
- 如果y是x右子树中的一个节点，则y.key ≥ x.key
直观理解：
- 左子树中的所有键 ≤ 当前节点的键
- 右子树中的所有键 ≥ 当前节点的键
- 这个性质对每个节点都成立
示例：
6
/ \
3 8
/ \ \
1 4 9
\ /
2 4这棵树满足二叉搜索树性质：每个节点的左子树键值都小于它，右子树键值都大于它。
12.2 二叉搜索树的遍历
中序遍历（Inorder Traversal）：
按升序访问所有节点。
INORDER-TREE-WALK(x)
if x ≠ NIL
INORDER-TREE-WALK(x.left)
print x.key
INORDER-TREE-WALK(x.right)时间复杂度：O(n)，其中n为节点数。
证明：每个节点恰好被访问一次，每次访问的额外工作为O(1)。
其他遍历：
- 前序遍历（Preorder）：根-左-右
- 后序遍历（Postorder）：左-右-根
- 层序遍历（Level-order）：按层从上到下
12.3 查询操作
查找（Search）：
TREE-SEARCH(x, k)
if x == NIL or k == x.key
return x
if k < x.key
return TREE-SEARCH(x.left, k)
else
return TREE-SEARCH(x.right, k)时间复杂度：O(h)，其中h为树的高度。
- 最好情况（平衡树）：O(log n)
- 最坏情况（退化为链表）：O(n)
迭代版本：
ITERATIVE-TREE-SEARCH(x, k)
while x ≠ NIL and k ≠ x.key
if k < x.key
x = x.left
else
x = x.right
return x最小值和最大值：
TREE-MINIMUM(x)
while x.left ≠ NIL
x = x.left
return x
TREE-MAXIMUM(x)
while x.right ≠ NIL
x = x.right
return x时间复杂度：O(h)
前驱和后继：
后继（Successor）：中序遍历中的下一个节点。
TREE-SUCCESSOR(x)
if x.right ≠ NIL
return TREE-MINIMUM(x.right)
y = x.parent
while y ≠ NIL and x == y.right
x = y
y = y.parent
return y时间复杂度：O(h)
12.4 插入操作
TREE-INSERT(T, z)
y = NIL
x = T.root
while x ≠ NIL
y = x
if z.key < x.key
x = x.left
else
x = x.right
z.parent = y
if y == NIL
T.root = z
else if z.key < y.key
y.left = z
else
y.right = z时间复杂度：O(h)
工作原理：
从根开始，沿着搜索路径向下
找到合适的叶子位置
将新节点插入
12.5 删除操作
删除操作比插入复杂，需要考虑三种情况：
情况1：节点z没有子节点
- 直接删除，将其父节点的相应指针设为NIL
情况2：节点z只有一个子节点
- 用子节点替换z
情况3：节点z有两个子节点
- 找到z的后继y（在z的右子树中）
- 如果y是z的右子节点，直接用y替换z
- 否则，先将y从其位置移除，再用y替换z
TREE-DELETE(T, z)
if z.left == NIL
TRANSPLANT(T, z, z.right)
else if z.right == NIL
TRANSPLANT(T, z, z.left)
else
y = TREE-MINIMUM(z.right)
if y.parent ≠ z
TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.parent = y
TRANSPLANT(T, z, y)
y.left = z.left
y.left.parent = y
TRANSPLANT(T, u, v)
if u.parent == NIL
T.root = v
else if u == u.parent.left
u.parent.left = v
else
u.parent.right = v
if v ≠ NIL
v.parent = u.parent时间复杂度：O(h)
12.6 二叉搜索树的性能分析
树的高度：
二叉搜索树的操作时间复杂度取决于树的高度h：
- 最好情况：h = O(log n)（平衡树）
- 最坏情况：h = O(n)（退化为链表）
- 平均情况（随机构建）：h = O(log n)
随机构建的BST：
如果n个关键字的n!种排列等概率，则随机BST的期望高度为O(log n)。
问题：
如果输入是有序的，BST会退化为链表，性能为O(n)。这是BST的主要缺点。
12.7 二叉搜索树的变体
AVL树：
- 每个节点的左右子树高度差不超过1
- 通过旋转保持平衡
- 查找、插入、删除：O(log n)最坏情况
红黑树：
- 每个节点有颜色（红或黑）
- 满足特定颜色约束
- 通过旋转和变色保持平衡
- 查找、插入、删除：O(log n)最坏情况
伸展树（Splay Tree）：
- 自调整数据结构
- 每次访问后将节点移到根
- 摊还O(log n)
Treap：
- 结合BST和堆的性质
- 每个节点有随机优先级
- 期望O(log n)
12.8 二叉搜索树的应用
1. 有序集合：
- 维护有序元素集合
- 支持范围查询
2. 字典/映射：
- 键值对存储
- 支持有序遍历
3. 优先级队列：
- 使用最小/最大BST
4. 区间树：
- 存储区间，支持区间查询
5. 符号表：
- 编译器中的变量管理
12.9 二叉搜索树的局限性
主要问题：
- 不平衡时性能退化
- 需要额外的平衡机制
解决方案：
- 使用平衡树（AVL、红黑树）
- 随机化（Treap）
- 自调整（伸展树）
12.10 二叉搜索树与其他数据结构的比较
| 数据结构 | 查找 | 插入 | 删除 | 有序遍历 | 最坏保证 |
|---|---|---|---|---|---|
| BST | O(h) | O(h) | O(h) | O(n) | O(n) |
| AVL树 | O(log n) | O(log n) | O(log n) | O(n) | O(log n) |
| 红黑树 | O(log n) | O(log n) | O(log n) | O(n) | O(log n) |
| 散列表 | O(1)平均 | O(1)平均 | O(1)平均 | 不支持 | O(n) |
重要知识点
知识点1：二叉搜索树性质的递归性
二叉搜索树性质是递归定义的：每个节点的左右子树也必须是二叉搜索树。这个递归性质使得许多操作可以自然地用递归实现。
知识点2：中序遍历的有序性
中序遍历二叉搜索树会按升序访问所有节点。这是二叉搜索树最重要的性质之一，也是许多应用的基础。
知识点3：删除操作的复杂性
删除操作需要考虑三种情况，特别是当节点有两个子节点时，需要用后继节点替换。这是BST操作中最复杂的部分。
知识点4：树高度对性能的影响
BST的性能取决于树的高度。不平衡的树会导致性能退化。平衡树通过额外机制保证树高为O(log n)。
知识点5：TRANSPLANT操作
TRANSPLANT是删除操作的核心辅助函数，用于将一棵子树替换为另一棵。理解TRANSPLANT有助于理解删除操作的实现。
常见误区
误区1：二叉搜索树总是高效的
BST的效率取决于树的高度。如果输入有序，BST会退化为链表，性能为O(n)。实际应用中应使用平衡树。
误区2：删除操作只需要断开指针
删除操作需要考虑节点是否有子节点，以及子节点的数量。简单地断开指针会破坏树的结构。
误区3：后继节点一定是右子节点
后继节点可能是右子树中的最小节点，也可能是祖先节点。需要根据具体情况判断。
误区4：BST不支持重复键
标准BST不允许重复键，但可以通过修改（如允许相等键在左子树或右子树）来支持。
误区5：BST比散列表好
BST和散列表各有优劣：
- BST：支持有序操作，最坏情况可控
- 散列表：O(1)平均性能，但不支持有序操作
实践应用
应用1：数据库索引
数据库使用平衡BST（如B+树）进行索引：
- 支持范围查询
- 有序遍历
- 磁盘友好
应用2：文件系统
文件系统使用BST组织：
- 目录结构
- 文件名查找
- 权限管理
应用3：内存管理
操作系统使用BST管理：
- 内存块分配
- 虚拟内存映射
- 页面替换
应用4：编译器
编译器使用BST存储：
- 符号表
- 作用域信息
- 类型信息
应用5：范围查询
BST支持高效的范围查询：
- 找所有在[a, b]范围内的元素
- 时间复杂度O(log n + k)，k为结果数
12.11 二叉搜索树的详细性能分析
随机BST的期望高度：
如果n个关键字的n!种排列等概率，则随机BST的期望高度为O(log n)。更精确地，期望高度约为4.311·ln n。
退化情况分析：
当输入为有序序列时，BST退化为链表：
1 → 2 → 3 → 4 → 5此时树的高度为n，所有操作的时间复杂度为O(n)。
随机化BST：
通过随机化输入顺序，可以保证期望O(log n)的性能。Treap就是一种随机化BST，每个节点有随机优先级，通过堆性质保证树的平衡。
12.12 平衡二叉搜索树详解
AVL树：
AVL树是最早的自平衡二叉搜索树。每个节点维护平衡因子 = 左子树高度 - 右子树高度，平衡因子的绝对值不超过1。
四种旋转操作：
- LL旋转（右旋）：左子树过高，且左子节点的左子树更高
- RR旋转（左旋）：右子树过高，且右子节点的右子树更高
- LR旋转：先左旋后右旋
- RL旋转：先右旋后左旋
每次插入最多需要一次旋转，每次删除最多需要O(log n)次旋转。
红黑树：
红黑树是每个节点有颜色（红或黑）的二叉搜索树，满足以下性质：
每个节点是红色或黑色
根节点是黑色
每个叶子节点（NIL）是黑色
红色节点的两个子节点都是黑色（无连续红节点）
从任一节点到其所有后代叶子的路径上，黑色节点数目相同
这些性质保证树的高度不超过2·log(n+1)。红黑树通过旋转和变色来维护性质。
红黑树vs AVL树：
- AVL树更严格平衡，查找更快
- 红黑树插入/删除时旋转次数更少
- 红黑树在标准库中更常用（C++ map、Java TreeMap）
12.13 BST的迭代器实现
BST的迭代器需要支持按序遍历所有元素：
基于栈的迭代器：
- 初始化：从根开始，将所有左子节点压入栈
- next()：弹出栈顶，如果有右子节点，将右子节点及其所有左后代压入栈
- hasNext()：栈非空
时间复杂度：每个节点入栈出栈各一次，n次next()调用的总时间为O(n)，摊还O(1)。
基于父指针的迭代器：
利用中序后继的计算，不需要额外空间。从最小值开始，每次调用TREE-SUCCESSOR获取下一个元素。
12.14 BST的区间查询
范围搜索：
找出BST中所有键在[a, b]范围内的元素。
算法：
从根开始搜索
如果当前节点键 < a，只搜索右子树
如果当前节点键 > b，只搜索左子树
如果a ≤ 当前节点键 ≤ b，输出当前节点，搜索左右子树
时间复杂度：O(log n + k)，其中k是结果数量。
排名查询：
找出BST中第k小的元素。需要在每个节点维护子树大小。
- 如果左子树大小 = k-1，当前节点就是答案
- 如果左子树大小 ≥ k，在左子树中找第k小
- 如果左子树大小 < k-1，在右子树中找第(k-左子树大小-1)小
时间复杂度：O(h)
12.15 BST在实际系统中的实现
C++ std::map：
基于红黑树实现，提供有序键值对存储。支持O(log n)的插入、删除、查找，以及O(n)的有序遍历。
Java TreeMap：
同样基于红黑树。提供subMap、headMap、tailMap等范围视图操作。
Go的有序映射：
Go标准库没有内置有序映射，但第三方库通常使用红黑树或跳表实现。
Rust的BTreeMap：
使用B树而非二叉搜索树，对缓存更友好，适合大规模数据。
本章小结
本章深入介绍了二叉搜索树。我们学习了：
定义和性质：左子树键值≤当前节点≤右子树键值，递归成立。中序遍历按升序访问所有节点。
基本操作：查找、最小值、最大值、前驱、后继、插入、删除，时间复杂度O(h)。删除操作使用TRANSPLANT处理三种情况。
性能分析：树的高度决定性能。随机BST期望O(log n)，有序输入退化O(n)。
平衡树：AVL树（平衡因子约束）和红黑树（颜色约束）通过旋转保持O(log n)性能。红黑树在标准库中更常用。
高级功能：迭代器实现、范围查询、排名查询。
应用：数据库索引、文件系统、内存管理、编译器符号表等。
二叉搜索树是理解树形数据结构和平衡概念的基础。掌握BST的原理和实现，是学习更高级数据结构的必经之路。
关键术语
| 术语 | 英文 | 含义 |
|---|---|---|
| 二叉搜索树 | Binary Search Tree | 满足搜索性质的二叉树 |
| 中序遍历 | Inorder Traversal | 左-根-右的遍历方式 |
| 后继 | Successor | 中序遍历中的下一个节点 |
| 前驱 | Predecessor | 中序遍历中的上一个节点 |
| 平衡树 | Balanced Tree | 高度为O(log n)的搜索树 |
| TRANSPLANT | TRANSPLANT | 子树替换操作 |
思考题
证明：中序遍历二叉搜索树会按升序访问所有节点。
设计一个算法，在O(h)时间内找到二叉搜索树中第k小的元素。
分析当输入为已排序数组时，依次插入构建的BST的结构和性能。
实现一个支持重复键的二叉搜索树，并修改插入和删除操作。