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

二叉搜索树删除

二叉搜索树删除

删除比插入更复杂,因为移除节点后仍要保持左小右大的顺序关系。本课将把删除拆成三种结构情况,并通过右子树最小节点作为中序后继,完成双子节点的安全替换。

学习目标

  • 区分叶节点、单子节点和双子节点的删除方式。
  • 实现基于中序后继的完整删除算法。
  • 分析删除操作的边界条件、复杂度与验证方法。

三种删除情况

搜索目标节点仍然沿比较结果向左或向右下降。找到节点后,根据子节点数量处理:

  1. 叶节点没有子树,直接返回 null,让父节点断开链接。
  2. 只有一个子节点,直接返回非空子节点,让它接替被删除节点的位置。
  3. 有两个子节点,先找到右子树中最小的节点作为中序后继,用后继键覆盖目标键,再从右子树中删除原后继节点。

二叉搜索树删除的三种结构情况

中序后继是大于目标键的最小键。它位于目标节点的右子树,并且不可能拥有左子节点,因此复制后继键后,对原后继位置的第二次删除只会落入叶节点或单子节点情况。整个过程仍只访问有限条向下路径,时间复杂度为 O(h)O(h);递归实现的调用栈空间也是 O(h)O(h)。

完整可运行示例

将代码保存为 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:将双子节点策略改为使用左子树最大节点,也就是中序前驱。要求删除结果仍然有序,并说明前驱节点为什么不可能拥有右子节点。

本课总结

  • 删除操作按子节点数量分为三类,叶节点和单子节点本质上都是链接替换。
  • 双子节点可用中序后继覆盖,再递归删除后继原位置,从而维持搜索树性质。
  • 删除时间和递归空间都受树高 hh 控制,最坏情况下为 O(n)O(n)。

下一课预告

完成基本插入与删除后,下一阶段可以继续研究树高失衡带来的性能问题,以及通过旋转和再平衡维持对数级操作成本的方法。

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

目录与阅读设置

阅读设置

17

记录一个想法

二叉搜索树删除

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

登录哪都通