樹與層次結構
字典樹
字典樹是一種專為儲存字串而生的樹：你所走過的路徑拼出了鍵，而不是把鍵塞進某一個節點。每條邊都標著一個字元，於是單詞「cat」就是從根出發的路徑 c → a → t。共享前綴的單詞也共享拼出該前綴的那段路徑：「car」和「cat」會一起經過 c → a，再分叉開來。它的名字源自 reTRIEval（檢索），讀音通常念作「try」，以便和「tree（樹）」區分。
查找一個鍵就是從根出發、一次一個字元地往下走，所以一次搜尋耗時 O(L)，其中 L 是字串的長度——而且很妙的是，存的單詞越多，它也不會變慢。這相對於平衡搜尋樹是個實打實的優勢，後者的 O(log n) 會隨鍵的數量增長。通常會在某個節點上做標記，表示「這裡結束了一個完整單詞」，於是「car」和「card」可以同時存在於這同一個結構裡。
正因為共享前綴寄存在共享路徑上，字典樹幾乎免費地回答前綴問題：走到「ca」所對應的節點，它底下的一切都是以「ca」開頭的單詞——這恰好是自動完成、拼字檢查器和 IP 路由表所需要的。代價是記憶體：樸素的節點會為每個可能的下一個字元都留一個槽位（比如小寫字母就是 26 個），所以稀疏的字典樹會浪費不少空間，這也是為什麼會有基數樹這樣的壓縮變體。
// root
// |c
// (c)
// |a
// (a)
// r/ \t
// (r)* (t)* <- car, cat
// |d
// (d)* <- card
struct TrieNode {
std::array<TrieNode*, 26> next{}; // a..z
bool isWord = false;
};每個子節點槽位以下一個字元為鍵；isWord 標記一個完整的鍵。
讀作「try」（源自 reTRIEval），以與「tree」區分；查找開銷 O(L) 取決於鍵的長度，而非已存鍵的數量。
又稱
另見