三叉搜索树
(重定向自三元搜索树)
三叉搜索树(英语:Ternary search tree,缩写:TST)在计算机科学中是trie树或前缀树的一种实现,树的各个节点之间的结构类似二叉搜索树。和其他的前缀树一样,三叉搜索树可以用于实现带前缀搜索功能的关联数组。三叉搜索树比标准的前缀树更节省空间,但是牺牲了部分查找速度。三叉搜索树常用于实现拼写检查和自动完成功能。[1]
三叉搜索树 | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | tree | ||||||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||||||
|
描述
编辑三叉搜索树的每个节点存储了一个字符、一个值对象或值指针以及三个指向子节点的指针。这三个字节点常被称为等位子节点、低位子节点和高位子节点。[2]
参考文献
编辑- ^ A. R. Hurson,Marvin Zelkowitz. Advances in Computers: Parallel, Distributed, and Pervasive Computing. Academic Press. 2005 [2015-02-02]. ISBN 9780120121632. (原始内容存档于2016-03-04).
- ^ Ostrovsky, Igor. Efficient auto-complete with a ternary search tree. [2015-02-02]. (原始内容存档于2015-02-07).