第 27 章 中等 約 12 分鐘
Trie 字典樹：搜尋引擎的自動完成
你在 Google 打「演算」就跳出「演算法」「演算法導論」——背後就是 Trie。樹狀儲存字串的字首索引。
建議先看過： 12-graph-basics
你打一半搜尋引擎就猜到了
Google 自動完成、輸入法選字、密碼字典—— 都需要「給我字首，列出所有可能的完整字」。
雜湊表能查「完整字串」是不是存在，但沒辦法做字首搜尋。
Trie（字典樹，發音同 “try”）就是為了字首查詢設計的。
看一棵 Trie
存了 cat, car, cap, dog, dot：
每條路徑代表一個字串。
- 走訪節點 = 字串的一個字元
- 每個節點記「我是不是某個字的結尾」
三個操作
Insert(“cat”)
從 root 開始，逐字走。沒有路就新建節點。最後一格標 isEnd = true。
Search(“car”)
從 root 開始逐字走。
- 走到底且最後一格
isEnd = true→ 找到 ✓ - 路斷了或
isEnd = false→ 沒找到 ✗
StartsWith(“ca”)（字首查詢）
從 root 開始逐字走。走得通就有匹配的字（不在乎是不是結尾）。
要列出所有匹配 → 從那個節點往下 DFS 收集所有 isEnd 節點。
Pseudocode
class TrieNode:
children ← {} // dict: char → TrieNode
isEnd ← false
Algorithm Insert(root, word):
node ← root
for ch in word:
if ch not in node.children:
node.children[ch] ← TrieNode()
node ← node.children[ch]
node.isEnd ← true
複雜度
| 操作 | 時間 | 注意 |
|---|---|---|
| Insert / Search / StartsWith | O(L) | L = 字串長度 |
| 列出某字首的所有字 | O(L + 答案總長度) | DFS |
| 空間 | O(N × L × Σ) | N=字數, L=平均長度, Σ=字母表大小 |
跟雜湊表比：
- 雜湊表：O(L) 查完整字，沒有字首功能
- Trie：O(L) 查完整字 + 支援字首，但佔記憶體
Trie vs Hash
| Trie | Hash | |
|---|---|---|
| 查完整字 | O(L) | O(L)（算 hash） |
| 查字首 | O(L) ✓ | ❌ |
| 列字首所有匹配 | O(L + ans) | O(N) 走全部 |
| 字母順序輸出 | 天生有序 | 需要排序 |
| 記憶體 | 較大 | 較小 |
💡實務應用
- Google / Yahoo / 注音輸入法自動完成
- 路由表（Trie 的變形 Radix Tree，IP 地址查詢）
- 拼字檢查器
- DNA 序列匹配
C++ 雖然沒內建 Trie，但 std::map<string, V> 底層是紅黑樹，字首查詢可以用 lower_bound——不過真要極致效能還是手刻 Trie。
📝考試會這樣考
題型一：給字串列表，畫 Trie。
例：插入 apple, app, apply, banana，畫出 Trie 結構。
訣竅：標清楚哪些節點是 isEnd（用實心圓或 ✓）。
題型二：查詢 / 字首查詢的差別。
- Search：要求 isEnd = true
- StartsWith：只要走得通即可
題型三：Trie 的空間複雜度為什麼這樣？ 答：最壞情況每個字元都是新節點 → N×L 節點，每節點需要 Σ 個子指標。 實務常用 hash map 取代陣列子節點，省空間。
題型四：Trie vs Hash 取捨。 答：要字首功能就用 Trie；只要查完整字串就用 Hash。
這章記住
- Trie = 字首樹，每條路徑是一個字串。
- Insert / Search / StartsWith 都 O(L)——和字串庫大小無關！
- 特長：字首查詢和列出所有匹配——這是 Hash 做不到的。
- 缺點：佔記憶體——每個節點都要存子指標。
- 應用：autocomplete、輸入法、IP 路由、拼字檢查。
學習進度只存在你的瀏覽器，不會上傳。