数据结构与算法 / 系统课时
二叉搜索树的删除
二叉搜索树的删除
删除操作既要移除目标节点,又要保持二叉搜索树的有序约束。本课把删除分为叶子、单子节点和双子节点三类,并用中序后继完成可运行实现与结果验证。
学习目标
- 能区分三类删除情况并正确连接剩余子树
- 理解中序后继和中序前驱在双子节点删除中的作用
- 能分析删除操作的复杂度与结构边界
三种删除情况
找到目标节点后,处理方式取决于它拥有的子节点数量。叶子节点可以直接删除;只有一个子节点时,由该子节点接替目标位置;左右子节点都存在时,需要选择一个不会破坏有序性的替代值。
常用方案是取右子树中的最小节点作为中序后继。先把后继值复制到目标节点,再从右子树删除原后继节点。也可以对称地选择左子树最大节点作为中序前驱。

完整可运行示例
递归函数必须返回修改后的子树根,父节点再把返回值接回 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]正确性与复杂度
查找目标、寻找后继和删除后继都沿树高方向进行,因此总时间复杂度为 。递归实现额外占用 栈空间;平衡树中 接近 ,退化树中可达到 。
复制节点值适合只保存简单键值的教学模型。若节点还包含对象身份、父指针或多个业务字段,直接复制可能破坏引用语义,此时应使用完整节点移植方案,而不是只替换一个字段。
常见错误是单子节点时返回空、复制后继后忘记删除原节点,或没有把递归返回值重新赋给父节点引用。
按自己的节奏,确认真正理解。