跳至主要内容

Trie

Trie（讀音同 「Try」），又被稱為字典樹（Dictionary Tree）或前綴樹（Prefix Tree），是一種專門用來處理字串檢索的進階樹狀資料結構。

資訊

它的核心思想是：利用字串的「共同前綴」來減少重複儲存，進而達到極致的查詢速度。

白話理解

想像一本實體字典，你想查 「apple」 和 「app」。你不會把這兩個字當作獨立不相關的字。你會先翻到字母 a 的那一頁，接著在 a 下面找到 p（變成 ap），再在下面找到 p（變成 app）。「app」和「apple」共用了同一段路徑，只有走到最後才分岔，這正是 Trie 節省空間、加快查詢的關鍵。

Trie 的圖形視覺化​

假設把 ["app", "apple", "beer", "add"] 這四個單字存進 Trie 裡，在邏輯上它會長成這樣：

                  ( Root 空節點 )
                 /               \
               [a]               [b]
              /   \               |
            [p]   [d]            [e]
            /       \             |
         *[p]*      [d]*         [e]
          /                       |
        [l]                      [r]*
        /
      [e]*

有打 * 的節點，代表「這裡可以組合出一個完整的單字」。

實作​

這邊實作都用物件導向的方式建立，但實際上解題時可以直接從一個 hash map 開始。

class Trie:

    def __init__(self):
        self.root = {}

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node['is_end'] = True

    def traverse(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return None
            node = node[char]
        return node

    def search(self, word: str) -> bool:
        node = self.traverse(word)
        return bool(node) and "is_end" in node

    def starts_with(self, prefix: str) -> bool:
        return bool(self.traverse(prefix))

複雜度​

如果要在一堆資料中找單字，普通方法是遍歷 Array。如果是用 Hash Table，雖然查詢是 O(1)，但當字串很長時，計算 Hash 值本身也需要時間。

Trie 的時間複雜度則非常快速：

操作時間複雜度說明
Insert (新增單字)O(M)M 為單字的長度。字有多長，就往下走幾層。
Search (完整搜尋)O(M)只跟「你要找的字有多長」有關，與資料庫裡有幾百萬個字完全無關！
StartsWith (前綴搜尋)O(M)檢查有沒有以特定前綴開頭的字（例如打 ap 找 apple）。

適用情況​

  • 輸入法自動完成 / 搜尋框建議（Auto-Complete / Suggestion）：在 Google 輸入 sw，搜尋框立刻跳出 switch、swift。這就是用 Trie 的 startsWith 特性，瞬間拉出所有共同前綴的字。
  • 拼字檢查（Spell Checker）：Word 或編輯器中，文字底下出現的紅色錯字虛線，可以透過 Trie 快速比對該單字是否存在於字典中。
  • IP 路由選擇（最長前綴匹配 Longest Prefix Matching）：在網路路由器中，用來決定數據包該往哪裡送。
  • 文字審查 / 敏感詞過濾（Trie 的進階變形：AC 自動機）：在遊戲聊天室或社群平台中，瞬間抓出一段長文字裡有沒有包含幾萬個違禁詞。

常見誤區​

  • 搞混「前綴存在」和「完整單字存在」：走到某個節點代表這個前綴有出現過，但不代表它本身是一個完整的單字。例如存入 apple 後，app 這個節點也會存在，但如果沒有額外標記，程式沒辦法區分 app 到底是不是一個獨立被存入的單字，這也是為什麼實作中一定要有 isEnd（或 is_end）這個標記。
  • 忘記處理大小寫或特殊字元：如果題目要求不分大小寫，記得在 insert 前先統一轉成小寫，否則 Apple 和 apple 會被當成兩條完全不同的路徑存進 Trie。
  • 誤以為 Trie 一定比 Hash Table 省空間：如果單字之間沒什麼共同前綴（例如隨機英文字串），Trie 反而會建立大量分支互不共用，佔用的空間可能比 Hash Table 還多，Trie 真正的優勢在於「有大量共同前綴」或「需要前綴搜尋」的情境。
最後於 更新