二叉搜索树与平衡树

二叉搜索树是一种特殊的二叉树，它能保持元素的有序性，并提供高效的查找、插入和删除操作。

二叉搜索树 (BST)

性质

1. 若左子树不为空，则左子树上所有节点的值均 小于 根节点的值。
2. 若右子树不为空，则右子树上所有节点的值均 大于 根节点的值。
3. 左右子树也分别为二叉搜索树。

中序遍历：BST 的中序遍历序列是 严格递增 的。

核心操作 (Java 实现)

public class BST {
    private TreeNode root;
    
    // 查找 - 平均 O(log n)，最坏 O(n)
    public TreeNode search(int val) {
        return search(root, val);
    }
    
    private TreeNode search(TreeNode node, int val) {
        if (node == null || node.val == val) return node;
        return val < node.val ? search(node.left, val) : search(node.right, val);
    }
    
    // 插入 - 递归或迭代均可
    public void insert(int val) {
        root = insert(root, val);
    }
    
    private TreeNode insert(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }
    
    // 删除 - 难点：处理有两个子节点的情况
    public void delete(int val) {
        root = delete(root, val);
    }
    
    private TreeNode delete(TreeNode node, int val) {
        if (node == null) return null;
        if (val < node.val) node.left = delete(node.left, val);
        else if (val > node.val) node.right = delete(node.right, val);
        else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;
            // 找到右子树的最小值 (后继节点) 替换
            TreeNode minNode = getMin(node.right);
            node.val = minNode.val;
            node.right = delete(node.right, minNode.val);
        }
        return node;
    }
}

平衡二叉树 (AVL 树)

BST 在极端情况下（如插入有序序列）会退化成链表，性能降为 O(n)。AVL 树通过 自平衡 机制保证高度始终为 O(log n)。

AVL 的平衡因子 (BF)

BF = height(left_subtree) - height(right_subtree)。AVL 树要求任意节点的 $|BF| \le 1$。

四种旋转方式

1. LL (单次右旋)：左子的左边插入。
2. RR (单次左旋)：右子的右边插入。
3. LR (先左后右)：左子的右边插入。
4. RL (先右后左)：右子的左边插入。

练习

1. LeetCode 98：验证二叉搜索树 (中序遍历思想)
2. LeetCode 700：二叉搜索树中的搜索
3. LeetCode 450：删除二叉搜索树中的节点
4. LeetCode 110：平衡二叉树 (AVL 性质判断)
5. 实现 LL 和 RR 旋转代码。
6. 理解 红黑树 (Red-Black Tree)：工业界最常用的平衡 BST（如 Java HashMap 内部使用）。