二叉搜索树（BST）的删除操作详解

字数 1842 2025-11-26 22:09:51

二叉搜索树（BST）的删除操作详解

二叉搜索树（BST）是一种基础且重要的数据结构，其删除操作相对复杂，因为它需要维护BST的性质：对于任意节点，其左子树的所有节点值都小于它，右子树的所有节点值都大于它。

1. 删除操作的基本情况分析

删除一个节点时，根据该节点拥有的子节点数量，可以分为三种基本情况：

情况一：待删除节点是叶子节点（无子节点）
- 描述：这是最简单的情况。节点没有左孩子也没有右孩子。
- 操作：直接将其父节点指向它的指针置为空（null），然后释放该节点即可。
- 示例：在树 [5, 3, 7] 中删除节点 3。节点 3 是叶子节点，只需将其父节点（5）的左指针置空。
情况二：待删除节点只有一个子节点
- 描述：节点只有左孩子或只有右孩子。
- 操作：将其唯一的那个子节点“提升”到它自己的位置。具体来说，就是让其父节点直接指向它的那个子节点，然后释放该节点。
- 示例：在树 [5, 3, 7, 4] 中删除节点 3。节点 3 有一个右孩子 4。我们需要将节点 5（父节点）的左指针，从指向节点 3 改为直接指向节点 4。
情况三：待删除节点有两个子节点
- 描述：这是最复杂的情况。节点同时拥有左孩子和右孩子。
- 核心思想：我们不能简单地删除这个节点，因为那样会得到两颗分离的子树。我们的策略是，找到一个合适的值来替换待删除节点的值，然后转而删除那个提供值的、更容易删除的节点。
- 选择合适的“继任者”：这个继任者必须能够维持BST的性质。它必须比左子树的所有节点都大，同时比右子树的所有节点都小。有两个候选者符合要求：
  1. 左子树中的最大值节点（即左子树最右边的节点）。
  2. 右子树中的最小值节点（即右子树最左边的节点）。
- 通用步骤（以选择右子树最小节点为例）：
  1. 在待删除节点的右子树中，找到值最小的节点（这个节点是右子树中最左边的节点，它一定没有左孩子，最多只有一个右孩子）。
  2. 用这个最小节点的值覆盖待删除节点的值。
  3. 现在，问题转化为删除这个右子树中的最小节点。因为这个节点是最左边的，它最多只有一个右孩子，所以它的删除就退化到了情况一（叶子节点） 或情况二（只有一个子节点），变得非常简单。

2. 详细步骤与图解

我们通过一个具体例子来完整走一遍流程。假设要删除下图中值为 12 的根节点。

        12
       /  \
      5    18
     / \   / \
    3   9 15  19
       /   \
      7     17

步骤一：定位待删除节点
- 从根节点 12 开始，找到要删除的节点就是它本身。该节点有两个子节点（5 和 18），属于情况三。
步骤二：寻找继任者
- 选择策略：找右子树的最小节点。
- 从右子节点 18 开始，一直向左走。18 -> 15 -> 17。节点 17 没有左孩子了，所以 17 就是右子树的最小节点。
步骤三：值替换
- 将待删除节点 12 的值替换为 17。此时树的结构变为（值已变，连接关系未变）：
```
      17    <-- 值从12改为17
     /  \
    5    18
   / \   / \
  3   9 15  19
     /   \
    7     17  <-- 这个节点值还是17
```
- 注意，现在树中有两个值为 17 的节点，这违反了BST的唯一性。所以我们需要进行下一步。
步骤四：删除继任者节点
- 原问题“删除值为12的节点” now 转化为 “删除原来那个值为17的节点（右子树的最小节点）”。
- 分析这个继任者节点（原来的 17）：
  - 它是最左边的节点，所以它没有左孩子。
  - 它有一个右孩子吗？在我们的例子中，它没有。所以它是一个叶子节点。
- 因此，删除这个节点属于情况一。直接将其父节点（15）指向它的指针（右指针）置空即可。

最终结果：

      17
     /  \
    5    18
   / \   /
  3   9 15
     /   \
    7    null  <-- 原来的17节点被删除

这棵树仍然是一棵有效的BST。

3. 边界情况与代码实现要点

在编写代码时，需要注意递归或迭代的边界条件。

递归实现思路：
1. 递归查找待删除节点。
2. 找到后，根据三种情况处理。
3. 对于情况三，递归调用删除函数来删除那个继任者节点。
关键细节：
- 内存管理：在C++等需要手动管理内存的语言中，记得 delete 或 free 被移除的节点。
- 根节点的删除：如果待删除的是根节点，需要特殊处理更新树的根指针。在递归实现中，通常通过返回值来更新父节点的指针。
- 重复值：标准的BST定义通常不允许重复值。如果允许，需要在设计时明确规则（例如，将重复值放在左子树或右子树，或使用计数器）。

通过这种分情况讨论和“替换-删除”的策略，BST的删除操作可以在 O(h) 的时间复杂度内完成，其中 h 是树的高度。在平衡BST中，h = log(n)，因此效率很高。

二叉搜索树（BST）的删除操作详解二叉搜索树（BST）是一种基础且重要的数据结构，其删除操作相对复杂，因为它需要维护BST的性质：对于任意节点，其左子树的所有节点值都小于它，右子树的所有节点值都大于它。 1. 删除操作的基本情况分析删除一个节点时，根据该节点拥有的子节点数量，可以分为三种基本情况：情况一：待删除节点是叶子节点（无子节点）描述：这是最简单的情况。节点没有左孩子也没有右孩子。操作：直接将其父节点指向它的指针置为空（ null ），然后释放该节点即可。示例：在树 [5, 3, 7] 中删除节点 3 。节点 3 是叶子节点，只需将其父节点（ 5 ）的左指针置空。情况二：待删除节点只有一个子节点描述：节点只有左孩子或只有右孩子。操作：将其唯一的那个子节点“提升”到它自己的位置。具体来说，就是让其父节点直接指向它的那个子节点，然后释放该节点。示例：在树 [5, 3, 7, 4] 中删除节点 3 。节点 3 有一个右孩子 4 。我们需要将节点 5 （父节点）的左指针，从指向节点 3 改为直接指向节点 4 。情况三：待删除节点有两个子节点描述：这是最复杂的情况。节点同时拥有左孩子和右孩子。核心思想：我们不能简单地删除这个节点，因为那样会得到两颗分离的子树。我们的策略是，找到一个合适的值来替换待删除节点的值，然后转而删除那个提供值的、更容易删除的节点。选择合适的“继任者” ：这个继任者必须能够维持BST的性质。它必须比左子树的所有节点都大，同时比右子树的所有节点都小。有两个候选者符合要求：左子树中的最大值节点（即左子树最右边的节点）。右子树中的最小值节点（即右子树最左边的节点）。通用步骤（以选择右子树最小节点为例）：在待删除节点的右子树中，找到值最小的节点（这个节点是右子树中最左边的节点，它一定没有左孩子，最多只有一个右孩子）。用这个最小节点的值覆盖待删除节点的值。现在，问题转化为删除这个右子树中的最小节点。因为这个节点是最左边的，它最多只有一个右孩子，所以它的删除就退化到了情况一（叶子节点）或情况二（只有一个子节点），变得非常简单。 2. 详细步骤与图解我们通过一个具体例子来完整走一遍流程。假设要删除下图中值为 12 的根节点。步骤一：定位待删除节点从根节点 12 开始，找到要删除的节点就是它本身。该节点有两个子节点（ 5 和 18 ），属于情况三。步骤二：寻找继任者选择策略：找右子树的最小节点。从右子节点 18 开始，一直向左走。 18 -> 15 -> 17 。节点 17 没有左孩子了，所以 17 就是右子树的最小节点。步骤三：值替换将待删除节点 12 的值替换为 17 。此时树的结构变为（值已变，连接关系未变）：注意，现在树中有两个值为 17 的节点，这违反了BST的唯一性。所以我们需要进行下一步。步骤四：删除继任者节点原问题“删除值为12的节点” now 转化为 “删除原来那个值为17的节点（右子树的最小节点）”。分析这个继任者节点（原来的 17 ）：它是最左边的节点，所以它没有左孩子。它有一个右孩子吗？在我们的例子中，它没有。所以它是一个叶子节点。因此，删除这个节点属于情况一。直接将其父节点（ 15 ）指向它的指针（右指针）置空即可。最终结果：这棵树仍然是一棵有效的BST。 3. 边界情况与代码实现要点在编写代码时，需要注意递归或迭代的边界条件。递归实现思路：递归查找待删除节点。找到后，根据三种情况处理。对于情况三，递归调用删除函数来删除那个继任者节点。关键细节：内存管理：在C++等需要手动管理内存的语言中，记得 delete 或 free 被移除的节点。根节点的删除：如果待删除的是根节点，需要特殊处理更新树的根指针。在递归实现中，通常通过返回值来更新父节点的指针。重复值：标准的BST定义通常不允许重复值。如果允许，需要在设计时明确规则（例如，将重复值放在左子树或右子树，或使用计数器）。通过这种分情况讨论和“替换-删除”的策略，BST的删除操作可以在 O(h) 的时间复杂度内完成，其中 h 是树的高度。在平衡BST中，h = log(n)，因此效率很高。