字典樹（Trie，前綴樹）教學：原理、程式碼與時間複雜度

字典樹解決什麼問題

雜湊集合能快速回答「這個單字是否被儲存？」，但如果不逐一檢查每個單字，就無法回答「哪些已儲存的單字以 pre 開頭？」。排序串列可以用二分搜尋回答前綴查詢，但插入很慢。字典樹是依前綴組織的，所以前綴相關的問題正是它的強項：搜尋框的自動完成、文字遊戲、拼字檢查，以及網路路由的最長前綴匹配。

用白話理解

想像手機通訊錄，你一次輸入一個字母來縮小範圍。輸入 c 會顯示所有 c 開頭的人，輸入 ca 再縮小範圍，依此類推。字典樹儲存單字的形狀正是如此。根節點代表空前綴。每個節點都有一個從下一個字元對應到子節點的映射，外加一個單字結尾旗標，因為像 car 這樣的單字，既可以是完整的單字，也可以是 cart 的前綴。

實例演練：插入 car、cart、cat 與 dog

這四個單字共有 13 個字母，但根節點底下只需要 8 個節點（c, a, r, t, t, d, o, g），因為 car、cart 和 cat 共用了 ca。搜尋 ca 會走過兩個節點，作為前綴是成功的，但 ca 不是單字，因為它的節點沒有被標記為結尾。搜尋 cow 會在第二步失敗：節點 c 沒有子節點 o。

Python 實作

每個節點保存一個子節點的 dict，能處理包括 Unicode 在內的任何字母表。starts_with 方法會收集某個前綴底下的所有單字，這是自動完成的核心。

class TrieNode:
    __slots__ = ("children", "is_word")
    def __init__(self):
        self.children = {}
        self.is_word = False
class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True
    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node
    def contains(self, word):
        node = self._find(word)
        return node is not None and node.is_word
    def starts_with(self, prefix):
        node, out = self._find(prefix), []
        stack = [(node, prefix)] if node else []
        while stack:
            node, path = stack.pop()
            if node.is_word:
                out.append(path)
            for ch, child in node.children.items():
                stack.append((child, path + ch))
        return sorted(out)

t = Trie()
for w in ["car", "cart", "cat", "dog"]:
    t.insert(w)
print(t.contains("car"), t.contains("ca"))  # True False
print(t.starts_with("ca"))                  # ['car', 'cart', 'cat']
print(t.starts_with("x"))                   # []

starts_with 會將輸出排序，以得到穩定的順序。真正的自動完成還會在前幾筆結果之後就停止並加以排名，例如依儲存的熱門程度計數排序。

時間與空間複雜度

時間與單字數量 n 無關，這是它相對於字串平衡樹（O(m log n) 次比較）的主要優勢。代價是記憶體：每個節點都是帶有自己字典的獨立物件，所以字典樹的記憶體用量可能是原始字串的許多倍。

變體與常見錯誤

• 陣列式子節點：針對小寫英文字母使用固定的 26 格陣列。比 dict 快，但對稀疏或大型字母表很浪費。
• 壓縮字典樹（基數樹 radix tree、Patricia trie）：把單一子節點的連續鏈合併成一條以字串標示的邊，能省下大量記憶體。基數樹被用在 IP 路由表和某些 HTTP 路由器中。
• 三元搜尋樹（ternary search tree）：每個節點有三個子節點（小於、等於、大於），比寬陣列更省記憶體。
• 計數字典樹：在每個節點存放計數器，就能在 O(m) 內回答「有多少單字以這個前綴開頭？」。
• 位元字典樹：逐位元儲存數字，用來解決最大 XOR 的問題。

何時使用字典樹，以及常見的面試題

當你需要前綴查詢、最長前綴匹配，或要對許多帶有共用前綴的字串做有序迭代時，請使用字典樹。如果只需要精確比對的查找，請用 set 或 dict：在 Python 中它更簡單，也更省記憶體。對於小型、不變動的單字清單，搭配 bisect 模組的排序串列也能很好地回答前綴查詢。

常見題目：實作字典樹（插入、搜尋、starts-with）、在網格中搜尋多個目標單字、把單字替換成它最短的字根、最長共同前綴、設計搜尋自動完成系統，以及用位元字典樹求兩數的最大 XOR。