01先把问题说具体
动态维护键集合,既要查找某个值,也要按顺序遍历。数组二分很快,但中间插入很贵。
02一步步得到方法
每个节点把键空间分成两侧
约定所有键互异:左子树全部小于根,右子树全部大于根。查找 x 时,x 小就向左,大就向右,相等则命中。重要的是整棵子树的约束,不只是直接孩子比父亲小或大。
插入沿同一路径走到空位置,新叶子的范围由所有祖先共同限定。重复键可以忽略、保存计数或统一放某侧,但必须让所有操作使用一致规则。
删除为什么分三种情况
叶子直接摘除;只有一个孩子时让父节点绕过它指向孩子;两个孩子时可用右子树最小键作为中序后继替换,再删除后继原节点。后继没有左孩子,因此第二步更简单。
本课代码完整演示查找与插入,删除先理解结构变换。普通 BST 不自动平衡,连续插入 1、2、3、4 会形成右链,下一课 AVL 用旋转限制高度。
沿比较结果排除整棵子树
查找键 x 时,如果 x 小于当前键,右子树所有键都更大,整棵右子树可被排除;向左下降并不是猜测,而是大小不变量保证的剪枝。
删除有两个孩子的节点常用中序后继替代,再在右子树删除后继。替代的是键或记录语义,节点指针与外部引用可能需要特殊处理;本课插入查找代码不隐含完成所有删除接口。
03把一个小例子完全算清楚
依次插入 4、2、7、1、3,查找 3。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 根 4 | 3<4,走左 | 整个右子树排除 |
| 节点 2 | 3>2,走右 | 整个左子树排除 |
| 节点 3 | 命中 | 路径长度 3 |
窄屏可左右滑动表格,阅读完整计算与理由。
查找每步只选一棵子树,但效率取决于树高而非仅取决于节点数。
04为什么这个方法成立
- BST 约束确保目标若存在,只能位于比较结果指定的子树。
- 插入走到的空位置满足全部祖先给定的上下界。
- 沿路径插入不会改变其他节点关系,因此保持 BST 性质。
05把推导翻译成代码
Python · 可独立运行的教学实现
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
elif key > root.key:
root.right = insert(root.right, key)
return root
def contains(root, key):
while root is not None:
if key == root.key:
return True
root = root.left if key < root.key else root.right
return False逐个理解关键决定
root.left = insert(root.left, key)- 递归可能返回新子树根,必须接回父节点。
elif key > root.key- 相等时不新增节点,本实现表示互异键集合。
06时间、空间与实现范围
查找、插入、删除均 O(h),平衡时 O(log n),退化时 O(n)。
本递归插入栈 O(h),迭代查找 O(1) 工作空间;存储 n 个节点 O(n)。
07改变条件,检查哪里会出错
只检查父子大小就验证整棵 BST
根 10 的左子树里出现 12,即使它大于父节点 5,也违反祖先上界;要传递完整上下界。
输入有序就一定更好
未经平衡的 BST 按有序序列插入可能退化为链,单次操作 O(n)。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
按 1、2、3、4 插入会怎样?
需要一点提示
每次都选右侧。
查看解析与答案
形成高度 4 的链,查找 4 需比较 4 次。
两个孩子的节点为何可用右子树最小值替换?
需要一点提示
它处在左右键集合的分界处。
查看解析与答案
它大于全部左子树键且不大于剩余右子树键,移除原位置后保持搜索顺序。
频繁插入但必须稳定对数查询怎么办?
需要一点提示
高度保证从哪里来?
查看解析与答案
使用 AVL、红黑树等自平衡结构,而不是假设输入随机。