高级数据结构：Trie、并查集与跳表

这一课你将能做到

1. 手写 Trie（前缀树）实现前缀匹配和自动补全
2. 手写并查集实现连通性判断与合并
3. 理解跳表的设计思想及其在有序集合中的应用

为什么要学

高级数据结构是特定场景的「重型武器」。Trie 让前缀搜索快到 O(1)，并查集让连通判断快到 O(α(n))，跳表让有序集合的增删查快到 O(log n)。不会它们，遇到字符串前缀、连通区域、排行榜等问题就只能暴力。

人话：Trie 是「字典的目录」——按字母一层一层展开；并查集是「朋友圈合并」——问你和我是不是一伙的；跳表是「多层楼梯」——每层跳一半，加速查找。

先建立图像

Trie (前缀树):
        root
       / | \
      a  b  c
      |  |  |
      p  a  a
      |  |  |
      p  l  t
         |
         l
         表示 "app", "ball", "cat"

并查集:   {1,2,3} {4,5} {6}
         合并(3,4) → {1,2,3,4,5} {6}
         查询(1,5)? true

跳表:    level 3:  1 ──────────→ 10
        level 2:  1 ────→ 5 ──→ 10
        level 1:  1 → 3 → 5 → 7 → 10

跟着做

步骤 1：Trie（前缀树）

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd = false;
}

public class Main {
    TrieNode root = new TrieNode();
    
    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
    
    // 查找完整单词
    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEnd;
    }
    
    // 查找前缀
    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }
    
    private TrieNode findNode(String s) {
        TrieNode node = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
    
    public static void main(String[] args) {
        Main trie = new Main();
        trie.insert("apple");
        trie.insert("app");
        System.out.println(trie.search("app"));     // true
        System.out.println(trie.startsWith("app")); // true
        System.out.println(trie.search("appl"));    // false
    }
}

插入和查找都是 O(m)，m 是单词长度。

步骤 2：并查集（路径压缩 + 按秩合并）

public class Main {
    int[] parent;
    int[] rank;
    
    public Main(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    // 查找根节点（路径压缩）
    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    // 合并两个集合
    public void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
    }
    
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    
    public static void main(String[] args) {
        Main dsu = new Main(6);
        dsu.union(0, 1);
        dsu.union(1, 2);
        dsu.union(3, 4);
        System.out.println(dsu.connected(0, 2)); // true
        System.out.println(dsu.connected(0, 3)); // false
    }
}

单次操作近似 O(1)（阿克曼函数反函数 α(n)，<5）。

步骤 3：并查集判环

public class Main {
    public boolean hasCycle(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        
        for (int[] e : edges) {
            int px = find(parent, e[0]);
            int py = find(parent, e[1]);
            if (px == py) return true; // 已经连通，加这条边成环
            parent[px] = py;
        }
        return false;
    }
    
    int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
    
    public static void main(String[] args) {
        int[][] edges = {{0,1},{1,2},{2,0}};
        System.out.println(new Main().hasCycle(3, edges)); // true
    }
}

步骤 4：跳表简介（Java TreeMap 底层思想）

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        // Java 的 TreeMap 基于红黑树，等价的跳表实现概念类似
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(3, "C");
        map.put(1, "A");
        map.put(5, "E");
        map.put(2, "B");
        map.put(4, "D");
        
        // 有序遍历
        map.forEach((k, v) -> System.out.print(v + " ")); // A B C D E
        
        // 范围查询
        System.out.println(map.subMap(2, true, 4, true)); // {2=B, 3=C, 4=D}
        
        // 首尾
        System.out.println(map.firstKey()); // 1
        System.out.println(map.lastKey());  // 5
    }
}

跳表用多层链表+随机层高实现 O(log n) 增删查，比红黑树实现简单，适合并发场景（如 Redis）。

讲清楚要点

1. Trie 的空间优化：如果字符集大，用 HashMap<Character, TrieNode> 替代固定长度数组。
2. 并查集的压缩：路径压缩让树变扁，按秩合并让树不高。两者结合后单次操作几乎 O(1)。
3. 跳表 vs 红黑树：跳表实现简单，支持无锁并发（CAS）；红黑树严格平衡，Java 标准库用红黑树。
4. 判题场景：Trie 用于单词前缀匹配、敏感词过滤；并查集用于连通分量、最小生成树（Kruskal）；有序集合用 TreeMap/TreeSet。

你可能会懵的地方

• Trie 每个节点只能存 26 个字母吗？ 可以存任意字符。小写字母用 26 长度数组；完整字符用 HashMap<Character, TrieNode>；二进制用 2 长度数组。

• 并查集怎么求连通分量数量？ 初始为 n，每次成功合并减 1。或者遍历所有节点，统计 find(i) == i 的个数。

• 路径压缩后秩还准吗？ 不太准，但没关系。秩只决定谁当爹，压缩后树很扁，按秩合并的优势已经发挥。

• 跳表随机层高怎么实现？ 每层以 1/2 概率晋升。Redis 的层高最大 64。Java 没有标准跳表实现，用 ConcurrentSkipListMap。

• 并查集和 DFS 连通性怎么选？ 动态加边用并查集；一次性求连通块用 DFS/BFS。并查集支持撤销用按大小合并+栈。

错法对照

错法	问题	正解
Trie 忘记标记 isEnd	前缀和完整单词无法区分	到达单词末尾时设置 isEnd=true
并查集不加路径压缩	退化成链表，O(n) 查询	parent[x] = find(parent[x])
并查集合并不判断根相同	重复合并浪费	先 if (px == py) return;
TreeMap 用可变对象作 Key	排序错误	Key 不可变，或修改后重新 put
跳表层高固定	失去概率平衡优势	随机决定，上层概率递减

卡点急救

1. Trie 内存爆炸：节点太多。用哈希表代替数组，或改用双数组 Trie（AC 自动机）。
2. 并查集递归栈溢出：节点数 >10^5 时，递归 find 可能溢出。改迭代：

   int find(int x) {
       while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
       return x;
   }
   

3. TreeMap 范围查询结果为空：检查是否包含边界，用 subMap(from, inclusive, to, inclusive)。

面试常问

• Trie 和哈希表怎么选？ 精确查找用哈希表 O(1)；前缀匹配、自动补全用 Trie O(m)。Trie 还能做字典序遍历。

• 并查集的时间复杂度为什么是 O(α(n))？ α 是阿克曼函数反函数，增长极慢。路径压缩把树压扁，按秩合并限制高度，两者结合后任意操作序列的总时间近似线性。

• Redis 为什么用跳表不用红黑树？ 跳表实现简单、支持无锁并发、区间查询方便（按排名取范围）。红黑树严格平衡，但实现复杂，并发需要锁。

自测三问

1. Trie 的插入和查找时间复杂度分别是多少？
2. 并查集的路径压缩和按秩合并分别解决什么问题？
3. 跳表和红黑树在有序集合中的时间复杂度对比？

小结一句话

Trie 加速字符串前缀搜索，并查集高效处理连通性问题，跳表/红黑树维护动态有序集合；高级数据结构是解决特定难题的利器。

延伸

• Java 官方文档：TreeMap
• 下一课：常用算法技巧——双指针、滑动窗口与动态规划入门。