二叉搜索树：查询、插入、删除与退化

重新整理“二叉搜索树：查询、插入、删除与退化”时，我先翻了自己以前的错误记录，其中最典型的一条就是：二叉搜索树的查询很直观，但我按有序数据连续插入后才看到，一棵看似正确的树可以悄悄退化成链表。沿着这个问题再看原理和代码，比直接背结论清楚得多。

二叉搜索树（BST）的核心规则是：对任意节点，左子树的键更小，右子树的键更大。中序遍历因此能得到有序序列。

它从哪里来

有序表上的二分查找很早就存在，但动态数据还需要支持插入和删除。二叉搜索树把二分决策从连续数组搬到链接节点上：左边更小、右边更大。它简单而强大，也暴露出按顺序插入时退化成链表的问题，直接推动了平衡树的发展。

查询与插入

图：插入顺序会改变树高，并决定操作接近 O(log n) 还是 O(n)

public final class BinarySearchTree {
    private static final class Node {
        int value;
        Node left;
        Node right;
        Node(int value) { this.value = value; }
    }

    private Node root;

    public boolean contains(int value) {
        Node node = root;
        while (node != null) {
            if (value == node.value) return true;
            node = value < node.value ? node.left : node.right;
        }
        return false;
    }

    public void add(int value) {
        if (root == null) { root = new Node(value); return; }
        Node node = root;
        while (true) {
            if (value == node.value) return;
            if (value < node.value) {
                if (node.left == null) { node.left = new Node(value); return; }
                node = node.left;
            } else {
                if (node.right == null) { node.right = new Node(value); return; }
                node = node.right;
            }
        }
    }
}

时间复杂度取决于树高 h，查询、插入和删除都是 O(h)。平衡时 h ≈ log n，退化时 h = n。

删除的三种情况

叶子节点：直接断开。
只有一个孩子：让父节点直接连接这个孩子。
有两个孩子：用右子树最小节点（后继）或左子树最大节点（前驱）替换，再删除那个替代节点。

第三种情况最容易出错，因为必须同时保持有序关系、根节点引用和父子连接。测试要覆盖删除根、删除不存在的值、后继正好是右孩子、后继还有右孩子等边界。

递归删除可以直接把“修复后的子树根”返回给父调用：

private Node remove(Node node, int value) {
    if (node == null) return null;
    if (value < node.value) node.left = remove(node.left, value);
    else if (value > node.value) node.right = remove(node.right, value);
    else {
        if (node.left == null) return node.right;
        if (node.right == null) return node.left;
        Node successor = min(node.right);
        node.value = successor.value;
        node.right = remove(node.right, successor.value);
    }
    return node;
}

private Node min(Node node) {
    while (node.left != null) node = node.left;
    return node;
}

若键和值分离，应复制后继的完整键值映射，而不只是键；若节点键不可变，则可以通过节点重连代替覆盖字段。

遍历、范围查询与有序能力

中序遍历能按升序输出全部键。范围查询 [low, high] 可以利用有序性剪枝：当前值小于下界时不用访问左子树，大于上界时不用访问右子树。

private void range(Node node, int low, int high, java.util.List<Integer> out) {
    if (node == null) return;
    if (node.value > low) range(node.left, low, high, out);
    if (node.value >= low && node.value <= high) out.add(node.value);
    if (node.value < high) range(node.right, low, high, out);
}

若节点再维护子树大小，还可以支持第 k 小元素和 rank 查询。这说明数据结构可以通过缓存聚合信息扩展能力，但每次旋转、插入和删除都必须同步维护这些字段。

如何验证一棵 BST

只比较节点与直接孩子不够，左子树的所有值都必须小于当前节点。正确验证应传递允许区间：

private boolean valid(Node node, long minExclusive, long maxExclusive) {
    if (node == null) return true;
    if (node.value <= minExclusive || node.value >= maxExclusive) return false;
    return valid(node.left, minExclusive, node.value)
        && valid(node.right, node.value, maxExclusive);
}

使用 long 边界避免节点值恰好为 Integer.MIN_VALUE 或 Integer.MAX_VALUE 时溢出。

退化不是小概率细节

依次插入 1,2,3,4,5 会得到只有右孩子的链。若输入本身有序，普通 BST 的性能会稳定退化到 O(n)。生产代码不能只用“随机输入通常平衡”来保证性能。

解决方向包括：

使用 AVL、红黑树等自平衡搜索树。
构建静态树时从有序数组中点递归生成。
输入可控且只需查询时，直接使用排序数组和二分查找。
数据位于磁盘页时使用 B 树或 B+ 树等多路结构。

重复键如何处理

BST 规则必须明确重复键策略：忽略、覆盖、计数，还是把多个值放在同一键下。随意规定“相等时总去右边”可能形成重复键长链。Map 语义通常覆盖值，MultiMap 则需要一键多值容器。

构建平衡静态 BST

已有有序数组且之后很少更新时，可以递归选择中点作为根：

private Node build(int[] sorted, int left, int right) {
    if (left > right) return null;
    int middle = left + (right - left) / 2;
    Node node = new Node(sorted[middle]);
    node.left = build(sorted, left, middle - 1);
    node.right = build(sorted, middle + 1, right);
    return node;
}

这能得到高度接近最小的树，但后续连续有序插入仍可能破坏平衡。动态场景需要真正的自平衡策略。

测试清单

空树、单节点和删除根节点。
递增序列验证退化高度。
两孩子删除的各种后继位置。
中序遍历是否严格有序。
随机操作后用区间验证器检查整棵树。
与 TreeSet 的 contains、add、remove 结果对照。

BST 的真正价值

普通 BST 很适合学习有序树和递归，但生产中通常直接使用成熟库。手写它的意义在于理解后续平衡树到底修复了什么：它们没有改变搜索顺序，只是在插入和删除后控制树高。