高级数据结构：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
    }
}