面试官最爱问的二叉搜索树（BST）删除操作，图解+代码带你一次搞定所有情况
二叉搜索树（BST）是面试中高频出现的数据结构，而删除操作往往是考察的重点和难点。很多候选人在面对"如何删除BST节点"这个问题时，要么思路混乱，要么代码漏洞百出。本文将用最直观的图解和最清晰的代码，帮你彻底掌握BST删除的所有情况。
1. 二叉搜索树删除操作的核心逻辑
BST删除之所以复杂，是因为需要维护二叉搜索树的性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点。删除节点时，我们必须保证这一性质不被破坏。
删除操作通常分为三种情况处理：
- 叶子节点：直接删除，不影响树结构
- 单子节点：用子节点替代被删除节点
- 双子节点：找到合适的替代节点，保持BST性质
实际编码中，前两种情况可以合并处理，因为它们都只需要简单的指针调整。
让我们看一个具体例子。假设有以下BST：
8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13如果要删除节点3，它有两个子节点，属于第三种情况；而删除节点1（叶子节点）或节点10（单子节点）则属于前两种情况。
2. 删除叶子节点和单子节点的情况
这两种情况相对简单，我们先用图示展示处理方式，再给出对应的代码实现。
2.1 删除叶子节点
以删除节点1为例：
- 找到节点1的父节点3
- 将父节点3的左指针置为nullptr
- 删除节点1
图示变化：
删除前： 3 / 1 删除后： 32.2 删除单子节点
以删除节点10为例：
- 找到节点10的父节点8
- 将父节点8的右指针指向节点10的子节点14
- 删除节点10
图示变化：
删除前： 8 \ 10 \ 14 删除后： 8 \ 142.3 代码实现
bool erase(Node* &root, int key) { Node* parent = nullptr; Node* curr = root; // 查找要删除的节点 while (curr && curr->key != key) { parent = curr; curr = (key < curr->key) ? curr->left : curr->right; } if (!curr) return false; // 未找到 // 情况1和2：左或右子节点为空 if (!curr->left || !curr->right) { Node* child = curr->left ? curr->left : curr->right; if (!parent) { // 删除的是根节点 root = child; } else { if (parent->left == curr) { parent->left = child; } else { parent->right = child; } } delete curr; } // 情况3处理见下一节 }3. 删除双子节点的情况
这是最复杂的情况，我们需要找到一个合适的节点来替代被删除的节点，同时保持BST性质。通常有两种策略：
- 前驱替代法：用左子树的最大节点替代
- 后继替代法：用右子树的最小节点替代
我们以后继替代法为例，讲解如何删除具有两个子节点的节点。
3.1 后继替代法步骤
以删除节点3为例：
- 找到节点3的右子树中的最小节点4（最左节点）
- 将节点4的值复制到节点3
- 删除原来的节点4（此时节点4最多只有一个子节点）
图示过程：
删除前： 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 步骤1-2：找到后继节点4并复制值 8 / \ 4 10 / \ \ 1 6 14 / \ / 4 7 13 步骤3：删除原来的节点4 8 / \ 4 10 / \ \ 1 6 14 \ / 7 133.2 代码实现
// 接前面的erase函数 else { // 情况3：有两个子节点 // 找到右子树的最小节点 Node* successor = curr->right; Node* successorParent = curr; while (successor->left) { successorParent = successor; successor = successor->left; } // 复制值 curr->key = successor->key; // 删除后继节点 if (successorParent->left == successor) { successorParent->left = successor->right; } else { successorParent->right = successor->right; } delete successor; }4. 递归实现与边界条件处理
虽然非递归实现效率高，但递归版本通常更简洁。让我们看看递归实现如何处理删除操作。
4.1 递归实现
bool eraseRecursive(Node* &root, int key) { if (!root) return false; if (key < root->key) { return eraseRecursive(root->left, key); } else if (key > root->key) { return eraseRecursive(root->right, key); } else { // 找到要删除的节点 if (!root->left) { Node* temp = root->right; delete root; root = temp; } else if (!root->right) { Node* temp = root->left; delete root; root = temp; } else { // 有两个子节点 Node* successor = root->right; while (successor->left) { successor = successor->left; } root->key = successor->key; eraseRecursive(root->right, successor->key); } return true; } }4.2 边界条件与常见错误
在实际面试中，候选人常犯以下错误：
- 忘记处理根节点删除：当删除的是根节点时，需要特殊处理
- 内存泄漏：删除节点后忘记释放内存
- 指针错误：在调整指针时，错误地修改了父节点的指针
- 后继节点处理不当：没有正确处理后继节点的子节点
在面试中，建议先画出示例树，然后逐步讲解删除过程，最后再写代码。这样可以避免很多逻辑错误。
5. 时间复杂度分析与常见面试问题
面试官通常会围绕BST删除操作提出一些延伸问题，以考察候选人的理解深度。
5.1 时间复杂度分析
BST删除操作的时间复杂度取决于树的高度：
- 最好情况：树是平衡的，高度为O(log n)，时间复杂度为O(log n)
- 最坏情况：树退化为链表，高度为O(n)，时间复杂度为O(n)
常见面试问题：
BST删除的平均时间复杂度是多少？
- 对于随机构建的BST，平均高度为O(log n)，因此平均时间复杂度为O(log n)
最坏情况下BST的性能如何？如何优化？
- 最坏情况下BST退化为链表，查找、插入、删除操作都变为O(n)
- 可以通过自平衡二叉搜索树（如AVL树、红黑树）来保证最坏情况下仍然是O(log n)
为什么通常选择右子树的最小节点作为后继？
- 因为右子树的最小节点一定大于左子树所有节点，小于右子树其他节点，能够保持BST性质
- 选择左子树的最大节点（前驱）同样可行
5.2 性能优化思路
当面试官问到如何优化BST时，可以提到以下方向：
自平衡二叉搜索树：
- AVL树：严格的平衡条件，查找效率高，但插入删除可能需要频繁旋转
- 红黑树：近似平衡，插入删除操作更高效，被广泛应用于STL等库中
其他树结构：
- B树/B+树：适合磁盘存储和数据库索引
- 跳表：替代平衡树的概率数据结构，实现更简单
工程实践中的优化：
- 对于静态数据，可以先排序再构建平衡BST
- 对于动态数据，可以定期重构树来保持平衡
