跳至內容

三叉搜索樹

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
三叉搜索樹
類型tree
大O符號表示的時間複雜度
算法 平均 最差
搜尋
插入
刪除

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

描述

[編輯]

三叉搜索樹的每個節點存儲了一個字符、一個值對象或值指針以及三個指向子節點的指針。這三個字節點常被稱為等位子節點、低位子節點和高位子節點。[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).