数据结构与算法 / 系统课时

二叉搜索树的删除

二叉搜索树的删除

删除操作既要移除目标节点,又要保持二叉搜索树的有序约束。本课把删除分为叶子、单子节点和双子节点三类,并用中序后继完成可运行实现与结果验证。

学习目标

  • 能区分三类删除情况并正确连接剩余子树
  • 理解中序后继和中序前驱在双子节点删除中的作用
  • 能分析删除操作的复杂度与结构边界

三种删除情况

找到目标节点后,处理方式取决于它拥有的子节点数量。叶子节点可以直接删除;只有一个子节点时,由该子节点接替目标位置;左右子节点都存在时,需要选择一个不会破坏有序性的替代值。

常用方案是取右子树中的最小节点作为中序后继。先把后继值复制到目标节点,再从右子树删除原后继节点。也可以对称地选择左子树最大节点作为中序前驱。

二叉搜索树删除三种情况

完整可运行示例

递归函数必须返回修改后的子树根,父节点再把返回值接回 left 或 right。这样删除根节点、叶子节点和内部节点都能使用同一套逻辑。

python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

def find_min(node):
    while node.left is not None:
        node = node.left
    return node

def delete(root, value):
    if root is None:
        return None

    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        # 零个或一个子节点时,直接让现有子树接替
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        # 双子节点使用右子树最小值作为中序后继
        successor = find_min(root.right)
        root.value = successor.value
        root.right = delete(root.right, successor.value)

    return root

def inorder(root):
    if root is None:
        return []
    return inorder(root.left) + [root.value] + inorder(root.right)

root = None
for value in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, value)

for value in [1, 14, 3, 8]:
    root = delete(root, value)
    print(f"删除 {value} 后:", inorder(root))

预期输出:

text
删除 1 后: [3, 4, 6, 7, 8, 10, 13, 14]
删除 14 后: [3, 4, 6, 7, 8, 10, 13]
删除 3 后: [4, 6, 7, 8, 10, 13]
删除 8 后: [4, 6, 7, 10, 13]

正确性与复杂度

查找目标、寻找后继和删除后继都沿树高方向进行,因此总时间复杂度为 O(h)O(h)。递归实现额外占用 O(h)O(h) 栈空间;平衡树中 hh 接近 log⁡n\log n,退化树中可达到 nn。

复制节点值适合只保存简单键值的教学模型。若节点还包含对象身份、父指针或多个业务字段,直接复制可能破坏引用语义,此时应使用完整节点移植方案,而不是只替换一个字段。

常见错误是单子节点时返回空、复制后继后忘记删除原节点,或没有把递归返回值重新赋给父节点引用。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉搜索树的删除

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通