Binary Search Tree CRUD

二叉搜索树满足：左子树键值小于当前节点，右子树键值大于当前节点。若允许重复键，必须统一规定重复值落在哪一侧或在节点内维护计数。

Search

从根开始比较目标键：相等即返回，更小进入左子树，更大进入右子树。时间复杂度为 $O(h)$，其中 $h$ 是树高。

Insert

沿搜索路径找到空位置并挂接新节点。插入后仍需满足 BST 不变量；平衡树还要执行旋转或重新着色。

TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);
    if (key < root.val) root.left = insert(root.left, key);
    else if (key > root.val) root.right = insert(root.right, key);
    return root;
}

Delete

删除分三种情况：

1. 叶子节点：直接移除；
2. 只有一个子节点：用该子节点替换当前节点；
3. 有两个子节点：用右子树最小节点（后继）或左子树最大节点（前驱）替换，再删除被移动的节点。

TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = delete(root.left, key);
    else if (key > root.val) root.right = delete(root.right, key);
    else {
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        TreeNode next = root.right;
        while (next.left != null) next = next.left;
        root.val = next.val;
        root.right = delete(root.right, next.val);
    }
    return root;
}

普通 BST 在有序输入下可能退化为链表，操作变为 $O(n)$；需要稳定 $O(\log n)$ 时使用 AVL、红黑树或 Treap。