Lesson 38: 二叉搜索树 (BST) 操作

练习任务

难度: 难

实现二叉搜索树(BST)的四个核心操作:

find_min(root) -- 找最小值: 一路向左,直到 left == NULL
bst_insert(root, val) -- 插入: 小于往左递归,大于往右递归,遇到 NULL 创建新节点
bst_search(root, val) -- 查找: 沿 BST 性质搜索,找到返回节点指针,未找到返回 NULL
bst_delete(root, val) -- 删除【难点】: 三种情况(叶子/单子/双子)

make_node 和 inorder(中序打印,用于验证)已提供。find_min 需自行实现。

本课共有 4 组测试用例:

输入 "insert 5 3 7 2 4"           -> inorder: 2 3 4 5 7
输入 "insert 5 3 7\nsearch 3"     -> inorder: 3 5 7  found
输入 "insert 5 3 7\nsearch 9"     -> inorder: 3 5 7  not found
输入 "insert 5 3 7 2 4\ndelete 3" -> inorder: 2 3 4 5 7  inorder: 2 4 5 7

提示: BST 的插入和查找是互为镜像的操作--插入在 NULL 处创建,查找在 NULL 处返回。删除是最复杂的部分,分三种情况递进: 叶子直接删、单子用孩子替换、双子找右子树最小值替换再递归删。find_min 已提供。中序遍历用于验证 BST 性质(必须输出有序序列)。

核心知识点

BST 核心性质: 左子树所有值 <= 根值 <= 右子树所有值,中序遍历必定有序
递归插入与搜索互为镜像: 小于向左,大于向右,遇到 NULL 时一个创建、一个返回
删除三种情况递进: 叶子(最简单)-> 一个孩子(子承父业)-> 两个孩子(右子树最小值替换)
双子删除的核心: 找右子树最小值替换,再递归删除该最小值(必为叶或单子)
find_min: 一路向左走到尽头,复杂度 O(h)
为何右子树最小值保 BST 性质: 它大于所有左子树值,小于所有右子树其他值
BST 退化: 插入顺序敏感,最坏退化为链表(h=n)-> AVL/红黑树动机
递归删除返回 root: 每次递归重新挂接子树指针

代码框架

38_BST_ops.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
    int data;
    struct node *left, *right;
};

struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val;
    p->left = p->right = NULL;
    return p;
}

void inorder(struct node *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

/* 找 BST 最小值: 不断向左走 */
struct node *find_min(struct node *root) {
    // 在这里实现 find_min:
    // 1. if (root == NULL) return NULL;
    // 2. while (root->left != NULL) root = root->left;
    // 3. return root;
}

/* BST 插入 */
struct node *bst_insert(struct node *root, int val) {
    // 在这里实现 bst_insert:
    // 1. if (root == NULL) return make_node(val);
    // 2. if (val < root->data)
    //        root->left = bst_insert(root->left, val);
    // 3. else if (val > root->data)
    //        root->right = bst_insert(root->right, val);
    // 4. return root;
}

/* BST 查找 */
struct node *bst_search(struct node *root, int val) {
    // 在这里实现 bst_search:
    // 1. if (root == NULL || root->data == val) return root;
    // 2. if (val < root->data) return bst_search(root->left, val);
    // 3. return bst_search(root->right, val);
}

/* BST 删除 -- 三种情况 */
struct node *bst_delete(struct node *root, int val) {
    // 在这里实现 bst_delete:
    // 1. if (root == NULL) return NULL;
    // 2. if (val < root->data)
    //        root->left = bst_delete(root->left, val);
    // 3. else if (val > root->data)
    //        root->right = bst_delete(root->right, val);
    // 4. else { // 找到要删的节点
    //        if (root->left == NULL) { tmp=root->right; free(root); return tmp; }
    //        if (root->right == NULL) { tmp=root->left; free(root); return tmp; }
    //        // 双子: 右子树最小值替换
    //        struct node *succ = find_min(root->right);
    //        root->data = succ->data;
    //        root->right = bst_delete(root->right, succ->data);
    //    }
    // 5. return root;
}

int main(void) {
    struct node *root = NULL;
    // 处理最多两行命令:
    // 第一行: insert 构建树
    // 第二行: search/delete 操作 (可选)
    // 在此实现命令行解析和操作分发
    return 0;
}

阅读骨架后思考: bst_insert 和 bst_search 的代码结构为什么几乎一模一样?删除的三种情况如何递进?find_min 为什么 "一路向左"?

TIP

先不要往下翻看参考解答。在纸上画一棵 BST(如 5,3,7,2,4),手动追踪 insert/search 的递归路径。然后尝试删除 3(叶子)、7(只有右子)、5(有两个孩子)三种情况。

深度讲解

1. 什么是二叉搜索树 (BST)?

1.1 BST 的定义

二叉搜索树(Binary Search Tree)的定义: 对于任意节点,左子树所有值 <= 根值 <= 右子树所有值。

合法的 BST:
       5
      / \
     3   7
    / \   \
   2   4   8

中序遍历: 2 3 4 5 7 8  -> 有序! <- BST 的核心特性

不合法的 BST:
       5
      / \
     3   7
    / \
   2   6       <- 6 在 3 的右子树,但 6 > 5(根!)违反了 BST 性质
     (合法 BST 要求: 右子树中所有值都要大于 根的所有祖先)

IMPORTANT

BST 性质是全局约束,不是局部约束——不能只比较父节点和直接孩子--左子树的所有节点(包括孙子、曾孙)都必须小于根。上面不合法例子中,6 虽然大于直接父节点 3,但小于祖父节点 5,而 6 在祖父 5 的左子树中--这违反了"左子树所有值 < 根"的规则。

1.2 BST 的递归特性

BST 的每个子树本身也是 BST:

       5           <- 整棵树是 BST
      / \
     3   7         <- 以 3 为根的子树是 BST (值: 2,3,4)
    / \   \        <- 以 7 为根的子树是 BST (值: 7,8)
   2   4   8

这个递归特性使得 BST 操作天然适合递归实现。

2. 插入与查找: 镜像操作

2.1 插入

bst_insert.c

struct node *bst_insert(struct node *root, int val) {
    if (root == NULL) return make_node(val);  // 到达空位,创建

    if (val < root->data)
        root->left = bst_insert(root->left, val);
    else if (val > root->data)
        root->right = bst_insert(root->right, val);
    // val == root->data: 已存在,重复值通常忽略

    return root;
}

为什么返回 root? 递归需要把新节点"挂回"树上。父节点的 left 或 right 通过返回值来更新。

插入 4 的跟踪 (树初始有 5,3,7):

bst_insert(5, 4):
  4 < 5 -> root->left = bst_insert(3, 4)

bst_insert(3, 4):
  4 > 3 -> root->right = bst_insert(NULL, 4)

bst_insert(NULL, 4):
  到达空位,创建节点 [4]
  返回 [4]

回到 bst_insert(3, 4): root->right = [4], 返回节点 3
回到 bst_insert(5, 4): root->left = 节点 3, 返回节点 5

结果:
       5
      / \
     3   7
      \
       4

2.2 查找

bst_search.c

struct node *bst_search(struct node *root, int val) {
    if (root == NULL) return NULL;          // 走到空,未找到
    if (val == root->data) return root;     // 找到了!

    if (val < root->data)
        return bst_search(root->left, val);
    else
        return bst_search(root->right, val);
}

2.3 插入与查找的镜像关系

插入路径                         查找路径
root->left = insert(left, val)  search(left, val)
root->right = insert(right, val) search(right, val)
遇到 NULL -> 创建新节点          遇到 NULL -> 返回 NULL(未找到)
返回 root                       返回 root(找到了)

插入和查找沿 BST 性质搜索的路径完全相同,区别只在终点处: 一个创建,一个返回。

3. 删除: 三种情况的递进

删除是 BST 操作中最复杂的部分,需要处理三种情况:

3.1 情况 1: 叶子节点(无孩子)-> 直接删

删除 4:
    5
   / \
  3   7         ->  free(4), 3->right = NULL
   \
    4

结果:
    5
   / \
  3   7

操作: free(root), 返回 NULL。父节点的对应指针设为 NULL。

3.2 情况 2: 只有一个孩子 -> 孩子提升

删除 3 (只有右孩子):
    5
   / \                         5
  3   7         ->  free(3)    / \
   \                         4   7
    4                        (3 被 4 替代)

删除 7 (只有右孩子):
    5
   / \                         5
  3   7         ->  free(7)    / \
     /                         3   8
    8                          (7 被 8 替代)

操作: 保存唯一的孩子 tmp = root->left ? root->left : root->right, free(root), 返回 tmp。孩子"子承父业"提升到被删节点的位置。

3.3 情况 3: 有两个孩子【难点!】-> 右子树最小值替换

删除 5:
       5
      / \
     3   7         目标: 保持 BST 性质,找谁来替代 5?
    / \ / \
   2  4 6  8

找右子树最小值(6)替代:
       6
      / \
     3   7        中序: 2 3 4 6 7 8  <- 仍然有序!
    / \   \
   2  4   8

为什么是右子树最小值?

  - 右子树的所有值 > 被删节点的值
  - 右子树的最小值 < 右子树其他值
  - 所以它恰好位于 被删节点 和 右子树其他值 之间
  - 替换后,BST 性质不变!

(同理,左子树最大值也可以替代,效果等价。)

操作步骤:

找 succ = find_min(root->right) -- 右子树最小值
root->data = succ->data -- 用 succ 的值替换 root
root->right = bst_delete(root->right, succ->data) -- 递归删除 succ(succ 必然是最左节点,属于情况 1 或 2)

3.4 完整删除代码

bst_delete.c

struct node *bst_delete(struct node *root, int val) {
    if (root == NULL) return NULL;

    if (val < root->data)
        root->left = bst_delete(root->left, val);
    else if (val > root->data)
        root->right = bst_delete(root->right, val);
    else {
        /* 找到了要删的节点 */
        /* 情况 1&2: 0 或 1 个孩子 */
        if (root->left == NULL) {
            struct node *tmp = root->right;
            free(root);
            return tmp;
        }
        if (root->right == NULL) {
            struct node *tmp = root->left;
            free(root);
            return tmp;
        }
        /* 情况 3: 两个孩子 */
        struct node *succ = find_min(root->right);
        root->data = succ->data;
        root->right = bst_delete(root->right, succ->data);
    }
    return root;
}

3.5 边界情况

删除不存在的值: 如果 val 不在 BST 中,bst_delete 沿搜索路径递归,但永远不会进入 else 分支(不会匹配到 val == root->data)时最终走到 NULL 时函数返回 NULL,各层递归的 root->left 或 root->right 不变,整棵树保持原样。
删除唯一节点: 当 BST 只有一个节点且需要删除它时,被删节点为叶子,走情况 1(叶子删除),free(root) 后返回 NULL,根指针变为 NULL,得到空树。

4. find_min: 一路向左

find_min.c

struct node *find_min(struct node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

BST 定义保证: 最左节点(沿 left 走到底)的值最小。时间复杂度 O(h),h 为树高。

5. BST 的退化与自平衡

5.1 插入顺序敏感

相同的数据,不同的插入顺序 -> 不同的树形状:

插入顺序 5,3,7,2,4:
       5
      / \
     3   7        高度 h=3,平衡!
    / \
   2   4

插入顺序 2,3,4,5,7:
   2
    \
     3
      \
       4          高度 h=5,退化为链表!
        \
         5
          \
           7

查找性能: O(log n) vs O(n)

5.2 AVL / 红黑树动机

当 BST 退化为链表时,所有操作(插入/查找/删除)从 O(log n) 退化为 O(n)。自平衡树(AVL 树、红黑树)通过旋转操作保持树高约等于 O(log n),保证操作效率。

这是本系列课程之外的高级话题,但理解 BST 的退化问题是对比学习 AVL/红黑树的必要前提。

参考解答

练习: BST 完整操作实现

solution_38_bst_ops.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
    int data;
    struct node *left, *right;
};
struct node *make_node(int val) {
    struct node *p = malloc(sizeof(*p));
    p->data = val;
    p->left = p->right = NULL;
    return p;
}

void inorder(struct node *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

struct node *find_min(struct node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL)
        root = root->left;
    return root;
}

struct node *bst_insert(struct node *root, int val) {
    if (root == NULL) return make_node(val);
    if (val < root->data)
        root->left = bst_insert(root->left, val);
    else if (val > root->data)
        root->right = bst_insert(root->right, val);
    return root;
}

struct node *bst_search(struct node *root, int val) {
    if (root == NULL || root->data == val) return root;
    if (val < root->data)
        return bst_search(root->left, val);
    return bst_search(root->right, val);
}

struct node *bst_delete(struct node *root, int val) {
    if (root == NULL) return NULL;
    if (val < root->data)
        root->left = bst_delete(root->left, val);
    else if (val > root->data)
        root->right = bst_delete(root->right, val);
    else {
        if (root->left == NULL) {
            struct node *tmp = root->right;
            free(root);
            return tmp;
        }
        if (root->right == NULL) {
            struct node *tmp = root->left;
            free(root);
            return tmp;
        }
        struct node *succ = find_min(root->right);
        root->data = succ->data;
        root->right = bst_delete(root->right, succ->data);
    }
    return root;
}

int main(void) {
    struct node *root = NULL;
    for (int ln = 0; ln < 2; ln++) {
        char line[256];
        if (!fgets(line, sizeof(line), stdin)) break;
        int i = 0;
        while (line[i] && line[i] != '\n') i++;
        line[i] = '\0';

        char *cmd = strtok(line, " ");
        if (!cmd) continue;

        if (strcmp(cmd, "insert") == 0) {
            char *tok;
            while ((tok = strtok(NULL, " ")) != NULL) {
                int val = atoi(tok);
                root = bst_insert(root, val);
            }
            printf("inorder: ");
            inorder(root);
            printf("\n");
        } else if (strcmp(cmd, "search") == 0) {
            char *tok = strtok(NULL, " ");
            int val = tok ? atoi(tok) : 0;
            struct node *found = bst_search(root, val);
            printf("%s\n", found ? "found" : "not found");
        } else if (strcmp(cmd, "delete") == 0) {
            printf("inorder: ");
            inorder(root);
            printf("\n");
            char *tok;
            while ((tok = strtok(NULL, " ")) != NULL) {
                int val = atoi(tok);
                root = bst_delete(root, val);
            }
            printf("inorder: ");
            inorder(root);
            printf("\n");
        }
    }
    return 0;
}

核心逻辑:

find_min: 循环沿 left 走到底--BST 最小值在最左。
insert/search: 互为镜像,沿 BST 性质搜索,遇到 NULL 时一个创建、一个返回。
delete: 三种情况递进--前两种情况(叶/单子)直接释放并返回孩子,第三种(双子)走替代-递归删除流程。
返回值 reroot: 每个递归层级重新挂接子树,保证指针正确。

对照检查: find_min 沿 left 走到底了吗?insert 和 search 代码对称吗?delete 中三种情况都覆盖了吗?双子情况用了右子树最小值替换并递归删除了吗?

课堂讨论

为什么 BST 的中序遍历一定是有序的?这个性质是 BST 的充分条件还是必要条件?
bst_insert 和 bst_search 的代码几乎互为镜像--它们在哪里汇合,在哪里分叉?
删除双子节点时,为什么找右子树的最小值(而不是最大值)来替换?左子树的最大值可以吗?
如果 BST 退化成链表,插入/查找/删除的时间复杂度是多少?如何避免这种退化?
递归删除中 root->left = bst_delete(...) 和 root->right = bst_delete(...) 返回的 root 有什么作用?

讨论答案

Q1: BST 中序为什么有序?

这是 BST 定义和中序遍历顺序的直接推论。

BST 定义: 左子树所有值 <= 根值 <= 右子树所有值
中序: 先左子树,再根,再右子树

左子树(小值) -> 根(中间值) -> 右子树(大值)
=> 天然有序!

这是 BST 的"指纹":
  如果中序有序 => 可能是 BST(必要条件)
  如果中序无序 => 一定不是 BST

Q2: insert 和 search 的代码对比

insert(root, val):              search(root, val):
  if (root == NULL)               if (root == NULL)
    return make_node(val);  //创建    return NULL;        //未找到
                                  if (val == root->data)
                                    return root;        //找到!
  if (val < root->data)           if (val < root->data)
    root->left = insert(left,val)   return search(left,val)
  else if (val > root->data)      else
    root->right = insert(right,val)  return search(right,val)
  return root;

汇合: 搜索路径完全相同(val<data 向左, val>data 向右)
分叉: 在 NULL 处(insert 创建,search 返回 NULL)
      在相等处(search 返回,insert 忽略)

Q3: 为什么用右子树最小值?

被删节点左子树: [1,2,3,4]   被删节点=5   右子树: [6,7,8,9]

需要找替代者满足:
  - 大于左子树所有值 -> > 4
  - 小于右子树所有值 -> < 6
  - 候选: 4(左子树最大值) 或 6(右子树最小值)

右子树最小值:
  - 一定 > 所有左子树值(因为它在右子树中)
  - 一定 < 右子树其他值(BST 性质)
  - 删除它很简单(它一定是最左节点,只有右孩子或无孩子)

左子树最大值也可以! 效果等价。只是我们习惯用右子树最小值。

Q4: BST 退化与应对

插入顺序 1,2,3,4,5:
  1 -> 2 -> 3 -> 4 -> 5  (退化为链表)

性能: 所有操作 O(n)

解决方案:
  - AVL 树: 维护平衡因子,高度差超过 1 时旋转
  - 红黑树: 颜色约束 + 旋转,保证 O(log n)
  - 两种树都通过"旋转"操作保持平衡

平衡 BST: 插入/查找/删除 = O(log n) 稳定!

Q5: 递归删除返回 root 的作用

bst_delete 返回 root 是为了"重新挂接子树":

root->left = bst_delete(root->left, val);

如果左子树中删除了某个节点,左子树的结构可能变化:
  - 被删节点是叶子 -> root->left 变成 NULL
  - 被删节点有子 -> root->left 变成那个孩子
  - 被删节点有双子 -> root->left 变成替换后的新子树

通过返回 root 并赋值,每一层递归都正确更新了父节点对子树的引用。

课后练习

统计 BST 节点总数: 编写 int bst_size(struct node *root) 返回 BST 节点数。利用 BST 的递归特性: 总数 = 1 + 左子树节点数 + 右子树节点数。
知识点提示: 与遍历的递归结构同构,空树返回 0。
判断是否为 BST: 编写 int is_bst(struct node *root, int min, int max) 判断一棵树是否为合法的 BST。利用 BST 定义中的"全局约束": 每个节点的值必须在 (min, max) 开区间内。
知识点提示: 递归传递约束范围,根值约束左右子树。注意不能只比较直接父节点。
BST 范围查询: 编写 void range_search(struct node *root, int low, int high) 打印 BST 中所有值在 [low, high] 范围内的节点。利用 BST 性质剪枝: 如果 root->data < low,只搜索右子树;如果 root->data > high,只搜索左子树。
知识点提示: 利用 BST 性质减少搜索范围,O(k+h) 而非 O(n)。
计算 BST 高度: 编写 int bst_height(struct node *root) 返回 BST 的高度。从一组随机数据构建 BST,观察树高与 log2(n) 的差距,直观感受 BST 退化。
知识点提示: 随机插入 build BST,插入顺序影响树高。用 rand() 生成随机序列验证。

参考资料

《算法导论》第 12 章二叉搜索树 -- BST 操作的形式化定义与正确性证明
《数据结构与算法分析 - C 语言描述》§4.3 BST -- BST 的插入/删除实现与复杂度分析
Lesson 36 二叉树遍历 -- BST 的中序验证(前置知识)
Visual BST -- VisuAlgo -- BST 插入/删除的交互式可视化
AVL 树与红黑树 -- BST 自平衡的进阶话题(课外延伸)

"The beauty of a BST is that you only need to know whether to go left or right -- a single comparison halves the search space." -- Robert Sedgewick

Lesson 38: 二叉搜索树 (BST) 操作 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 什么是二叉搜索树 (BST)? ​

1.1 BST 的定义 ​

1.2 BST 的递归特性 ​

2. 插入与查找: 镜像操作 ​

2.1 插入 ​

2.2 查找 ​

2.3 插入与查找的镜像关系 ​

3. 删除: 三种情况的递进 ​

3.1 情况 1: 叶子节点(无孩子)-> 直接删 ​

3.2 情况 2: 只有一个孩子 -> 孩子提升 ​

3.3 情况 3: 有两个孩子【难点!】-> 右子树最小值替换 ​

3.4 完整删除代码 ​

3.5 边界情况 ​

4. find_min: 一路向左 ​

5. BST 的退化与自平衡 ​

5.1 插入顺序敏感 ​

5.2 AVL / 红黑树动机 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​