你在 Google 搜尋框打了三個字母，瞬間跳出十個建議——背後就是 Trie。
先講結論
Trie 是專門處理字串的樹狀結構，最強的能力是前綴搜尋——給定前綴，O(m) 找到所有匹配的字（m = 前綴長度）。Hash Table 做不到這件事。代價是空間消耗較大，但共享前綴的特性會幫你省回來。
結構：共享前綴的樹
插入 cat、car、card、dog：
root
/ \
c d
| |
a o
/ \ |
t* r* g*
|
d*
* 標記單字結尾。注意 cat 和 car 共享 c-a 前綴——不用存兩份。
每個節點就是一個字元，從 root 走到標記節點的路徑就是一個完整的字。
為什麼不用 HashSet？
搜尋單字的話，HashSet 也是 O(m)，跟 Trie 一樣快。但如果你要找「所有以 ‘app’ 開頭的字」呢？
- HashSet：得遍歷所有字去檢查前綴，O(n)
- Trie：走到 ‘a-p-p’ 節點，DFS 它底下的子樹就好，O(m + 結果數量)
這個差距在字典量級（十萬、百萬字）下非常巨大。
核心操作
插入 O(m)：沿著字串一個字元一個字元走，沒有就建新節點。
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;
}搜尋 O(m)：走到最後一個字元，檢查 isEndOfWord。走到一半發現節點不存在就回傳 false。
前綴檢查 O(m)：跟搜尋一樣，但不用檢查 isEndOfWord——只要走得完就代表這個前綴存在。
應用場景
自動補全：你的 IDE 的 autocomplete、手機鍵盤的選字、Google 的搜尋建議。走到前綴節點，DFS 列出所有可能的完整字。
拼字檢查：快速判斷一個字存不存在字典裡。
IP 路由：路由表的最長前綴匹配（Longest Prefix Match）。192.168.1.* 和 192.168.* 哪個更精確？Trie 可以很自然地處理這個問題。
壓縮 Trie（Radix Tree）
如果路徑上的節點只有一個子節點，把它們合併：
一般 Trie: 壓縮 Trie:
r r
| |
o omane
|
m
|
a
|
n
|
e
省空間，查找速度不變。Linux kernel 的路由表就用 Radix Tree。
Trie 的空間問題
坦白說，Trie 很吃記憶體。每個節點要存一個 Map（或固定大小的 array），如果字元集很大（比如 Unicode），空間爆炸。
所以在資料量不大的場景，HashSet 通常比 Trie 更實用。Trie 的價值在「前綴操作」——如果你不需要前綴搜尋，其實不用特別選它。
Trie 的名字來自 retrieval，但大家都念成 “try”——可能是因為它真的值得你 try 一下。冷到我自己都想刪掉這行。