字典樹／前綴樹（trie）
/ TRY or TREE /
想像一個老式的、按拼字排列的卡片目錄：所有以 'c' 開頭的詞都在 'c' 標籤後面，接著 'ca' 在子標籤後，然後 'cat'、'car'、'cab' 再往外分岔。trie 正是把這個想法做成一棵樹。每條邊以一個字元標記，從根往下到某節點的路徑就拼出一個前綴。開頭相同的詞共享路徑的上半段，所以這個結構自然地依共同前綴分組。
具體來說，trie 是一棵有根樹，每個節點對每個字母符號最多有一個子節點。要插入一個詞，你從根沿著它的字元往下走，建出任何缺少的節點，並把最後的節點標記為一個詞的結尾。要查找一個詞，你走同一條路徑；走到一個標記為「詞尾」的節點就表示它存在。搜尋或插入一個長度為 L 的詞花費 O(L)，與 trie 裝了多少個詞無關——代價取決於詞，而非字典大小，這是相對於平衡二元搜尋樹的關鍵優勢，後者每次比較本身就要掃過一整個字串。trie 也讓前綴查詢變得輕而易舉：要找所有以 "car" 開頭的詞，走到 "car" 節點，蒐集它子樹裡的一切即可。樸素的 trie 在許多節點只有單一子節點時會浪費記憶體；壓縮 trie（又稱基數樹或 Patricia 樹）把每條這樣的鏈合併成一條標記著整個子字串的邊，在保留行為的同時縮小結構。
凡是前綴重要的地方都有 trie：自動完成與預測輸入、IP 路由表（最長前綴匹配）、拼字檢查器，以及作為 Aho-Corasick 多模式比對的骨幹。誠實的取捨在於空間：在大字母表上的樸素 trie，每個節點對每個符號可能用掉一個子指標欄位，對稀疏資料而言很浪費——因此有壓縮版本以及「陣列對雜湊表」的各種變體。但對以前綴為核心的工作負載，trie 的 O(長度) 操作和輕鬆的前綴列舉，很難被超越。
插入 "car"、"card"、"cat"。根有一個子節點 'c'，然後 'a'，再分岔到 'r' 和 't'。'r' 節點（拼出 "car"）被標記為詞尾，並繼續到 'd'（"card"，也是詞尾）。搜尋 "care" 走 c-a-r 後找不到 'e' 子節點，所以它不存在；列出 "car" 子樹立刻得到 "car" 和 "card"。
共同前綴共享路徑；搜尋與插入花費 O(詞長)，而前綴查詢就是走一趟子樹。
trie 的速度是 O(詞長)，不是 O(log n)——與儲存的詞數無關——但在大字母表上可能很吃記憶體；當單子節點鏈占多數時，改用壓縮（基數）trie。'trie' 一詞源自 're-trie-val'，常念作 'try' 以避免和 'tree' 混淆。