雜湊表把字串整條折成一個數，查詢是期望 (O(1)) 或 (O(L))（(L) 是字串長），但「所有以 ca 開頭的鍵」「最長的符合前綴」要不是掃全表，就是另外建索引。字典樹把這個前綴結構直接做成樹。KMP 教材提到的 Aho–Corasick、模糊搜尋教材裡的 Trie+編輯距離，都從這一棵樹出發。
相關教材：Hash/Hash_Algorithms_Teaching_Materials.md、KMP_Complete_Teaching_Materials.md、Fuzzy_Search_Complete_Teaching_Materials.md。
目錄
1. 它比雜湊多出來的操作
假設鍵都是小寫英文字：
| 操作 | 雜湊表 | 字典樹 |
|---|---|---|
| 插入 / 精確查詢 | 期望 (O(L)) | (O(L)) 最壞 |
| 列舉某個前綴下的所有鍵 | 掃全表 | 走到前綴節點，再 DFS 子樹 |
| 最長符合前綴 | 不直接支援 | 沿字串往下走，記住最後一個「是鍵」的節點 |
| 順序遍歷 | 無 | 孩子依字母排序的話，就是字典序 |
代價是空間：每個字元一個節點，稀疏的字母表會有很多空指標。鍵是任意 64 位元整數時，雜湊或平衡樹通常更合適。鍵是字串、又要前綴時，用字典樹。
2. 節點裡有什麼
節點：
child[26] # 或一棵 map<char, 節點>
terminal # 這個節點是不是某個鍵的結尾terminal 必須獨立於「有沒有孩子」。car 是一個鍵，同時也是 card 的前綴。代表 car 的節點既是結尾，又有孩子 d。只靠「沒有孩子」來判斷結尾，會把 car 漏掉。
空字串若也是合法鍵，根節點的 terminal 就是真。
3. 插入與查詢
插入 s：從根出發，對 s 的每個字元，沒有對應孩子就新建，然後走下去。走完把該節點標成結尾。
精確查詢：同樣往下走。路徑斷了就是沒有。走完還要看 terminal。只走完表示「它是某個鍵的前綴」，不表示它自己是鍵。
4. 手算一棵小樹
依序插入 cat、car、card、dog。
root
├─ c
│ └─ a
│ ├─ t [鍵 cat]
│ └─ r [鍵 car]
│ └─ d [鍵 card]
└─ d
└─ o
└─ g [鍵 dog]節點數：根 + c,a,t + r,d + d,o,g。card 重用 car 的前綴，只多一個 d。四個字串共 3+3+4+3=13 個字元，樹的邊少於 13，因為 ca 與 car 被共享。
查 car：走到 r，terminal 為真。查 ca：走到 a，不是結尾，回傳假。查 card：真。查 do：走到 o，不是結尾。查 dot：在 o 沒有孩子 t，路徑斷了。
5. 前綴查詢與最長前綴
列舉前綴 ca。 先走到 a。從那裡 DFS，每次碰到 terminal 就輸出目前拼出的字串。得到 cat、car、card。若前綴節點不存在，答案是空集合。
最長鍵前綴。 查 carpet。
| 消費的字元 | 所在節點 | 是鍵嗎 | 目前最佳 |
|---|---|---|---|
| c | c | 否 | （無） |
| a | a | 否 | （無） |
| r | r | 是 car |
car |
| p | 沒有孩子 | 停止 |
回傳 car。後面的 pet 不必再看。
查 dogma 會在 dog 更新最佳，下一個 m 走不下去，回傳 dog。
這個操作是路由器「最長前綴匹配」的字串版。IP 位址那一種通常改用二元字典樹（每個節點只有 0 與 1），原則相同。
6. 刪除
刪掉 car，但 card 還在：只把 car 那個節點的 terminal 改成假，節點留著，因為 card 還要經過它。
刪掉 card 且沒有其他鍵經過那條尾巴：從 d 往回剪，直到遇到「仍是結尾」或「還有別的孩子」的節點。car 的節點是結尾，剪到那裡要停。
刪掉不存在的鍵應是 no-op，不要把前綴的 terminal 誤清掉。
7. R 叉樹與三元搜尋樹
R 叉（本篇的 26 孩子）：字母表大小 (R) 固定時，走一步是 (O(1))。(R=256) 且節點用陣列，空指標非常多。Unicode 整張碼表不適合用陣列，改用 map 或先正規化成位元組再當 256 叉。
三元搜尋樹（ternary search trie）：每個節點只有小於、等於、大於三個孩子，像 BST 嵌在字元上。空間接近 (O(\text{總字元數}))，查詢多一個字母表上的搜尋，實務常數常常比稀疏的大陣列好。本站若只需要正確的前綴語意，R 叉或 map 版就夠。
8. 複雜度
令 (L) 為操作的字串長度，(N) 為已存字元節點數（共享前綴後）。
| 操作 | 時間 | 額外空間 |
|---|---|---|
| 插入 / 精確查詢 / 刪除 | (O(L)) | 插入最多新增 (L) 個節點 |
| 列舉某前綴下的 (M) 個鍵 | (O(L + \text{子樹大小})) | — |
| 全部鍵的總空間 | — | (\Theta(N)) 個節點 |
和雜湊比，精確查詢的最壞時間是確定的 (O(L))，沒有碰撞退化。和平衡 BST（鍵是整個字串）比，比較次數從 (O(L\log n)) 降到 (O(L))，而且前綴是一等公民。
Aho–Corasick 在這棵樹上再加失敗指標，才能在一次掃描裡匹配多個模式。那是 KMP 的失敗函數推廣，見 KMP 教材的延伸，不要和「字典樹本身」混成同一個演算法。
9. 常見陷阱
- 忘記
terminal。 前綴存在不代表鍵存在。 - 刪除時剪掉還在用的前綴。
card還在就不能釋放car的節點。 - 大小寫與正規化。
Car與car是兩條路徑，除非插入前先轉小寫。 - 用
std::string當 BST 的鍵來假裝 Trie。 前綴查詢會退化成掃一個範圍，而且每個比較仍可能看完整個字串。那是合法的有序表，不是字典樹。 - 字母表用錯索引。
'c' - 'a'只對小寫英文合法。其他字元會寫出界。
10. C++ 實作
#include <algorithm>
#include <string>
#include <vector>
struct Node {
int child[26];
bool terminal = false;
Node() { std::fill(std::begin(child), std::end(child), -1); }
};
class Trie {
public:
Trie() { nodes_.emplace_back(); }
void insert(const std::string& s) {
int u = 0;
for (char ch : s) {
int c = ch - 'a';
if (nodes_[u].child[c] < 0) {
nodes_[u].child[c] = static_cast<int>(nodes_.size());
nodes_.emplace_back();
}
u = nodes_[u].child[c];
}
nodes_[u].terminal = true;
}
bool contains(const std::string& s) const {
int u = walk(s);
return u >= 0 && nodes_[u].terminal;
}
bool has_prefix(const std::string& s) const { return walk(s) >= 0; }
private:
std::vector<Node> nodes_;
int walk(const std::string& s) const {
int u = 0;
for (char ch : s) {
int c = ch - 'a';
if (c < 0 || c >= 26) return -1;
u = nodes_[u].child[c];
if (u < 0) return -1;
}
return u;
}
};節點用 arena（vector）而不是裸指標，索引 -1 表示沒有孩子，避免每個節點 26 次獨立配置。
11. 練習題
- 在第 4 節的樹上查
carpet的最長鍵前綴、查ca是否為鍵、列舉前綴c。 - 刪除
car之後，card與cat還能查到嗎？car那個節點還在嗎？ - 插入
a、ab、abc。這棵樹有幾個terminal為真的節點？ - 為什麼 26 叉陣列在只存 1000 個很長、幾乎沒有共享前綴的 Unicode 字串時會浪費空間？該換什麼？
- 雜湊表要支援「最長鍵前綴」，最少要額外付出什麼？
參考答案
- 最長鍵前綴是
car。ca不是鍵。前綴c下列出cat、car、card。 card與cat都還在。car的節點必須留下，因為card經過它，只是terminal改為假。- 三個：
a、ab、abc各自的結尾。三個節點排成一條鏈，每個都是結尾。 - 每個節點固定 26 或 256 格，字母幾乎不重複時共享很少，空格數量是 (O(NR))。改成
map或三元搜尋樹，空間跟著實際出現的字元走。Unicode 應先編碼成位元組或碼點再決定分支。 - 要不是對每個鍵的每個前綴都存進雜湊表（空間乘上平均長度），就是查詢時從長到短截斷字串逐次雜湊（時間乘上長度）。字典樹把這兩件事合成沿路徑走一次。
小結
字典樹用一條字元路徑表示鍵，共享前綴，並用一個布林值標出結尾。精確查詢是 (O(L))，前綴列舉與最長前綴是它比雜湊多出來的能力。刪除只能清掉結尾標記，還有後綴在用的節點不能釋放。多模式匹配與模糊字典是這棵樹的延伸，不是另一種插入法。