专题进阶 · 树与范围查询推荐总顺序 · 第 49 / 148 课

将有序区间映射到子树,解释查找、插入与退化高度。

先学会这些,再进入本课 二叉树 中序遍历 二分查找
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

二叉搜索树BST

左子树键更小、右子树键更大;退化链时操作可能到 O(n)。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

将有序区间映射到子树,解释查找、插入与退化高度。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

动态维护键集合,既要查找某个值,也要按顺序遍历。数组二分很快,但中间插入很贵。

02一步步得到方法

每个节点把键空间分成两侧

约定所有键互异:左子树全部小于根,右子树全部大于根。查找 x 时,x 小就向左,大就向右,相等则命中。重要的是整棵子树的约束,不只是直接孩子比父亲小或大。

插入沿同一路径走到空位置,新叶子的范围由所有祖先共同限定。重复键可以忽略、保存计数或统一放某侧,但必须让所有操作使用一致规则。

删除为什么分三种情况

叶子直接摘除;只有一个孩子时让父节点绕过它指向孩子;两个孩子时可用右子树最小键作为中序后继替换,再删除后继原节点。后继没有左孩子,因此第二步更简单。

本课代码完整演示查找与插入,删除先理解结构变换。普通 BST 不自动平衡,连续插入 1、2、3、4 会形成右链,下一课 AVL 用旋转限制高度。

沿比较结果排除整棵子树

查找键 x 时,如果 x 小于当前键,右子树所有键都更大,整棵右子树可被排除;向左下降并不是猜测,而是大小不变量保证的剪枝。

删除有两个孩子的节点常用中序后继替代,再在右子树删除后继。替代的是键或记录语义,节点指针与外部引用可能需要特殊处理;本课插入查找代码不隐含完成所有删除接口。

03把一个小例子完全算清楚

依次插入 4、2、7、1、3,查找 3。

步骤计算与状态为什么这样做
根 43<4,走左整个右子树排除
节点 23>2,走右整个左子树排除
节点 3命中路径长度 3

窄屏可左右滑动表格,阅读完整计算与理由。

查找每步只选一棵子树,但效率取决于树高而非仅取决于节点数。

04为什么这个方法成立

  1. BST 约束确保目标若存在,只能位于比较结果指定的子树。
  2. 插入走到的空位置满足全部祖先给定的上下界。
  3. 沿路径插入不会改变其他节点关系,因此保持 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 · 复现与理解

按 1、2、3、4 插入会怎样?

需要一点提示

每次都选右侧。

查看解析与答案

形成高度 4 的链,查找 4 需比较 4 次。

练习 2 · 边界与辨析

两个孩子的节点为何可用右子树最小值替换?

需要一点提示

它处在左右键集合的分界处。

查看解析与答案

它大于全部左子树键且不大于剩余右子树键,移除原位置后保持搜索顺序。

练习 3 · 变式与迁移

频繁插入但必须稳定对数查询怎么办?

需要一点提示

高度保证从哪里来?

查看解析与答案

使用 AVL、红黑树等自平衡结构,而不是假设输入随机。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。