有序数组能折半查找，却要为中间插入付出元素移动。二叉排序树把有序关系放进树的链接中：查找仍能不断缩小范围，插入和删除则只改动路径附近的指针。

学习目标

• 说明二叉排序树的不变量及其中序有序性；
• 实现查找、插入和删除，处理删除的三种结构情况；
• 根据结点深度计算成功或失败查找的比较次数；
• 分析树高如何决定复杂度，以及插入顺序为何会造成退化；
• 解释为什么 BST 需要平衡化改进。

定义与不变量

二叉排序树（binary search tree，BST）是一棵空树，或满足以下条件的二叉树：

• 左子树中所有关键字都小于根关键字；
• 右子树中所有关键字都大于根关键字；
• 左右子树本身也都是 BST。

本节默认关键字互不相同。若允许重复值，必须统一规定"重复值放哪边"或在结点中维护计数，否则查找、删除和中序有序性的定义会变得含糊。

DEF定义 · BST 不变量

对 BST 的每个结点 $v$，其左子树中任意关键字都小于 $v$，右子树中任意关键字都大于 $v$。这一条件对每个结点递归成立。

一个重要的推论是：BST 的中序遍历得到严格递增序列。反过来，中序有序也是检查一次修改是否破坏 BST 的实用方法。

PROP性质 · BST 不变量与插入位置

新插入的结点总是落在某个空指针位置（叶位置），插入不会破坏已有结点之间的相对顺序。因此 BST 的不变量在插入时天然保持，只需要把新结点接到正确的地方。

BST 的中序遍历得到严格递增序列。反过来，中序有序也是检查一次修改是否破坏 BST 的实用方法。

查找

从根开始比较：相等则成功；目标更小就进入左子树；目标更大就进入右子树。到达空指针仍未命中，则查找失败。

Node* find(Node* root, int key) {
    Node* current = root;
    while (current != nullptr) {
        if (key == current->key) return current;
        current = key < current->key
            ? current->left
            : current->right;
    }
    return nullptr;
}

bst-find.cpp

若根结点位于第 1 层，查找某结点的关键字比较次数就是它的层数。失败查找则落在某个空指针位置，比较次数等于到该空指针的路径上经过的非空结点数。

EX示例 · 一次成功与一次失败查找

对下面这棵 BST：

        40
       /  \
      20   60
     / \   / \
    10 30 50 70

• 查找 30：比较 40（大，向左）→ 20（小，向右）→ 30（命中），共 3 次，等于 30 的层数。
• 查找 55：比较 40 → 60 → 50 → 空指针，共 3 次比较后失败（目标应落在 50 的右孩子，但它是空的）。路径经过 40, 60, 50 三个非空结点。

插入

插入先执行一次失败查找，再把新结点接到失败位置。沿途不改变已有结点之间的关系，因此 BST 不变量自然保持。

Node* insert(Node* root, int key) {
    if (root == nullptr) return new Node{key, nullptr, nullptr};

    if (key < root->key) {
        root->left = insert(root->left, key);
    } else if (key > root->key) {
        root->right = insert(root->right, key);
    }
    return root; // 相等时不重复插入
}

bst-insert.cpp

同一组关键字按不同顺序插入，可能得到完全不同的 BST。中序序列只决定关键字的排序结果，不决定树形。

EX示例 · 相同关键字、不同插入顺序

对关键字 {1,2,3,4,5}：

• 按 3, 1, 2, 5, 4 插入，得到较平衡的树，高度约 3：

• 按 1, 2, 3, 4, 5 插入，每个结点都挂在右孩子上，树退化成一条链，高度 5：

两组关键字的中序序列完全相同（都是 1 2 3 4 5），但查找复杂度从 $O(\log n)$ 退化为 $O(n)$。这就是"中序序列不能唯一确定 BST"的含义。

交互式演示

这个演示把"同一组关键字、不同插入顺序"画成一张可操作的树。先点"退化链"感受高度 5 的细长树，再换平衡序列对比树高与成功 ASL——两边中序序列完全一样，但查找成本天差地别；也可以点击任意结点，亲手体验删除的叶、单孩、双孩三种情况。

观察什么

分别用 1,2,3,4,5 和 3,1,2,5,4 插入，比较树高与成功 ASL。再用 40,20,60,10,30,50,70 建树后依次删除叶、单孩、双孩结点，每一步核对中序遍历是否仍严格升序。

例如依次插入 5, 3, 7, 1, 4, 6, 8，得到的树接近平衡；依次插入 1, 2, 3, 4, 5，每个结点都只有右孩子，树退化成链。

删除的三种情况

删除前先找到目标结点，再根据孩子数量处理。

1. 叶结点

叶结点没有孩子，直接断开父结点指向它的链接即可。

2. 只有一个孩子

让父结点直接指向目标的唯一孩子。目标左侧或右侧的全部关键字原本就处于合法区间，整体上移不会破坏次序。

3. 有两个孩子

目标不能简单由某棵子树整体替代。常用做法是：

1. 找到右子树中的最小结点，即目标的中序后继；
2. 用后继关键字替换目标关键字；
3. 在右子树中删除原后继结点。

后继是右子树最左侧结点，不可能有左孩子，所以第 3 步一定退化为删除叶结点或只有一个孩子的结点。也可以对称地使用左子树最大结点，即中序前驱。

IDEA直觉 · 为什么双孩子要用中序后继替换

双孩子结点左右子树都有内容，不能整个用某棵子树顶替，否则会丢掉另一半。但我们可以只把关键字换掉，保持树形。用中序后继（右子树最小）替换后，整棵树的中序序列不变，仍然严格升序；剩下要做的只是把原来的后继结点从右子树删掉，而后继必然没有左孩子，删除退化为简单情形。

Node* remove(Node* root, int key) {
    if (root == nullptr) return nullptr;

    if (key < root->key) {
        root->left = remove(root->left, key);
    } else if (key > root->key) {
        root->right = remove(root->right, key);
    } else {
        if (root->left == nullptr) return root->right;
        if (root->right == nullptr) return root->left;

        Node* successor = root->right;
        while (successor->left != nullptr) successor = successor->left;
        root->key = successor->key;
        root->right = remove(root->right, successor->key);
    }
    return root;
}

bst-remove.cpp

EX示例 · 三种删除的完整走一遍

对下面这棵 BST：

删除叶结点 10：10 没有孩子，直接让 20 的左孩子指向空，树变为：

删除单孩子结点 60：60 有右孩子 70（没有左孩子），让 40 的右孩子直接指向 70：

删除双孩子结点 40（根）：找右子树 70 的最小结点，即 70 本身（无左孩子）。用 70 替换根的关键字，再删除原来的 70：

每一步之后中序遍历都严格升序，BST 性质保持。

示例代码省略了内存释放，以突出结构变化；完整实现必须在返回孩子前释放被删除结点，并明确树的所有权策略。

复杂度取决于树高

设树高为 $h$。查找、插入和删除都只沿一条根到结点的路径进行，额外寻找后继也不会超出树高，因此三者均为：

$$T(n)=O(h).$$

树形	高度	查找、插入、删除
接近平衡	$O(\log n)$	$O(\log n)$
完全退化	$n$	$O(n)$

随机排列依次插入时，BST 的期望高度为 $O(\log n)$；但这只是输入分布下的期望，不是最坏保证。有序或接近有序的插入序列很容易生成细长树。

O(·)复杂度 · BST 的期望与最坏

• 期望（随机插入）：$O(\log n)$；
• 最坏（有序插入）：$O(n)$。

BST 只约束"左小右大"，并不约束左右子树高度差。因此 $O(\log n)$ 只是平均期待，不是最坏承诺。

成功 ASL

若每个结点等概率被查找，成功 ASL 等于所有结点层数之和除以结点数：

$$AS{L}_{success}=\frac{1}{n}\sum _{i=1}^{n}level(i).$$

因此比较两棵含相同关键字的 BST 时，不能只看结点数；要看整棵树的带权路径长度或平均深度。

EX示例 · 同关键字不同树形，ASL 不同

两棵含 {1,2,3,4,5} 的 BST：平衡树各层结点数为 1,2,2，成功 ASL $={\displaystyle \frac{1\cdot 1+2\cdot 2+2\cdot 3}{5}}={\displaystyle \frac{11}{5}}=2.2$；退化链的层数为 1,2,3,4,5，成功 ASL $={\displaystyle \frac{1+2+3+4+5}{5}}=3$。退化树的平均查找次数明显更差。

BST 与折半查找的关系

对一个有序序列执行折半查找，可以把比较过程画成一棵判定树；这棵判定树本身满足 BST 的有序关系。区别在于：

• 折半查找的树由数组下标和取中规则隐式决定，数据更新常要移动元素；
• BST 的树由插入顺序显式形成，链接便于局部修改，但树形可能失控。

两者的查找比较次数都由树深决定。前者借助静态数组获得稳定的近似平衡，后者需要额外机制维持高度。

易错点

• BST 不等于平衡二叉树。 "左小右大"不限制左右子树高度。
• 插入位置一定是叶位置。 不能把新值挂在搜索路径中间而不调整原子树。
• 双孩子删除是值替换加一次更简单的删除。 复制后继后，原后继仍要从右子树删掉。
• 中序序列不能唯一确定 BST。 还需要先序/后序信息或插入顺序。
• 平均 $O(\log n)$ 不是无条件结论。 普通 BST 的最坏时间仍是 $O(n)$。

WARN易错点 · 双孩子删除的"值替换"陷阱

很多人以为双孩子删除是"把整个子树提上来"。实际上，若用中序后继替换，树形不变，只是目标结点的值变了；被替换的原后继仍然留在右子树中，需要再删一次。忘记这第二次删除会让树里残留一个重复关键字，破坏中序严格升序。

何时不该用普通 BST

若输入可能近似有序，或系统需要稳定的最坏延迟，普通 BST 风险很高。平衡查找树通过旋转和颜色等局部信息约束高度，把查找、插入、删除稳定在 $O(\log n)$。

配套 Lab

完成 Lab 08-E-01：BST 增删查与边界测试，用中序遍历验证每次修改后的不变量，并比较随机插入与有序插入的树高；进阶做 Lab 08-P-01：自平衡查找树——AVL 旋转维护与退化对比。

小结

BST 把"有序数组里的折半方向"变成了可动态修改的左右链接。它的所有核心操作都沿树高进行；灵活性来自链接，风险也来自树形。只要高度不受约束，O(log n) 就只能是平均期待，而不是最坏承诺。

练习

1. 依次插入 40, 20, 60, 10, 30, 50, 70, 25，画出 BST 并写出成功查找 25 的比较序列。
2. 在上题的树中依次删除叶结点 10、单孩子结点 30、双孩子结点 40，每步画出结果并核对中序序列。
3. 给出两种插入顺序，使关键字 {1,2,3,4,5,6,7} 分别形成高度 3 和高度 7 的 BST。
4. 一棵 BST 的先序序列是 8, 3, 1, 6, 4, 7, 10, 14, 13。不用建树，写出其中序序列；再判断树高。
5. 若要支持"第 $k$ 小"查询，应在每个结点额外维护什么信息？插入和删除时如何更新？