Trie字典樹
每層一個字元，共用前綴。
用在：自動補全、拼字檢查、IP 路由表
01為什麼需要它
使用者打了「alg」，要立刻列出所有以 alg 開頭的詞。字典有幾十萬個詞，每次都掃一遍太慢；雜湊表又只能查完整的鍵。
為什麼用它字典樹把共用前綴的詞疊在同一條路徑上。走 3 步到達「alg」，它底下的所有葉就是答案，成本和字典大小無關。
一篇文章的每個字都要查「在不在字典裡」，或掃一段文字看有沒有出現任何一個敏感詞。
為什麼用它查一個長度 L 的字只要 L 步。多個模式一起比對時，把所有模式建成一棵樹，掃文字時一次對照全部，這是 Aho-Corasick 的基礎。
路由表有幾十萬條規則，每個封包要找「最長前綴匹配」的那一條，而且每秒要處理百萬個封包。
為什麼用它把 IP 當成位元字串放進字典樹，沿著封包的位元往下走，走到最深的有效節點就是最長前綴。這是二元字典樹（radix tree）的經典用途。
看到這些關鍵字就想到它：前綴、開頭是、自動補全、多個字串共用前綴、最長前綴匹配、字典。
02核心概念
字典樹（Trie，來自 retrieval）是一棵邊上有字元的樹。從根出發，沿著邊把字元串起來，走到任何一個節點，路徑就是一個前綴。共用前綴的字串共用路徑：car、cat、cart 只需要一條 c-a 的路，之後才分岔。每個節點另外有一個結尾標記，表示「有一個字串剛好在這裡結束」，這樣才能區分「ca 只是前綴」和「car 是一個字」。
插入、查詢、判斷前綴，都是沿著字串的每個字元往下走一步，成本是字串長度 O(L)，和樹裡有多少字串無關。這是它和雜湊表的差別：雜湊表也能 O(L) 查一個完整的字，但它對前綴一無所知；字典樹走到前綴那個節點之後，底下的整棵子樹都是答案。
代價在空間。每個節點要存子節點表：字元集小（26 個小寫字母）就用固定陣列，查一步是 O(1) 但每個節點 26 個指標；字元集大（Unicode）就用雜湊表，省空間但慢一點。實務上還會做壓縮，把只有一個子節點的鏈合併成一段字串，那就是 radix tree，路由表和許多檔案系統用的就是它。
03演算法步驟
- 1節點結構：一個子節點表（
dict或長度 26 的陣列）加一個is_end布林。根對應空字串。 - 2插入：從根開始，對每個字元，沒有對應的子節點就建一個，然後走過去。最後一個節點標
is_end = True。 - 3查單字：沿字元走，任何一步走不下去就是不存在；走完還要檢查
is_end。查前綴：只要走得完就算有。 - 4自動補全：先走到前綴的節點，再對那棵子樹做 DFS，遇到
is_end就收集一個字。 - 5字元集固定且小時用陣列存子節點，查得快；否則用雜湊表。字串非常多時考慮壓縮成 radix tree。
04互動示範
插入 car、cat、cart、dog，看共用的 c-a 路徑怎麼被重複利用。接著查前綴 ca 做自動補全，再分別查 ca 與 cart 是不是完整的字。綠色節點是有結尾標記的。
05程式碼
插入、查單字、查前綴與自動補全。Python 版用 dict 存子節點，C++ 版示範小寫字母用固定陣列的寫法。
class TrieNode:
def __init__(self):
self.children = {} # 字元 -> TrieNode
self.is_end = False # 有沒有單字在這裡結束
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children: # 沒有這條邊就開一條
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _walk(self, s):
"""沿著 s 走到底，走不下去回傳 None"""
node = self.root
for ch in s:
node = node.children.get(ch)
if node is None:
return None
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._walk(prefix) is not None
def autocomplete(self, prefix):
"""列出所有以 prefix 開頭的單字：先走到前綴，再 DFS 收集"""
node = self._walk(prefix)
out = []
def dfs(n, path):
if n.is_end:
out.append(path)
for ch, child in sorted(n.children.items()):
dfs(child, path + ch)
if node:
dfs(node, prefix)
return out
t = Trie()
for w in ["car", "cat", "cart", "dog"]:
t.insert(w)
print(t.search("ca"), t.starts_with("ca")) # False True
print(t.autocomplete("ca")) # ['car', 'cart', 'cat']06練習題
- LeetCode 208Implement Trie (Prefix Tree)Medium
- LeetCode 211Design Add and Search Words（含萬用字元的 DFS）Medium
- LeetCode 1268Search Suggestions System（自動補全）Medium
- LeetCode 212Word Search II（字典樹 + 網格回溯）Hard
- LeetCode 648Replace Words（最短前綴）Medium