三元搜尋樹

三叉搜尋樹是在計算機科學中是trie樹或前綴樹的一種實現，樹的各個節點之間的結構類似二叉搜尋樹。

基本介紹

• 中文名：三叉搜尋樹
• 外文名：Ternary search tree

和其他的前綴樹一樣，三叉搜尋樹可以用於實現帶前綴搜尋功能的關聯數組。三叉搜尋樹比標準的前綴樹更節省空間，但是犧牲了部分查找速度。三叉搜尋樹常用於實現拼寫檢查和自動完成功能。

三叉搜尋樹的每個節點存儲了一個字元、一個值對象或值指針以及三個指向子節點的指針。這三個位元組點常被稱為等位子節點、低位子節點和高位子節點。