树结构：二叉搜索树、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
    }
}

始终 O(log n)，但旋转有开销。

步骤 3：堆（优先级队列）

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        // 小顶堆（默认）
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(5); minHeap.offer(2); minHeap.offer(8);
        System.out.println(minHeap.poll()); // 2
        
        // 大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.offer(5); maxHeap.offer(2); maxHeap.offer(8);
        System.out.println(maxHeap.poll()); // 8
    }
}

步骤 4：Top K 问题

import java.util.PriorityQueue;

public class Main {
    public static int[] topK(int[] nums, int k) {
        // 小顶堆，保持堆大小为 k
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) heap.poll(); // 移除最小的
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) res[i] = heap.poll();
        return res;
    }
    
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int[] res = topK(nums, 2);
        for (int x : res) System.out.print(x + " "); // 5 6
    }
}

时间 O(n log k)，空间 O(k)。

步骤 5：排行榜设计

import java.util.TreeMap;

public class Main {
    // 用 TreeMap 实现排行榜（分数 → 用户列表）
    private TreeMap<Integer, String> leaderboard = new TreeMap<>();
    
    public void addScore(int score, String user) {
        leaderboard.put(score, user);
    }
    
    public String getTop() {
        return leaderboard.lastEntry().getValue(); // 最高分
    }
    
    public static void main(String[] args) {
        Main lb = new Main();
        lb.addScore(100, "Alice");
        lb.addScore(85, "Bob");
        lb.addScore(95, "Charlie");
        System.out.println("第一名: " + lb.getTop()); // Alice
    }
}

讲清楚要点

1. BST 的退化：插入有序数据会退化成链表，查询 O(n)。AVL 通过旋转保持平衡，始终 O(log n)。
2. 堆的数组表示：父节点 i，左子 2i+1，右子 2i+2。建堆 O(n)，取顶 O(1)，调整 O(log n)。
3. TreeMap vs PriorityQueue：TreeMap 是红黑树，支持范围查询；PriorityQueue 是堆，只支持取极值。
4. 判题场景：Top K 用堆；有序统计用 TreeMap/TreeSet；需要动态插入删除且保持顺序用 AVL 思想。

你可能会懵的地方

• BST 和堆有什么区别？ BST 是「左 < 根 < 右」，支持有序遍历；堆只保证「父 > 子」或「父 < 子」，不支持有序遍历。堆用数组实现，BST 用指针。

• AVL 和红黑树哪个好？ AVL 更严格平衡，查询更快；红黑树旋转更少，插入删除更快。Java 的 TreeMap 用红黑树，因为插入删除更频繁。

• 堆为什么用数组不用指针？ 完全二叉树的结构用数组更紧凑，没有指针开销，缓存友好。

• PriorityQueue 怎么实现自定义排序？ 传入 Comparator：new PriorityQueue<>((a, b) -> b - a) 是大顶堆；new PriorityQueue<>((a, b) -> a.compareTo(b)) 是小顶堆。

• TreeMap 的底层是什么？ 红黑树。查询、插入、删除都是 O(log n)，支持 firstKey()、lastKey()、subMap() 等范围操作。

错法对照

错法	问题	正解
BST 删除节点直接置 null	破坏树结构	分三种情况：叶子、单子、双子（用后继替换）
AVL 旋转后忘记更新高度	后续平衡判断错误	旋转后重新计算涉及节点的高度
堆调整时遗漏子节点	堆性质破坏	递归或循环检查所有子树
PriorityQueue 存重复元素	无法去重	用 TreeSet 或额外 HashSet 去重
TreeMap 键为 null	抛 NullPointerException	键不能为 null，值可以为 null

卡点急救

1. BST 退化成链表：改用 AVL 或红黑树，或随机打乱插入顺序。
2. 堆排序结果不对：检查建堆是否从 n/2-1 开始，以及 heapify 的递归终止条件。
3. TreeMap 范围查询慢：用 subMap、headMap、tailMap 而不是遍历。

面试常问

• BST 和哈希表怎么选？ 需要范围查询、有序遍历用 BST；只需要精确查找用哈希表。BST 是 O(log n)，哈希表是 O(1)。

• AVL 树的四种旋转？ LL（右旋）、RR（左旋）、LR（先左旋后右旋）、RL（先右旋后左旋）。判断依据：看插入路径和平衡因子。

• 堆为什么建堆是 O(n) 不是 O(n log n)？ 大部分节点高度很小。数学推导：n/2 个叶子高度 0，n/4 个高度 1，总操作次数约 2n。

自测三问

1. BST 中序遍历的结果有什么特点？
2. AVL 树和红黑树的主要区别是什么？
3. 用堆求 Top K 问题的时间和空间复杂度？

小结一句话

BST 提供有序结构，AVL 保证严格平衡，堆实现快速取极值；树结构是处理层级和优先级数据的核心武器。

延伸

• Java 官方文档：TreeMap
• 下一课：图算法——BFS、DFS、拓扑排序与最短路。