Trie

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

資訊

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

想像一本實體字典，你想查「apple」和「app」。你不會把這兩個字當作獨立不相關的字。你會先翻到字母 a 的那一頁，接著在 a 下面找到 p（變成 ap），再在下面找到 p（變成 app）。

Trie 的圖形視覺化

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

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

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

實作

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

// JavaScript

class Trie {
  constructor() {
    this.root = {};
  }

  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (node[char] == null) node[char] = {};
      node = node[char];
    }
    node.isEnd = true;
  }

  traverse(word) {
    let node = this.root;
    for (let char of word) {
      if (node[char] == null) return null;
      node = node[char];
    }
    return node;
  }

  search(word) {
    const node = this.traverse(word);
    return !!node && node.isEnd;
  }

  startsWith(prefix) {
    return !!this.traverse(prefix);
  }
}

# Python

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 自動機）：在遊戲聊天室或社群平台中，瞬間抓出一段長文字裡有沒有包含幾萬個違禁詞。

Trie 的圖形視覺化​

實作​

複雜度​

適用情況​

Trie 的圖形視覺化

實作

複雜度

適用情況