[algorithms] Trie 前綴樹（字典樹）

cover

你在 Google 搜尋框打了三個字母，瞬間跳出十個建議——背後就是 Trie。

為什麼前綴搜尋要靠它

Trie 是專門處理字串的樹狀結構，最強的能力是前綴搜尋——給定前綴，O(m) 找到所有匹配的字（m = 前綴長度）。Hash Table 做不到這件事。代價是空間消耗較大，但共享前綴的特性會幫你省回來。

結構：共享前綴的樹

插入 cat、car、card、dog：

        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    t*  r*   g*
        |
        d*

* 標記單字結尾。注意 cat 和 car 共享 c-a 前綴——不用存兩份。

每個節點就是一個字元，從 root 走到標記節點的路徑就是一個完整的字。

為什麼不用 HashSet？

搜尋單字的話，HashSet 也是 O(m)，跟 Trie 一樣快。但如果你要找「所有以 ‘app’ 開頭的字」呢？

HashSet：得遍歷所有字去檢查前綴，O(n)
Trie：走到 ‘a-p-p’ 節點，DFS 它底下的子樹就好，O(m + 結果數量)

這個差距在字典量級（十萬、百萬字）下非常巨大。

核心操作

一個節點只裝兩樣東西：往下的分支、還有「我是不是某個字的結尾」這個旗標：

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord;
}

插入 O(m)：沿著字串一個字元一個字元走，沒有就建新節點。

void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        node.children.putIfAbsent(c, new TrieNode());
        node = node.children.get(c);
    }
    node.isEndOfWord = true;
}

搜尋 O(m)：走到最後一個字元，檢查 isEndOfWord。走到一半發現節點不存在就回傳 false。

前綴檢查 O(m)：跟搜尋一樣，但不用檢查 isEndOfWord——只要走得完就代表這個前綴存在。

刪除 O(m)：這個最容易寫錯。不能走到結尾就把整條路徑砍掉，因為別的字可能共用這段前綴。正確做法是先把 isEndOfWord 取消，然後由下往上：只有當某個節點「不是任何字的結尾、也沒有其他子節點」時才真的拔掉它。刪 car 時如果 card 還在，那條 c-a-r 一根都不能動。

🎬 互動視覺化：Trie 前綴樹的插入與查找 — 逐字插入單字，看共享前綴怎麼合流成同一條路徑，再打一個前綴看它從那個節點往下 DFS 撈出所有候選字。

應用場景

自動補全：你的 IDE 的 autocomplete、手機鍵盤的選字、Google 的搜尋建議。走到前綴節點，DFS 列出所有可能的完整字。

拼字檢查：快速判斷一個字存不存在字典裡。

IP 路由：路由表的最長前綴匹配（Longest Prefix Match）。192.168.1.* 和 192.168.* 哪個更精確？Trie 可以很自然地處理這個問題。

壓縮 Trie（Radix Tree）

如果路徑上的節點只有一個子節點，把它們合併：

一般 Trie:     壓縮 Trie:
  r               r
  |               |
  o              omane
  |
  m
  |
  a
  |
  n
  |
  e

省空間，查找速度不變。Linux kernel 的路由表就用 Radix Tree。

還有兩種是專門為了省記憶體生出來的：Ternary Search Tree 每個節點只留「小於／等於／大於」三個分支，不像標準 Trie 每個節點都掛一張大 Map；Double-Array Trie 乾脆用兩個整數陣列把整棵樹壓平，查找極快、常見於中日韓輸入法和斷詞庫。它們都是拿實作複雜度去換空間，等你真的被 Trie 的記憶體咬到再考慮。

Trie 的空間問題

坦白說，Trie 很吃記憶體。每個節點要存一個 Map（或固定大小的 array），如果字元集很大（比如 Unicode），空間爆炸。

所以在資料量不大的場景，HashSet 通常比 Trie 更實用。Trie 的價值在「前綴操作」——如果你不需要前綴搜尋，其實不用特別選它。

Trie 的名字來自 retrieval，但大家都念成 “try”——可能是因為它真的值得你 try 一下。~~冷到我自己都想刪掉這行。~~

接下來往哪走

AVL Tree 自平衡二元搜尋樹 — 下一篇：從字串專用的樹回到通用的自平衡樹
Aho-Corasick 自動機：同時搜尋所有關鍵字 — Trie 加上 KMP 的失敗函數，就能同時比對十萬個關鍵字
Suffix Array 後綴陣列 — 字串索引的另一條路：不建樹，把所有後綴排序壓進陣列

Terry Yao's Blog

目錄

Trie 前綴樹（字典樹）