算法刷题系列（五十九）：二叉搜索树——查找、插入与删除

算法刷题系列（五十九）：二叉搜索树——查找、插入与删除

目录里的早期“二叉排序树”笔记只留下了定义和一张插图。本篇把定义扩展成完整操作：在二叉搜索树（BST）中，左子树的键小于根，右子树的键大于根，并且左右子树本身也满足这一性质。

这条顺序性质让查找可以像二分一样沿一条根到叶路径前进；但普通 BST 不保证平衡，输入顺序可能让它退化成链表。

一、查找为什么只走一边？

要查找键 x，在当前节点比较：

• x 小于当前键，只可能在左子树；
• x 大于当前键，只可能在右子树；
• 相等则命中。

每次比较都丢弃另一棵子树。运行时间与树高 h 成正比：平均平衡时约 O(log n)；极端偏斜时为 O(n)。

二、插入与重复键策略

从根开始按查找规则走，遇到空孩子时插入新节点。下面的实现约定不保存重复键；若业务需要重复键，可让节点保存计数或将相等键统一放在一侧，但查询、删除和旋转都必须遵循同一规则。

三、删除分三种情况

删除目标节点时：

1. 叶子节点：让父节点链接置空。
2. 只有一个孩子：用唯一孩子替代该节点。
3. 有两个孩子：用右子树最小节点（中序后继）替换键值，再删除后继原位置。

第三种情况保持了左边都小于替代键、右边都大于替代键的顺序关系。

四、Java 实现

public class BinarySearchTree {
    private static final class Node {
        int key;
        Node left;
        Node right;

        Node(int key) {
            this.key = key;
        }
    }

    private Node root;

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

    public void insert(int key) {
        root = insert(root, key);
    }

    private Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key);
        }
        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        }
        return node;
    }

    public void delete(int key) {
        root = delete(root, key);
    }

    private Node delete(Node node, int key) {
        if (node == null) {
            return null;
        }
        if (key < node.key) {
            node.left = delete(node.left, key);
        } else if (key > node.key) {
            node.right = delete(node.right, key);
        } else if (node.left == null) {
            return node.right;
        } else if (node.right == null) {
            return node.left;
        } else {
            Node successor = node.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            node.key = successor.key;
            node.right = delete(node.right, successor.key);
        }
        return node;
    }
}

五、Python 实现

from __future__ import annotations

class Node:
    def __init__(self, key: int) -> None:
        self.key = key
        self.left: Node | None = None
        self.right: Node | None = None

class BinarySearchTree:
    def __init__(self) -> None:
        self.root: Node | None = None

    def contains(self, key: int) -> bool:
        current = self.root
        while current is not None:
            if key == current.key:
                return True
            current = current.left if key < current.key else current.right
        return False

    def insert(self, key: int) -> None:
        self.root = self._insert(self.root, key)

    def _insert(self, node: Node | None, key: int) -> Node:
        if node is None:
            return Node(key)
        if key < node.key:
            node.left = self._insert(node.left, key)
        elif key > node.key:
            node.right = self._insert(node.right, key)
        return node

    def delete(self, key: int) -> None:
        self.root = self._delete(self.root, key)

    def _delete(self, node: Node | None, key: int) -> Node | None:
        if node is None:
            return None
        if key < node.key:
            node.left = self._delete(node.left, key)
        elif key > node.key:
            node.right = self._delete(node.right, key)
        elif node.left is None:
            return node.right
        elif node.right is None:
            return node.left
        else:
            successor = node.right
            while successor.left is not None:
                successor = successor.left
            node.key = successor.key
            node.right = self._delete(node.right, successor.key)
        return node

tree = BinarySearchTree()
for value in (8, 3, 10, 1, 6, 14, 4, 7, 13):
    tree.insert(value)
assert tree.contains(6) and not tree.contains(2)
tree.delete(3)
assert not tree.contains(3) and tree.contains(4) and tree.contains(6)

低于 Python 3.10 的解释器可在代码顶部添加 from __future__ import annotations。

六、中序遍历与有序输出

BST 的中序遍历顺序是“左子树、当前节点、右子树”，因此输出键按升序排列。反过来，若树的中序结果不是非递减序列，输入就不满足 BST 的定义。

验证 BST 时，不能只比较节点与直接孩子；必须检查整棵左子树都小于祖先、整棵右子树都大于祖先。可递归传递每个子树允许的上下界。

七、边界与复杂度

• 空树查找失败、插入后成为根节点。
• 删除不存在的键不改变树。
• 删除根节点要把新的子树根返回给调用者。
• 若按升序依次插入，普通 BST 会变成高度为 n 的链，操作退化为 O(n)。
• 递归操作调用栈为 O(h)；偏斜树可能导致递归深度过大。

因此，BST 的顺序性质并不等于它自动平衡。下一篇对比 AVL、B 树和 B+ 树如何控制高度，及它们为何适用于不同的内存层次。

小结

BST 用一条比较规则把查找范围缩到一个孩子；插入沿同一路径寻找空位，删除则需处理零、一、两个孩子三类结构。操作复杂度由树高决定，想获得稳定的对数级操作还需要平衡机制。