Trie
在電腦科學中，trie，又稱字首樹或字典樹，是一種有序樹，用於儲存關聯陣列，其中的鍵通常是字串。與二元搜尋樹不同，鍵不是直接儲存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的字首，也就是這個節點對應的字串，而根節點對應空字串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。
Trie 這個術語來自於 retrieval。根據詞源學，trie 的發明者 Edward Fredkin 把它讀作 /ˈtriː/ "tree"。但是，其他作者把它讀作 /ˈtraɪ/ "try"。在圖示中，鍵標註在節點中，值標註在節點之下。每一個完整的英文單詞對應一個特定的整數。Trie 可以看作是一個確定有限狀態自動機，儘管邊上的符號一般是隱含在分支的順序中的。
鍵不需要被顯式地儲存在節點中。圖示中標註出完整的單詞，只是為了演示 trie 的原理。
trie 中的鍵通常是字串，但也可以是其它的結構。trie 的演算法可以很容易地修改為處理其它結構的有序序列，比如一串數字或者形狀的排列。比如，bitwise trie 中的鍵是一串位元，可以用於表示整數或者記憶體位址。