数据结构与算法 / 系统课时
二叉搜索树删除
二叉搜索树删除
删除比插入更复杂,因为移除节点后仍要保持左小右大的顺序关系。本课将把删除拆成三种结构情况,并通过右子树最小节点作为中序后继,完成双子节点的安全替换。
学习目标
- 区分叶节点、单子节点和双子节点的删除方式。
- 实现基于中序后继的完整删除算法。
- 分析删除操作的边界条件、复杂度与验证方法。
三种删除情况
搜索目标节点仍然沿比较结果向左或向右下降。找到节点后,根据子节点数量处理:
- 叶节点没有子树,直接返回
null,让父节点断开链接。 - 只有一个子节点,直接返回非空子节点,让它接替被删除节点的位置。
- 有两个子节点,先找到右子树中最小的节点作为中序后继,用后继键覆盖目标键,再从右子树中删除原后继节点。

中序后继是大于目标键的最小键。它位于目标节点的右子树,并且不可能拥有左子节点,因此复制后继键后,对原后继位置的第二次删除只会落入叶节点或单子节点情况。整个过程仍只访问有限条向下路径,时间复杂度为 ;递归实现的调用栈空间也是 。
完整可运行示例
将代码保存为 BstDeleteDemo.java。示例依次删除叶节点 1、只有左子节点的 14,以及拥有两个子节点的 3,每一步都用中序遍历验证结果。
java
import java.util.ArrayList;
import java.util.List;
public class BstDeleteDemo {
private static final class Node {
int key;
Node left;
Node right;
Node(int key) {
this.key = key;
}
}
public static void main(String[] args) {
int[] keys = {8, 3, 10, 1, 6, 14, 4, 7, 13};
Node root = null;
for (int key : keys) {
root = insert(root, key);
}
System.out.println("初始中序: " + inOrder(root));
root = delete(root, 1);
System.out.println("删除叶节点 1: " + inOrder(root));
root = delete(root, 14);
System.out.println("删除单子节点 14: " + inOrder(root));
root = delete(root, 3);
System.out.println("删除双子节点 3: " + inOrder(root));
}
private static Node insert(Node root, int key) {
if (root == null) {
return new Node(key);
}
if (key < root.key) {
root.left = insert(root.left, key);
} else if (key > root.key) {
root.right = insert(root.right, key);
}
return root;
}
private static Node delete(Node root, int key) {
if (root == null) {
return null;
}
if (key < root.key) {
root.left = delete(root.left, key);
} else if (key > root.key) {
root.right = delete(root.right, key);
} else {
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
Node successor = findMin(root.right);
root.key = successor.key;
root.right = delete(root.right, successor.key);
}
return root;
}
private static Node findMin(Node node) {
Node current = node;
while (current.left != null) {
current = current.left;
}
return current;
}
private static List<Integer> inOrder(Node root) {
List<Integer> result = new ArrayList<>();
collectInOrder(root, result);
return result;
}
private static void collectInOrder(Node node, List<Integer> result) {
if (node == null) {
return;
}
collectInOrder(node.left, result);
result.add(node.key);
collectInOrder(node.right, result);
}
}编译并运行:
bash
javac BstDeleteDemo.java
java BstDeleteDemo预期输出
text
初始中序: [1, 3, 4, 6, 7, 8, 10, 13, 14]
删除叶节点 1: [3, 4, 6, 7, 8, 10, 13, 14]
删除单子节点 14: [3, 4, 6, 7, 8, 10, 13]
删除双子节点 3: [4, 6, 7, 8, 10, 13]每次输出都保持严格递增,并且只少了指定键。删除 3 时,它先被后继键 4 覆盖,再删除原来的 4 节点,因此最终集合中不会出现重复键。
常见错误与练习
最常见的错误是递归删除后没有把返回值重新赋给 root.left 或 root.right,这样父节点仍保存旧链接。另一个错误是双子节点只复制后继键,却没有继续删除原后继,结果会产生重复键。删除根节点时尤其要使用 root = delete(root, key) 接收可能变化的新根。
练习 1:为空树、单节点树以及不存在的键补充测试,验收条件是程序不抛异常,且不存在的键不会改变中序遍历结果。
练习 2:将双子节点策略改为使用左子树最大节点,也就是中序前驱。要求删除结果仍然有序,并说明前驱节点为什么不可能拥有右子节点。
本课总结
- 删除操作按子节点数量分为三类,叶节点和单子节点本质上都是链接替换。
- 双子节点可用中序后继覆盖,再递归删除后继原位置,从而维持搜索树性质。
- 删除时间和递归空间都受树高 控制,最坏情况下为 。
下一课预告
完成基本插入与删除后,下一阶段可以继续研究树高失衡带来的性能问题,以及通过旋转和再平衡维持对数级操作成本的方法。
按自己的节奏,确认真正理解。