三叉搜尋樹

三叉搜尋樹（英語：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)}$

描述

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

參考文獻

1. A. R. Hurson，Marvin Zelkowitz. Advances in Computers: Parallel, Distributed, and Pervasive Computing. Academic Press. 2005 [2015-02-02]. ISBN 9780120121632. （原始內容存檔於2016-03-04）.
2. Ostrovsky, Igor. Efficient auto-complete with a ternary search tree. [2015-02-02]. （原始內容存檔於2015-02-07）.