二叉搜索树

概念讲解

定义

二叉搜索树(Binary Search Tree,简称 BST)是一棵二叉树,并且对树中任意一个节点都满足:

  1. 若左子树非空,则左子树上所有节点的值都小于该节点的值;
  2. 若右子树非空,则右子树上所有节点的值都大于该节点的值;
  3. 左、右子树本身也都是二叉搜索树。

注意第 1、2 条说的是"所有节点",不是"直接左(右)孩子"。这一点是 BST 判定题最常设的陷阱。

如果允许重复值,通常约定:重复值统一放到左子树,或统一放到右子树,并在插入时规定好。下文默认节点值互不相同。

中序遍历的有序性

对 BST 做中序遍历(左 → 根 → 右),得到的序列是严格递增的。

理由:中序遍历先访问左子树的所有节点(它们都小于根),再访问根,最后访问右子树的所有节点(它们都大于根)。对每个子树递归成立,所以整体有序。反过来,若一棵二叉树的中序遍历严格递增,它也是 BST——于是"中序遍历是否有序"可以作为 BST 的判定方法。

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

中序:20 30 40 50 60 70 80
前序:50 30 20 40 70 60 80

查找、插入与删除

查找

从根出发,把待查值与当前节点值比较:小则去左子树,大则去右子树,相等即命中;走到空指针说明不存在。

12345678910111213141516171819#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* find(TreeNode* root, int x) {
    while (root != nullptr) {
        if (x == root->val) return root;
        if (x < root->val) root = root->left;
        else root = root->right;
    }
    return nullptr;
}

每比较一次就丢掉一整棵子树,比较次数等于查找路径上的节点数,复杂度 O(h)O(h),hh 为树高。

插入

沿着查找路径走到空位置,在那里新建节点。若值已存在则不插入(也可按约定挂到重复一侧)。

123456TreeNode* insert(TreeNode* root, int x) {
    if (root == nullptr) return new TreeNode(x);
    if (x < root->val) root->left = insert(root->left, x);
    else if (x > root->val) root->right = insert(root->right, x);
    return root;
}

插入顺序决定树形。例如依次插入 50, 30, 70, 20, 40, 60, 80,得到的正是上图;若依次插入 10, 20, 30, 40, 50,则每个新值都比前一个大,全部挂在右边,退化成一条右斜链。

删除(三种情形)

删除是最容易写错的操作,按被删节点 p 的孩子数量分三种情况:

  1. p 是叶子(没有孩子):直接删除,让父节点对应指针置空。
  2. p 只有一个孩子:用这个唯一的孩子顶替 p 的位置(把父节点指向 p 的指针改为指向该孩子)。
  3. p 有两个孩子:不能简单上移。做法是用 p 的中序后继(右子树中的最小值,即右子树最左节点)替换 p 的值,再在右子树中删除那个后继节点。后继节点最多只有一个右孩子,于是回到情形 1 或 2。

也可以改用中序前驱(左子树最大值)替换,效果等价。

12345678910111213141516171819202122232425262728TreeNode* findMin(TreeNode* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

TreeNode* erase(TreeNode* root, int x) {
    if (root == nullptr) return nullptr;
    if (x < root->val) {
        root->left = erase(root->left, x);
    } else if (x > root->val) {
        root->right = erase(root->right, x);
    } else {
        if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        TreeNode* suc = findMin(root->right);
        root->val = suc->val;
        root->right = erase(root->right, suc->val);
    }
    return root;
}

删除只是"移走一个值",不会打乱其余节点的相对顺序,所以删除任意节点后,剩下的节点中序遍历序列仍然有序——只是少了一个元素。

前驱与后继

  • 中序前驱:中序遍历中紧挨在某节点前面的节点。若该节点有左子树,前驱就是左子树中最大的节点(左子树最右端);否则需要沿父指针向上找。
  • 中序后继:紧挨在后面的节点。若有右子树,后继就是右子树中最小的节点(右子树最左端);否则需要向上找祖先。

在上面的示例树中:5050 的前驱是 4040,后继是 6060;整个树的最小值在最左端 2020,最大值在最右端 8080。

复杂度与退化

BST 上的查找、插入、删除都只需沿一条根到叶的路径走,复杂度为 O(h)O(h):

树形 高度 hh 单次操作
平衡(最好) ⌈log⁡2(n+1)⌉\lceil \log_2(n+1) \rceil 左右 O(log⁡n)O(\log n)
随机插入 期望 O(log⁡n)O(\log n) 期望 O(log⁡n)O(\log n)
退化成链(最坏) nn O(n)O(n)

退化最典型的触发方式就是按升序(或降序)插入:每次新值都挂在最右(或最左),树变成单链表,查找退化为顺序查找。为避免这种情况,实际使用中会引入平衡树(AVL 树、红黑树、Treap、Splay 等),通过旋转维持 h=O(log⁡n)h = O(\log n),从而保证最坏也是 O(log⁡n)O(\log n)。竞赛中常用的 std::set / std::map 底层就是平衡树,而 std::priority_queue 是堆,不是 BST。

考点分析

初赛考查方式

  1. 选择题: BST 的定义、中序遍历序列、前驱后继位置
  2. 程序阅读: 查找/插入/删除代码的功能与输出
  3. 分析题: 给定插入序列画树、计算查找比较次数、退化分析

常见考点

  • 由插入序列画出 BST,写出前序/中序序列
  • 删除节点后树的结构变化
  • 判定 BST 的正确做法(区间约束或中序有序)
  • 平均与最坏复杂度

例题精讲

例题 1:建树与遍历

题目: 依次插入 8, 3, 10, 1, 6, 14, 4, 7, 13,画出 BST,并写出前序与中序序列。

解答:

  • 88 为根;3<83<8 作左孩子;10>810>8 作右孩子;
  • 1<31<3 作 33 的左孩子;6>36>3 作 33 的右孩子;
  • 14>1014>10 作 1010 的右孩子;
  • 4<64<6 作 66 的左孩子;7>67>6 作 66 的右孩子;
  • 13<1413<14 且 >10>10,作 1414 的左孩子。
          8
        /   \
       3     10
      / \      \
     1   6      14
        / \    /
       4   7  13

前序(根 → 左 → 右):8 3 1 6 4 7 10 14 13

中序(左 → 根 → 右):1 3 4 6 7 8 10 13 14(严格递增,可用它自查建树是否正确)

查找 77 的比较路径为 8→3→6→78 \to 3 \to 6 \to 7,共 44 次比较。

例题 2:删除有两个孩子的节点

题目: 在上面这棵树中删除节点 33,树会变成什么样?

解答:

节点 33 有左右两个孩子,属于第三种情形。它的中序后继是右子树最小值:33 的右子树为 66(含 4,74, 7),最小值为 44。于是用 44 覆盖 33 的值,再在右子树中删除原来的 44(44 是叶子,直接删除)。

          8
        /   \
       4     10
      / \      \
     1   6      14
          \    /
           7  13

中序遍历仍为 1 4 6 7 8 10 13 14,只是原来的 33 不在了、44 提前出现——序列依旧有序。

练习题

  1. 依次插入 5, 2, 8, 1, 3, 7, 9,写出中序序列与树高。
查看答案

中序:1 2 3 5 7 8 9。树形为根 55、左子树以 22 为根(孩子 1,31,3)、右子树以 88 为根(孩子 7,97,9),高度为 33(按节点数计)。

  1. 判断 BST 时,为什么"每个节点只和它的左右孩子比较"是错的?
查看答案

BST 约束的是整棵子树,而不是直接孩子。反例:根 1010,左孩子 55,右孩子 1515,而 55 的右孩子是 1212。逐对比较时 12>512>5、12<1512<15 都满足,但 1212 位于 1010 的左子树中却大于 1010,违反 BST 定义。正确做法是给每个节点传一个合法值域 (lo,hi)(lo, hi),或在遍历时检查中序序列是否升序。

  1. 为什么按升序插入会让 BST 退化?如何缓解?
查看答案

升序插入时每个新值都大于此前所有值,只能一路向右挂,最终形成长度为 nn 的右斜链,树高 h=nh=n,单次操作从 O(log⁡n)O(\log n) 退化为 O(n)O(n)。缓解办法是使用平衡树(AVL、红黑树、Treap 等)在插入后通过旋转把树高维持在 O(log⁡n)O(\log n);也可以先随机打乱插入顺序,使期望树高为 O(log⁡n)O(\log n)。

易错点

⚠️ 注意:

  1. BST 要求左子树所有节点小于根、右子树所有节点大于根,只比较父子会误判
  2. BST 的中序遍历严格递增,但"前序遍历有序"不能作为判定依据
  3. 删除有两个孩子的节点要用中序后继(右子树最小)或中序前驱替换,不能直接把孩子提上来
  4. 中序后继是"右子树最左",中序前驱是"左子树最右",方向不要记反
  5. 平衡 BST 的查找是 O(log⁡n)O(\log n),退化成链时是 O(n)O(n),不能说 BST 查找一定是 O(log⁡n)O(\log n)
  6. std::set / std::map 是平衡树实现,std::priority_queue 是堆,两者都不是"普通 BST"