三叉搜索樹

三叉搜索樹（英語：Ternary search tree，縮寫：TST）在計算機科學中是trie樹或前綴樹的一種實現，樹的各個節點之間的結構類似二叉搜索樹。和其他的前綴樹一樣，三叉搜索樹可以用於實現帶前綴搜索功能的關聯數組。三叉搜索樹比標準的前綴樹更節省空間，但是犧牲了部分查找速度。三叉搜索樹常用於實現拼寫檢查和自動完成功能。^[1]

三叉搜索樹
類型	tree
用大O符號表示的時間複雜度 算法 平均 最差 搜尋 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 插入 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 刪除 ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ 用大O符號表示的空間複雜度

描述

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