CC++ & Algorithm

二叉搜索树的插入与删除

较难3
语言版本：通用
概述：用整理书架的例子讲解BST的插入和删除操作，包括删除的三种情况（无孩子、一个孩子、两个孩子）及用前驱或后继替代的方法，并给出完整代码。

二叉搜索树的插入与删除——像整理书架一样管理数据

为什么需要二叉搜索树？

想象你有一个装满故事书的书架，每本书的书名按拼音顺序排列。如果你想快速找到一本《西游记》，你不必一本本地翻，而是从中间（根）开始：如果“西”的拼音比当前书的拼音大，就往右边找；如果小，就往左边找。这样每次比较都能排除一半的书，效率很高。这个思路就是二叉搜索树（Binary Search Tree，BST） 的核心思想——每个节点左边都比它小，右边都比它大。

二叉搜索树常用于需要快速查找、插入和删除的场合，比如字典、集合、数据库索引等。今天我们就来学习如何在 BST 中插入一本“新书”和删除一本“旧书”，同时保持整个书架始终有序。

1. 插入操作：找到空位，放书

插入非常简单，就像你在已有的有序书架上找空位放新书。做法和查找一模一样：从根开始，比较新书和当前节点的值。如果新书的值小于当前节点，就往左子树走；如果大于，就往右子树走。一直走到某个节点的左孩子或右孩子为空，就在那个空位上放一本新书。

小例子：假设已有 BST 包含节点 50, 30, 70, 20, 40, 80, 10（结构见下图），现在要插入 25。

       50
      /  \
    30    70
   /  \    \
 20   40   80
/
10
  1. 从根 50 开始：25 < 50 → 向左到 30
  2. 25 < 30 → 向左到 20
  3. 25 > 20 → 向右，20 的右孩子为空 → 插入 25 作为 20 的右孩子

插入后，树依然保持 BST 性质：所有左子节点比父节点小，右子节点比父节点大。

注意：如果遇到值相等的情况，要不要插入？通常我们说 BST 不允许重复，或者可以约定用某种方式处理（比如放在右子树或计数）。这里我们采用“不插入重复值”。

代码片段（C++ 递归实现）：

TreeNode* insert(TreeNode* node, int x) {
    if (node == nullptr) return new TreeNode(x);   // 找到空位，创建新节点
    if (x < node->val)
        node->left = insert(node->left, x);       // 向左走
    else if (x > node->val)
        node->right = insert(node->right, x);     // 向右走
    // 相等则不做操作
    return node;
}

2. 删除操作：三种情况，对症下药

删除比插入麻烦，因为删除一个节点后，还要保证剩下的节点依然满足“左小右大”。根据被删除节点的孩子数量，分成三种情况。

情况1：删除叶子节点（没有孩子）

就像从书架上拿走一本两侧都没有倚靠的书，直接抽掉就行，不用管其他书。

例子：删除上图中的节点 10（叶子节点）。它没有左孩子和右孩子。只需要把它的父节点 20 的左指针设为 nullptr 即可。

代码处理：在递归删除函数中，如果发现当前节点没有左孩子且没有右孩子（实际上会在“只有一个孩子”的代码中一并处理，但可以单独判断），直接返回 nullptr。

情况2：删除只有一个孩子的节点

相当于书架上有一本书，它旁边只有一本书靠着。拿走这本书后，让它的孩子直接连到它的父节点上，就像把靠着的书挪过来顶替位置。

例子：删除节点 20（它有一个左孩子 10）。树的结构如下（部分）：

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

删除 20 后，让 30 的左指针直接指向 20 的左孩子 10。结果：

       50
      /  \
    30    70
   /  \    \
 10   40   80

注意：这里 20 的右孩子为空，所以用左孩子顶替。如果节点只有右孩子，就用右孩子顶替。

代码处理：

if (node->left == nullptr) {
    // 左孩子为空，返回右孩子（可能也为空，正好删除）
    TreeNode* rightChild = node->right;
    delete node;
    return rightChild;
} else if (node->right == nullptr) {
    // 右孩子为空，返回左孩子
    TreeNode* leftChild = node->left;
    delete node;
    return leftChild;
}

情况3：删除有两个孩子的节点

这是最复杂的情况。想象书架上有一本书（例如 30），左右两边都堆满了书。如果直接抽走它，左右两边的书就断了联系，而且无法保持有序。怎么办？聪明的做法是：找一本合适的“替代书”来填空，这本替代书必须比左边所有书都大，同时比右边所有书都小。

这样的替代书有两个候选：

  • 中序后继：被删节点右子树中最小的节点（一直往左走到底）。
  • 中序前驱：被删节点左子树中最大的节点（一直往右走到底）。

两者都可以。我们常用中序后继，因为它的左子树一定为空（否则更小的还能左走），删除它时只会退化到情况1或2，处理更简单。

具体步骤：

  1. 找到被删除节点 node 的右子树中的最小节点 successor。
  2. 把 successor 的值复制给 node（替换内容）。
  3. 删除原来的 successor 节点（它一定没有左孩子，可能有一个右孩子）。
  4. 由于 successor 被删除了，但它的值已经移到 node 位置，所以 BST 性质保持。

例子：删除根节点 50（有两个孩子 30 和 70）。

  • 右子树最小节点是 70？不对，70 的左子树可能还有更小。这里右子树是 70 -> 80，最小节点是 70 本身（它没有左孩子）。
  • 将 50 的值替换为 70。
  • 然后删除原来的 70 节点（它只有一个右孩子 80，属于情况2）。
  • 结果：根的值变为 70，它的右孩子变为 80（删除 70 后，80 被提升）。

更典型例子：删除节点 30（图中 30 有两个孩子 20 和 40）。

  • 30 的右子树最小节点：从 40 往左走，40 没有左孩子，所以最小节点就是 40。
  • 把 30 的值改为 40。
  • 删除原来 40 的位置（它是 30 的右孩子，且没有左孩子，只有一个右孩子吗？这里 40 是叶子，直接删除）。
  • 结果：30 的位置变成了 40，树仍然有序。

代码处理（C++）：

// 有两个孩子
TreeNode* successor = findMin(node->right);   // 找右子树最小节点
node->val = successor->val;                  // 替换值
node->right = remove(node->right, successor->val); // 递归删除后继节点

findMin 就是不断向左走：

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

3. 新手常见错误

  1. 忘记给父节点赋值
    递归删除时，如果只处理了当前节点，却没有把返回的新子节点赋值给父节点的指针，就会导致树断裂。例如：

    // 错误写法
if (x < node->val) {
    remove(node->left, x);   // 忘记赋值 node->left = ...
}

    正确做法是 node->left = remove(node->left, x);

  2. 删除有两个孩子的节点时，直接删除节点本身
    有人会把节点删掉，然后尝试把左子树和右子树连接起来，比如把左子树的最大节点或右子树的最小节点提上来，但操作复杂容易出错。用值替换+删除后继是最稳妥的方法。

  3. 没有处理递归返回的根节点变化
    当删除根节点时，根指针会改变。所以 main 函数中调用 remove 后，应该更新 root，例如 root = remove(root, x);。

  4. 内存泄漏
    C++ 中 new 的节点必须 delete。如果只修改指针而不释放内存，会导致内存泄漏。在 Python 中不需要手动管理，但也要注意引用。

4. 完整可运行的代码示例

下面给出 C++ 和 Python 两个版本的完整代码，包含插入、删除、中序遍历（用于验证）。代码中的变量名都简短，且每行变量定义都有中文注释，方便理解。

C++ 版本

#include <iostream>
using namespace std;

struct TreeNode {
    int val;                // 节点值
    TreeNode* left;         // 左孩子指针
    TreeNode* right;        // 右孩子指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
private:
    TreeNode* root;         // 树的根节点

    // 插入辅助函数
    TreeNode* insert(TreeNode* node, int x) {
        if (node == nullptr) return new TreeNode(x);   // 空位，插入新节点
        if (x < node->val)
            node->left = insert(node->left, x);       // 向左递归
        else if (x > node->val)
            node->right = insert(node->right, x);     // 向右递归
        return node;
    }

    // 查找以node为根的树中的最小值节点
    TreeNode* findMin(TreeNode* node) {
        while (node->left != nullptr)    // 一直向左走到叶子
            node = node->left;
        return node;
    }

    // 删除辅助函数，返回新根
    TreeNode* remove(TreeNode* node, int x) {
        if (node == nullptr) return nullptr;   // 没找到要删的值

        if (x < node->val) {
            node->left = remove(node->left, x);          // 在左子树中删除
        } else if (x > node->val) {
            node->right = remove(node->right, x);        // 在右子树中删除
        } else {
            // 找到了要删除的节点
            // 情况1和2：没有孩子或只有一个孩子
            if (node->left == nullptr) {
                // 左孩子为空，用右孩子顶替（右孩子可能也为空）
                TreeNode* rightChild = node->right;
                delete node;
                return rightChild;
            } else if (node->right == nullptr) {
                // 右孩子为空，用左孩子顶替
                TreeNode* leftChild = node->left;
                delete node;
                return leftChild;
            }
            // 情况3：有两个孩子
            // 找到右子树的最小节点（中序后继）
            TreeNode* successor = findMin(node->right);
            // 用后继的值替换当前节点
            node->val = successor->val;
            // 删除后继节点（它在右子树中，且一定没有左孩子）
            node->right = remove(node->right, successor->val);
        }
        return node;
    }

    // 释放整棵树的内存
    void destroy(TreeNode* node) {
        if (node) {
            destroy(node->left);
            destroy(node->right);
            delete node;
        }
    }

public:
    BST() : root(nullptr) {}
    ~BST() { destroy(root); }

    void insert(int x) { root = insert(root, x); }
    void remove(int x) { root = remove(root, x); }

    // 中序遍历（用于测试）
    void inorder(TreeNode* node) {
        if (node == nullptr) return;
        inorder(node->left);
        cout << node->val << " ";
        inorder(node->right);
    }
    void printInorder() {
        inorder(root);
        cout << endl;
    }
};

int main() {
    BST tree;
    // 插入一些值：50,30,70,20,40,80,10
    for (int v : {50,30,70,20,40,80,10})
        tree.insert(v);

    cout << "删除前中序遍历: ";
    tree.printInorder();  // 10 20 30 40 50 70 80

    tree.remove(30);
    cout << "删除30后中序遍历: ";
    tree.printInorder();  // 10 20 40 50 70 80

    tree.remove(20);
    cout << "删除20后中序遍历: ";
    tree.printInorder();  // 10 40 50 70 80

    return 0;
}

Python 版本

class TreeNode:
    def __init__(self, val):
        self.val = val          # 节点值
        self.left = None        # 左孩子
        self.right = None       # 右孩子

class BST:
    def __init__(self):
        self.root = None

    def insert(self, x):
        def _insert(node, x):
            if node is None:
                return TreeNode(x)
            if x < node.val:
                node.left = _insert(node.left, x)
            elif x > node.val:
                node.right = _insert(node.right, x)
            return node
        self.root = _insert(self.root, x)

    def find_min(self, node):
        """返回以node为根的树中的最小值节点"""
        while node.left:
            node = node.left
        return node

    def remove(self, x):
        def _remove(node, x):
            if node is None:
                return None
            if x < node.val:
                node.left = _remove(node.left, x)
            elif x > node.val:
                node.right = _remove(node.right, x)
            else:
                # 找到要删除的节点
                # 情况1和2：最多一个孩子
                if node.left is None:
                    return node.right
                if node.right is None:
                    return node.left
                # 情况3：两个孩子
                # 找右子树最小节点（后继）
                successor = self.find_min(node.right)
                # 复制值
                node.val = successor.val
                # 删除后继
                node.right = _remove(node.right, successor.val)
            return node
        self.root = _remove(self.root, x)

    def inorder(self, node):
        if node is None:
            return []
        return self.inorder(node.left) + [node.val] + self.inorder(node.right)

    def print_inorder(self):
        print(self.inorder(self.root))

# 测试
tree = BST()
for v in [50, 30, 70, 20, 40, 80, 10]:
    tree.insert(v)

print("删除前:", end=" ")
tree.print_inorder()  # [10,20,30,40,50,70,80]

tree.remove(30)
print("删除30后:", end=" ")
tree.print_inorder()  # [10,20,40,50,70,80]

tree.remove(20)
print("删除20后:", end=" ")
tree.print_inorder()  # [10,40,50,70,80]

运行两个程序，输出结果都是有序序列，证明插入和删除操作正确。

5. 总结与扩展

  • 插入：像找空位放书一样简单，递归比较直到空位。
  • 删除：分三种情况——
    • 无孩子：直接移除。
    • 一个孩子：用孩子顶替。
    • 两个孩子：用右子树最小节点（后继）或左子树最大节点（前驱）替换值，然后删除那个节点。
  • 时间复杂度：插入和删除都是 O(h)，h 是树高。如果树退化成链表（比如插入有序数据），h = n，性能很差。因此我们需要平衡二叉搜索树（如 AVL 树、红黑树）来保证 h = O(log n)。
  • 相关知识点：如果你想进一步学习，可以搜索：
    • AVL 树的平衡旋转
    • 红黑树的颜色与旋转
    • 二叉搜索树的遍历（前序、中序、后序、层序）
    • 堆（另一种树结构，用于优先队列）

现在你已经掌握了 BST 的核心操作，接下来可以试着写一个程序，实现一个简单的学生成绩管理系统，用 BST 存储学号和分数，支持添加、删除和按名次查询。祝你编码愉快！

例题精讲

1单选题

在二叉搜索树中插入一个新节点，最终该节点会成为什么类型的节点？

A根节点
B叶子节点
C内部节点
D可能是叶子或内部节点
2判断题

删除二叉搜索树中一个度为2的节点时，通常用它的中序后继节点来替换。

3填空题
下面是二叉搜索树删除操作中查找最小节点的函数，请填空。
struct TreeNode* minValueNode(struct TreeNode* node) {
    struct TreeNode* current = node;
    while (current && current->left != NULL)
        current = current->___;
    return current;
}
4判断题

在二叉搜索树中，如果待删除节点有两个子节点，可以用其左子树中的最大节点来替换。

5单选题

在二叉搜索树中插入一个已经存在的键值，通常会发生什么？

A插入重复节点
B忽略插入
C替换原有节点
D导致树不平衡