5.2 二叉搜索树的增删查
前置：二叉树的结构与递归，约 35 分钟。本节采用唯一整数 key，依次实现查找、插入、三类删除、全局验证与范围查询，并始终用树高
h分析成本。
排序规则是一条全局不变量
BST 给普通二叉树加上一条全局排序规则：
对每个节点，左子树的所有 key 都小于当前 key，右子树的所有 key 都大于当前 key。
“所有”很重要。下面这棵树的直接孩子看起来正确，节点 12 却落在根 10 的左子树里，因此不是 BST。
10
/ \
5 15
\
12 ← 大于 10，却仍在 10 的左子树本页把 BST 当作唯一整数 key 的集合。重复插入保留原树并返回 False，size 不增长。若业务需要同 key 多条记录，可以把值改成列表，或为节点增加 count；不要在没有说明时任意把相等 key 塞到某一侧。
查找：每次只走一个子树
在样例树中查找 60：
50 → 70 → 60
60 > 50，向右
60 < 70，向左本页沿用按边计高，非空树高为 h。查询最多检查 h+1 个节点，时间为 O(h + 1)；空树查询为常数时间。只有在 h = O(log n) 时，才可写成 O(log n)。
查找失败也沿一条路径走到空链接。它不需要遍历另一侧，因为 BST 不变量已经排除了那里的 key。
插入：沿查找路径接到空位
插入与失败查找走同一条路。区别是，走到空链接后创建节点，并把链接接回父节点。
重复 key 在本页不创建节点。这个决定会影响 size、删除语义、验证边界和中序结果，所以代码把它集中在 insert 里。
删除：父节点应接回什么
找到目标节点后，按孩子数量处理：
没有孩子
返回空链接。父节点不再指向目标。
只有一个孩子
返回唯一孩子。父节点越过目标，直接连到其子树。
有两个孩子
目标的左右子树都要保留。代码选择右子树中最小的 key，也就是中序后继：
- 把后继 key 复制到目标节点。
- 在右子树中删除原后继节点。
- 把更新后的右子树接回。
后继没有左孩子，因此第二次删除只会落入“没有孩子”或“一个孩子”。
完整实现
这段程序可以独立运行。公开方法负责 root 与 size，删除的递归辅助函数返回更新后的子树根；查找和插入使用循环。入口检查整数 key，避免 NaN 一类既不小于也不大于的值误走删除分支。
def require_int_key(key):
if not isinstance(key, int):
raise TypeError("key must be an integer")
class TreeNode:
def __init__(self, key):
require_int_key(key)
self.key = key
self.left = None
self.right = None
def is_valid_bst(root):
"""使用开区间上下界验证严格 BST 不变量。"""
def validate(node, lower, upper):
if node is None:
return True
if lower is not None and node.key <= lower:
return False
if upper is not None and node.key >= upper:
return False
return (
validate(node.left, lower, node.key)
and validate(node.right, node.key, upper)
)
return validate(root, None, None)
def range_query(root, low, high):
"""按升序返回闭区间 [low, high] 内的 key。"""
require_int_key(low)
require_int_key(high)
if low > high:
return []
result = []
def visit(node):
if node is None:
return
if node.key > low:
visit(node.left)
if low <= node.key <= high:
result.append(node.key)
if node.key < high:
visit(node.right)
visit(root)
return result
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def search(self, key):
require_int_key(key)
current = self.root
while current is not None:
if key == current.key:
return current
if key < current.key:
current = current.left
else:
current = current.right
return None
def insert(self, key):
require_int_key(key)
if self.root is None:
self.root = TreeNode(key)
self.size = 1
return True
parent = None
current = self.root
while current is not None:
parent = current
if key == current.key:
return False
if key < current.key:
current = current.left
else:
current = current.right
if key < parent.key:
parent.left = TreeNode(key)
else:
parent.right = TreeNode(key)
self.size += 1
return True
def delete(self, key):
require_int_key(key)
self.root, deleted = self._delete(self.root, key)
if deleted:
self.size -= 1
return deleted
def _delete(self, node, key):
if node is None:
return None, False
if key < node.key:
node.left, deleted = self._delete(node.left, key)
return node, deleted
if key > node.key:
node.right, deleted = self._delete(node.right, key)
return node, deleted
if node.left is None:
return node.right, True
if node.right is None:
return node.left, True
successor = node.right
while successor.left is not None:
successor = successor.left
node.key = successor.key
node.right, _ = self._delete(node.right, successor.key)
return node, True
def inorder(self):
result = []
def visit(node):
if node is None:
return
visit(node.left)
result.append(node.key)
visit(node.right)
visit(self.root)
return result
def range_query(self, low, high):
return range_query(self.root, low, high)
def is_valid(self):
return is_valid_bst(self.root)
tree = BinarySearchTree()
for key in [50, 30, 70, 20, 40, 60, 80]:
assert tree.insert(key)
assert tree.inorder() == [20, 30, 40, 50, 60, 70, 80]
assert tree.size == 7
assert tree.search(60).key == 60
assert tree.search(99) is None
assert not tree.insert(60)
assert tree.size == 7
assert tree.range_query(35, 70) == [40, 50, 60, 70]
assert tree.is_valid()
assert tree.delete(20) # 叶节点
assert tree.delete(30) # 此时只有一个孩子 40
assert tree.delete(50) # 双孩子根节点
assert not tree.delete(999) # 缺失 key
assert tree.inorder() == [40, 60, 70, 80]
assert tree.size == 4
assert tree.is_valid()为什么验证必须传上下界
局部检查只能保证：
node.left.key < node.key < node.right.key它约束不了更深后代。验证根 10 的左子树时，所有节点都必须落在 (-∞, 10)；进入节点 5 的右子树后，允许区间收紧为 (5, 10)。节点 12 因超过上界而失败。
is_valid_bst 验证的是 key 顺序，前提是输入已经是一棵无环、没有共享孩子的二叉树；它不会检测对象图中的环。代码使用开区间，正好对应严格唯一键规则。若数据结构采用其他重复键策略，边界比较也要同步调整。
范围查询怎样剪枝
查询闭区间 [35, 70] 时：
- 当前 key 小于等于 35，其左子树不可能产生结果。
- 当前 key 大于等于 70，其右子树不可能产生结果。
- 当前 key 落在区间内，按中序位置加入结果。
返回的 key 已经升序排列，不需要二次排序。若输出数量为 k，访问成本是 O(h + k + 1)；链状树或覆盖全部 key 的查询最坏仍为 O(n)。返回 k 个 key 需要 Θ(k) 输出空间，递归还要 O(h+1) 辅助空间。low > high 时直接返回空列表。
复杂度与形状
下表按整数比较为单位成本计算；很大的 Python 整数还要计入位数。中序列表的 Θ(n) 输出空间另计，空树操作仍为常数。
| 操作 | 时间 | 迭代辅助空间 | 递归辅助空间 |
|---|---|---|---|
| 查找 | O(h + 1) | O(1) | 若递归实现则 O(h + 1) |
| 插入 | O(h + 1) | O(1) | 若递归实现则 O(h + 1) |
| 删除 | O(h + 1) | 本页递归实现不适用 | O(h + 1) |
| 中序遍历 | O(n) | O(h + 1) | O(h + 1) |
| 范围查询 | O(h + k + 1)，最坏 O(n) | 取决于实现 | 本页为 O(h + 1) |
依次插入 1, 2, 3, 4, 5 会得到：
1
\
2
\
3
\
4
\
5这棵树仍满足 BST 不变量，却有 h = n - 1。普通 BST 没有自我平衡机制，输入顺序会决定形状。查找和插入虽然是循环，删除、中序遍历与验证仍递归；很深的链可能触及 Python 递归限制。
BST、哈希表与有序容器
| 能力 | 普通哈希表 | 未平衡 BST | 平衡有序容器 |
|---|---|---|---|
| 精确查找 | 期望 O(1)，最坏可线性 | O(h + 1) | O(log n) |
| 升序遍历 | 需另行排序 | O(n) | O(n) |
| 下界/上界 | 通常要扫描 | O(h + 1) | O(log n) |
| 范围查询 | 通常要扫描或维护额外索引 | O(h + k + 1) | O(log n + k) |
| 输入顺序影响树高 | 不适用 | 会 | 平衡规则限制高度 |
Java TreeMap 公开声明采用红黑树并为基本操作提供对数时间保证。C++ 标准对 set、map 等有序关联容器规定比较器顺序和对数复杂度，但不要求某一种节点布局。Python dict 的迭代顺序是插入顺序，不是 key 的排序顺序。
常见错误
删除后没有更新根
根可能被唯一孩子替代，也可能变为空树。类方法要写 self.root = ...，函数式接口要让调用者接住返回的新根。
双孩子删除后留下两个相同 key
复制后继 key 后，还要从右子树删除原后继节点。只复制不删除会违反唯一键契约。还有节点身份问题：外部若保存了目标节点引用，删除后这个对象可能仍在树中，但 key 已变成后继 key；被摘除的反而是原后继节点。本例不保证“节点引用永久对应同一个 key”，调用者也不能绕过树直接改写 key 或链接。
重复插入仍增加 size
先判断相等，再创建节点和增加计数。本页 insert 用布尔返回值明确告诉调用者是否发生结构变化。
用 float("-inf") 当通用边界
浮点无穷适用于数值 key，却不适用于字符串或自定义可比较对象。代码用 None 表示无界，再仅在边界存在时比较。
把实现细节当作语言保证
某个 C++ 标准库常用红黑树，不代表 C++ 标准强制它这样实现。专业文档应引用公开复杂度和顺序契约。
调试顺序
- 写下重复键策略和比较器语义。
- 每次变更后做中序遍历，确认严格递增。
- 同时检查
size与中序结果长度。 - 分别测试空树、单节点、叶、单孩子、双孩子根和缺失 key。
- 构造深层违规节点，测试上下界验证。
- 插入有序序列，记录高度并复核复杂度说明。
动手检验全局不变量
- 实现
min_key、max_key、floor和ceiling。 - 把重复键策略改为节点计数，列出需要同步修改的方法。
- 为
delete写五组断言，覆盖三种孩子数量、根与缺失 key。 - 写一个错误的局部验证器，用深层违规树证明它会误判。
- 比较随机顺序与升序插入后的树高，不要只比较运行时间。
核对全局顺序与树高
BST 的判断条件是整棵子树的上下界，不是只看直接孩子。查找和插入沿一条路径前进，双孩子删除还会寻找并移除后继；总成本仍是 O(h + 1)；普通 BST 若被有序输入压成长链，并没有对数保证。删除时最值得反复测试的是根节点与双孩子节点，因为调用者必须接住新的子树根。
接下来去 树的遍历，把“走哪边”和“何时访问当前节点”分开。有序输入造成的高度问题，则留给 第 6 章：平衡树用旋转和颜色约束处理。