[algorithms] Trie 前綴樹（字典樹）

視覺化概覽

graph TD
    ROOT["root"] --> C["c"]
    ROOT --> D["d"]
    C --> A["a"]
    A --> T["t *"]
    A --> R["r *"]
    R --> RD["d *"]
    D --> O["o"]
    O --> G["g *"]
    style T fill:#9f9,stroke:#333
    style R fill:#9f9,stroke:#333
    style RD fill:#9f9,stroke:#333
    style G fill:#9f9,stroke:#333

什麼是 Trie？

專門處理字串的樹狀結構，共享前綴節省空間。

插入: apple, app, apply, banana

        root
       /    \
      a      b
      |      |
      p      a
      |      |
      p      n
     /|\     |
    l i y    a
    |        |
    e*       n
    |        |
   [end]     a*

* 表示單字結尾

核心概念

• 每個節點代表一個字元
• 從根到節點的路徑 = 前綴
• 從根到標記節點的路徑 = 完整單字
• 共享相同前綴的單字共用節點

節點結構

class TrieNode {
    Map<Character, TrieNode> children;  // 子節點
    boolean isEndOfWord;                 // 是否為單字結尾
}

基本操作

1. 插入 Insert - O(m)

插入 "app":

root → a → p → p*
             ↑
         標記結尾

public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        node.children.putIfAbsent(c, new TrieNode());
        node = node.children.get(c);
    }
    node.isEndOfWord = true;
}

2. 搜尋 Search - O(m)

public boolean search(String word) {
    TrieNode node = findNode(word);
    return node != null && node.isEndOfWord;
}

3. 前綴檢查 StartsWith - O(m)

public boolean startsWith(String prefix) {
    return findNode(prefix) != null;
}

4. 刪除 Delete - O(m)

刪除時需要考慮：

• 該單字是否存在
• 是否有其他單字共用前綴
• 是否有子節點

應用場景

1. 自動補全

輸入 "app"，找出所有以 "app" 開頭的單字:
→ apple, application, apply, app

實作: 找到前綴節點，DFS 遍歷所有子樹

2. 拼字檢查

檢查 "aple" 是否正確:
search("aple") → false

建議修正: 找相似的正確單字

3. IP 路由表

IP 前綴匹配:
192.168.1.* → 路由 A
192.168.*   → 路由 B
192.*       → 路由 C

用 Trie 找最長匹配前綴

4. 詞頻統計

class TrieNode {
    Map<Character, TrieNode> children;
    int count;  // 該單字出現次數
}

時間複雜度

操作	時間複雜度	說明
插入	O(m)	m = 單字長度
搜尋	O(m)	m = 單字長度
前綴檢查	O(m)	m = 前綴長度
刪除	O(m)	m = 單字長度
自動補全	O(m + k)	k = 結果數量

空間複雜度

• 最差：O(字母數 × 總字元數)
• 實際：共享前綴，通常遠小於最差情況

Trie vs HashSet

比較	Trie	HashSet
搜尋單字	O(m)	O(m) 平均
前綴搜尋	O(m) ✓	O(n) 需遍歷
自動補全	O(前綴 + 結果) ✓	不支援
空間	共享前綴	獨立存儲

變體

1. 壓縮 Trie（Radix Tree）

一般 Trie:     壓縮 Trie:
  r               r
  |               |
  o              omane
  |
  m
  |
  a
  |
  n
  |
  e

合併單一子節點，節省空間

2. Ternary Search Tree

每個節點最多三個子節點：小於、等於、大於

3. Double-Array Trie

用兩個陣列實作，更緊湊

經典題目

1. 實作 Trie - LeetCode 208
2. 單字搜尋 II - LeetCode 212
3. 替換單字 - LeetCode 648
4. 最大 XOR - LeetCode 421

相關檔案

• Java 實作：Trie.java