二叉搜索树（BST）
二叉搜索树（Binary Search Tree, BST）对每个节点，左子树所有值 < 节点值 < 右子树所有值——查找、插入、删除平均 O(log n)
🗂️ 如何组织大量数据——让查找变得更快？
上一节学了二叉树——数据有了层次结构。但有一个问题：你怎么在树里快速找到某个数？
如果一棵树只是随便组织——根节点是 1，左子是 9，右子是 3——那你要找一个数，最坏情况还是要把所有节点都看一遍。
二叉搜索树（Binary Search Tree, BST） 给树加了一个”规则”：
对于树的每一个节点：左子树的所有值 < 节点值 < 右子树的所有值
这个简单的规则，让查找变得像二分搜索一样快。
🏫 类比：图书馆的图书分类
你去图书馆找一本书。图书馆的书是按字母分区的：
- A-K 区在左边（左子树）
- L-Z 区在右边（右子树）
你走到 L-Z 区，发现里面又分了两个分区：
- L-R 区在左
- S-Z 区在右
你走进 S-Z 区……每次你只需要决定”往左还是往右”，不用遍历整个图书馆。
这就是 BST 的核心思想——每次比较都能排除一半的可能。
📐 BST 的定义和性质
定义
一棵二叉搜索树满足：对于树中的每一个节点：
- 如果左子树不为空，左子树中所有节点的值都小于该节点的值
- 如果右子树不为空，右子树中所有节点的值都大于该节点的值
- 左右子树也都是 BST
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
验证：
- 节点 3：左子树
{1}都小于 3，右子树{4,6,7}都大于 3 ✅ - 节点 10：右子树
{13,14}都大于 10 ✅ - 节点 6：左子树
{4}小于 6，右子树{7}大于 6 ✅
关键性质
# BST 的中序遍历 = 从小到大排序
def inorder(node):
if not node:
return
inorder(node.left)
print(node.val) # 输出：1, 3, 4, 6, 7, 8, 10, 13, 14
inorder(node.right)
这是 BST 最重要的性质：中序遍历的结果是升序序列。这个性质你在很多树相关的问题中都会用到。
🔍 BST 的查找
查找过程
从根节点开始比较：
查找 7：
8 → 7 < 8 → 去左子树
↓
3 → 7 > 3 → 去右子树
↓
6 → 7 > 6 → 去右子树
↓
7 → 7 == 7 → 找到了！ ✅
def search_bst(root, target):
if not root or root.val == target:
return root
if target < root.val:
return search_bst(root.left, target)
else:
return search_bst(root.right, target)
每次比较排除一整棵子树——这就是 BST 查找 O(log n) 的来源。
💡 和二分搜索的对比：BST 的查找和二分搜索的本质是一样的——每次比较排除一半数据。区别在于：
- 二分搜索在数组上工作，要求数组有序
- BST 在树上工作，树的构造过程就”自带”有序性
➕ BST 的插入
插入的逻辑和查找几乎一样——先找到应该存放的位置，然后插入：
def insert_bst(root, val):
if not root:
return TreeNode(val) # 找到空位，插入
if val < root.val:
root.left = insert_bst(root.left, val)
elif val > root.val:
root.right = insert_bst(root.right, val)
# 如果 val == root.val，根据具体需求处理（通常不插入重复值）
return root
插入 5 到 BST 中：
8 8
/ \ / \
3 10 → 3 10
/ \ / \
1 6 1 6
/
5 ← 插在这里（因为 5 < 6 且 5 > 3）
➖ BST 的删除（最复杂）
BST 的删除分三种情况：
情况 1：删除叶子节点（没有子节点）
最简单——直接删除。
删除 4：
8 8
/ \ / \
3 7 → 3 7
/ /
2 2
\
4 ← 删除
if not root.left and not root.right:
return None # 直接删掉
情况 2：删除有一个子节点的节点
用子节点替换要删除的节点。
删除 7（右子节点为 9）：
8 8
/ \ / \
3 7 → 3 9
/ \
6 9
if not root.left:
return root.right # 用右子替换
if not root.right:
return root.left # 用左子替换
情况 3：删除有两个子节点的节点
这是最复杂的情况。策略：用右子树中的最小节点替换被删除节点。
删除 3（有两个子节点）：
8 8
/ \ / \
3 10 → 4 10
/ \ / \
1 6 1 6
/ \ / \
4 7 5 7
\
5 ← 右子树中的最小节点
# 找到右子树的最小节点
min_node = find_min(root.right)
root.val = min_node.val # 用最小值替换当前节点
root.right = delete(root.right, min_node.val) # 删除那个最小节点
📊 复杂度分析
| 操作 | 平均情况 | 最坏情况 |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
BST 的致命缺陷——退化
BST 的 O(log n) 是”平均情况”——它依赖树的形状。如果插入的数据是已经有序的：
# 按顺序插入 1, 2, 3, 4, 5, 6
root = None
for i in [1, 2, 3, 4, 5, 6]:
root = insert_bst(root, i)
# 结果树：
# 1
# \
# 2
# \
# 3
# \
# 4
# \
# 5
# \
# 6
这棵树退化成了链表！查找变成 O(n)，完全失去了 BST 的优势。
💡 为什么会退化？ 因为 BST 没有”自动平衡”的机制——插入数据的顺序决定了树的形状。有序数据让 BST 变成单向延伸。这正是 平衡树（AVL/红黑树） 要解决的问题——通过旋转保持树的平衡。
🏢 BST 的实际应用
| 场景 | 说明 |
|---|---|
| C++ STL map/set | 用红黑树（平衡 BST）实现，支持有序遍历 |
| Java TreeMap | 同样用红黑树实现 |
| 数据库索引（非主流） | 大多数数据库用 B+ 树（BST 的变体） |
| 表达式树 | 编译器用 BST 表示算术表达式 |
| 区间查找 | BST 可以高效地查找某个范围内的所有值 |
Python 中为什么不直接用 BST？
Python 标准库没有直接的 BST 实现（因为大多数场景有更好的替代）：
- 需要键值对查找 → 用 dict（哈希表）
- 需要有序数据 → 用 list + sort
- 需要有序键值对 → 用
bisect模块 + dict
📝 小结
| 概念 | 一句话 |
|---|---|
| BST 性质 | 左子树 < 节点 < 右子树 |
| 中序遍历 | 输出 BST 的升序排列 |
| 查找 | 比较→左或右→递归——O(log n) |
| 插入 | 找到空位插入——和查找类似 |
| 删除 | 三种情况：无子、一子、两子 |
| 退化 | 有序插入导致 BST 退化成链表 O(n) |
🎯 思考题：给定一个数组，如何构造一棵”最优”的 BST——即查找效率最高的 BST？（提示：这和二分查找的 mid 选择有关。如果你能选择根节点，应该选哪个？）
为什么先学这个？ BST 解决了”查找”和”插入”的动态平衡问题，但它有退化风险。平衡树（AVL/红黑树）通过旋转解决了退化问题。另一个分支是堆——一种不完全排序但部分有序的树结构。