跳轉到

8.1 Trie樹#

概念說明#

Trie（字典樹、前綴樹） 的每條「根到節點的路徑」代表一個字串前綴：根是空字串，往下每一步多吃一個字元。多個單字共用相同前綴的邊，例如 "car"、"cat"、"card" 共用 c-a-r 的路徑。每個節點維護「26（或任意字元集）個子女」與「是否為單字結尾」的標記。

Trie 的殺手級特性：

  1. 查詢成本 = O(單字長度)，與詞庫有幾萬個字完全無關。
  2. 前綴查詢是天然的：走到前綴節點後，收集其子樹即可列出所有以該前綴開頭的單字。
  3. 無雜湊碰撞問題：不是「算一個雜湊值」，而是「逐字元對照」，行為完全可預測。

代價是空間：字元集大、單字又少時，稀疏節點很浪費；實務上常用字典代替定長陣列存子女，或用「雙陣列 Trie」壓縮。

操作步驟#

  1. insert(word)：從根出發，逐字元「缺邊就建新節點」；走完後把末節點標為單字結尾。
  2. search(word)：逐字元往下走；任一步斷頭即 False；走完後檢查「單字結尾」標記（走得到但沒標記，代表只是別的單字的前綴）。
  3. starts_with(prefix)：走完前綴即可回 True，不必檢查結尾標記。
  4. autocomplete(prefix)：走到前綴節點後做 DFS，收集所有標了結尾的路徑。

Python 實作#

class TrieNode:
    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:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def autocomplete(self, prefix):
        node = self._walk(prefix)
        if node is None:
            return []
        results = []
        def dfs(n, path):
            if n.is_word:
                results.append(prefix + path)
            for ch, child in n.children.items():
                dfs(child, path + ch)
        dfs(node, "")
        return results

t = Trie()
words = ["cat", "car", "card", "care", "dog", "do"]
for w in words:
    t.insert(w)

print(t.search("card"))        # True
print(t.search("ca"))          # False（只是前綴，不是完整單字）
print(t.starts_with("ca"))     # True
print(t.autocomplete("car"))   # ['car', 'card', 'care']
print(t.autocomplete("d"))     # ['dog', 'do']

與雜湊表的取捨#

查「單字存在嗎」，雜湊表 O(長度) 平均、夠快且省程式碼。但以下需求只有 Trie 能優雅勝任：

  • 自動補全 / 前綴列舉：雜湊表必須掃全表 O(n)，Trie 是 O(前綴長 + 結果總長)。
  • 按字典序輸出：Trie 子女排序後 DFS 即得；雜湊表無序。
  • 最長前綴匹配：如 IP 路由表，Trie 逐位元下走即得最長匹配。

複雜度分析#

insert / search / starts_with 都是 O(L)（L 為字串長度）。autocomplete 為 O(前綴長 + 輸出總字元數)。空間最壞 O(所有字元總數 × 字元集)，但共用前綴會大幅節省；字元集大時用 dict 存子女，空間與實際出現的邊數成正比。

練習#

  1. 在 Trie 加上 count_words_starting_with(prefix)：統計以指定前綴開頭的單字數。提示：讓每個節點記錄「子樹內單字數」，插入時沿途加一。
  2. 實作「最長公共前綴」：給一組單字建 Trie 後，找出它們共同的最長前綴（不必逐字兩兩比較）。
  3. 用 Trie 實作一個單字的「拼字建議」：查詢 misspelled 字時，列出「編輯距離 ≤ 1」的所有字典單字（提示：DFS 時允許一次替換、插入或刪除）。