异常教程

二分搜索树节点删除（长文讲解）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

在数据结构与算法的学习中，二分搜索树（Binary Search Tree，简称 BST）因其高效的搜索、插入和删除操作而备受关注。然而，对于许多编程初学者和中级开发者来说，二分搜索树节点删除的实现过程常常成为理解的难点。这一操作不仅需要对树的结构有清晰的认识，还需要灵活运用递归或迭代方法，同时处理多种边界条件。本文将从基础概念出发，逐步拆解节点删除的三种核心场景，并通过代码示例和实际案例，帮助读者掌握这一重要技能。

二分搜索树的结构与特性

核心定义与性质

二分搜索树是一种基于二叉树结构的有序数据集合，其每个节点的值满足以下规则：

  • 左子树中的所有节点值 小于 父节点值；
  • 右子树中的所有节点值 大于 父节点值；
  • 子树本身也遵循相同的规则。

通过这一特性，二分搜索树能够实现高效的搜索、插入和删除操作，平均时间复杂度为 O(log N)。

形象比喻：树的“家族等级”

可以将二分搜索树想象为一个家族族谱：

  • 父节点是“家长”，左子节点是“年轻一代”（值更小），右子节点是“年长一代”（值更大）；
  • 每个分支都严格遵循“左小右大”的规则，确保家族成员的有序性。

节点删除的三种场景

删除二分搜索树中的一个节点时，需要根据该节点的子节点数量（0、1 或 2 个）选择不同的处理策略。以下是三种核心场景的详细分析：

场景 1：删除叶子节点（无子节点）

条件：目标节点没有左子节点和右子节点。
操作：直接删除该节点即可。
比喻：家族中某成员无子女，直接从族谱中移除即可。

示例

假设树中有一个节点值为 5，且其左、右子节点均为 null，删除后树的结构不变，仅移除该节点。

场景 2：删除单子节点的节点

条件：目标节点有一个子节点（左或右子节点存在，另一个不存在）。
操作：将子节点直接替换到目标节点的位置，保持树的结构。
比喻：家族中某成员有一个子女，直接让子女继承其位置，无需调整其他分支。

示例

假设节点值为 8，其只有右子节点 9。删除后，节点 9 将取代节点 8 的位置，成为父节点的右子节点。

场景 3：删除双子节点的节点

条件：目标节点同时拥有左、右子节点。
操作：需找到一个“替代节点”来维持树的有序性。通常有两种选择：

  1. 前驱节点：左子树中最大的节点（即左子树的最右节点）；
  2. 后继节点：右子树中最小的节点（即右子树的最左节点）。
    比喻：家族中某成员有两个子女，需选择一位“接班人”继承其位置，同时确保家族等级规则不变。

示例

假设删除节点值为 10，其左子树最大节点为 9，右子树最小节点为 11。可以选择将 9 或 11 替换到 10 的位置，并删除原替代节点。

代码实现：递归法与具体步骤

基础数据结构定义

以下为 Python 语言的二分搜索树节点定义：

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

删除节点的核心函数

def delete_node(root, key):
    if not root:
        return None

    # 递归寻找目标节点
    if key < root.value:
        root.left = delete_node(root.left, key)
    elif key > root.value:
        root.right = delete_node(root.right, key)
    else:
        # 场景 1：无子节点
        if not root.left and not root.right:
            return None
        # 场景 2：单子节点
        elif not root.left or not root.right:
            return root.left if root.left else root.right
        # 场景 3：双子节点
        else:
            # 寻找后继节点（右子树的最小值）
            successor = root.right
            while successor.left:
                successor = successor.left
            # 将后继节点值替换到当前节点
            root.value = successor.value
            # 删除后继节点（递归调用）
            root.right = delete_node(root.right, successor.value)
    return root

代码逻辑解析

  1. 递归定位：通过比较 key 与当前节点值，逐步向左或右子树递归查找目标节点。
  2. 处理场景：
    • 场景 1：直接返回 None，释放节点。
    • 场景 2：返回存在的子节点，替代当前节点。
    • 场景 3：通过寻找后继节点（此处选择右子树的最小值），将后继值替换到当前节点，再递归删除后继节点（此时后继节点变为场景 1 或 2）。

实际案例：删除操作的分步演示

假设有一棵二分搜索树，结构如下：

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

任务：删除节点值为 10。

步骤分解

  1. 定位目标节点：找到值为 10 的节点，其左子节点为 None，右子节点为 14。
  2. 判断场景：该节点有右子节点，属于场景 2。
  3. 执行操作：将右子节点 14 直接替换到原 10 的位置，删除原 10 节点。

删除后的树结构：

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

优化与常见问题

关键优化点

  1. 后继/前驱节点选择：选择后继或前驱节点对树的平衡性影响较小。实践中通常选择右子树的最小值（后继节点）。
  2. 递归深度控制：对于极端倾斜的树（如退化为链表），递归可能导致栈溢出。可改用迭代法实现。

常见问题与解决

  • 问题：删除后树的结构是否仍满足二分搜索树规则？
    解决：通过替代节点的选择逻辑，始终保证“左小右大”规则。
  • 问题：如何处理多个相同值的节点？
    解决：通常二分搜索树不允许重复值，若需支持，需在插入时定义规则（如允许右子树存储相同值）。

总结：掌握节点删除的关键路径

通过本文的讲解，读者可以清晰理解二分搜索树节点删除的三种核心场景，并通过代码实现和案例演示掌握具体操作。这一过程不仅需要对树结构的深刻理解，还需要对递归逻辑和边界条件的精准把控。对于编程学习者而言，建议通过以下步骤逐步提升：

  1. 手动绘制树结构：在纸上模拟删除操作，理解节点替换的直观效果；
  2. 逐步调试代码：通过打印中间结果或使用调试工具，观察递归过程；
  3. 设计测试用例：覆盖所有场景（如删除根节点、中间节点、叶子节点等）。

掌握二分搜索树节点删除不仅是算法能力的体现，更是对数据结构本质理解的检验。这一技能在实际开发中广泛应用于数据库索引、缓存系统等领域，是成为一名专业开发者的重要基石。

关键词布局回顾：
本文通过自然段落和代码示例，多次提及“二分搜索树节点删除”的核心操作场景，确保关键词“二分搜索树节点删除”在内容中合理分布，同时兼顾了技术深度与可读性。

最新发布

查看更多文章