树结构：二叉搜索树、AVL 树与堆

这一课你将能做到

1. 手写二叉搜索树的插入、删除、查找
2. 理解 AVL 树的旋转平衡机制
3. 用堆实现 Top K 问题和排行榜

为什么要学

树是层级数据的天然表示。文件系统、数据库索引、缓存淘汰策略，底层都是树。BST 提供有序遍历，AVL 保证平衡，堆实现快速取极值。不会树，就像图书管理员不会用索引。

人话：BST 是「左边小右边大」的二叉树；AVL 是「左右高度差不超过 1」的自平衡 BST；堆是「父节点比子节点大（或小）」的完全二叉树，用数组实现。

先建立图像

BST:        5
           / \
          3   7
         / \ / \
        2  4 6  8
        左 < 根 < 右

AVL 旋转 (右旋):
      5                3
     /                / \
    3      →         2   5
   /                /   /
  2                1   4
 /
1

堆 (大顶堆):    9
              / \
             6   8
            / \ /
           3  2 1
           数组: [9,6,8,3,2,1]

跟着做

步骤 1：二叉搜索树（BST）

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    // 插入
    public static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val < root.val) root.left = insert(root.left, val);
        else if (val > root.val) root.right = insert(root.right, val);
        return root;
    }
    
    // 查找
    public static boolean search(TreeNode root, int val) {
        if (root == null) return false;
        if (val == root.val) return true;
        return val < root.val ? search(root.left, val) : search(root.right, val);
    }
    
    // 中序遍历（有序）
    public static void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    
    public static void main(String[] args) {
        TreeNode root = null;
        int[] vals = {5, 3, 7, 2, 4, 6, 8};
        for (int v : vals) root = insert(root, v);
        inorder(root); // 2 3 4 5 6 7 8
        System.out.println("\n查找 6: " + search(root, 6)); // true
    }
}

平均 O(log n)，最坏 O(n)（退化成链表）。

步骤 2：AVL 树的旋转

class AVLNode {
    int val, height = 1;
    AVLNode left, right;
    AVLNode(int x) { val = x; }
}

public class Main {
    static int height(AVLNode n) { return n == null ? 0 : n.height; }
    static int balance(AVLNode n) { return n == null ? 0 : height(n.left) - height(n.right); }
    
    // 右旋
    static AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        x.right = y;
        y.left = T2;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        return x;
    }
    
    // 左旋
    static AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;
        y.left = x;
        x.right = T2;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        return y;
    }
    
    // 插入（自动平衡）
    static AVLNode insert(AVLNode node, int val) {
        if (node == null) return new AVLNode(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        else return node;
        
        node.height = 1 + Math.max(height(node.left), height(node.right));
        int bal = balance(node);
        
        // LL
        if (bal > 1 && val < node.left.val) return rightRotate(node);
        // RR
        if (bal < -1 && val > node.right.val) return leftRotate(node);
        // LR
        if (bal > 1 && val > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // RL
        if (bal < -1 && val < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }
    
    public static void main(String[] args) {
        AVLNode root = null;
        int[] vals = {10, 20, 30, 40, 50, 25};
        for (int v : vals) root = insert(root, v);
        System.out.println("根节点: " + root.val); // 30
    }
}