查看“︁三叉搜索树”︁的源代码

{{NoteTA
|G1 = IT
}}
{{Infobox data structure
|name=三叉搜索树
|type=tree
|search_avg= <math>O(\log n)</math>
|search_worst= <math>O(n)</math>
|insert_avg= <math>O(\log n)</math>
|insert_worst= <math>O(n)</math>
|delete_avg= <math>O(\log n)</math>
|delete_worst= <math>O(n)</math>
}}
'''三叉搜索树'''（{{lang-en|Ternary search tree}}，縮寫：'''TST'''）在计算机科学中是[[trie树]]或[[前缀树]]的一种实现，树的各个节点之间的结构类似[[二叉搜索树]]。和其他的前缀树一样，三叉搜索树可以用于实现带前缀搜索功能的关联数组。三叉搜索树比标准的前缀树更节省空间，但是牺牲了部分查找速度。三叉搜索树常用于实现[[拼写检查]]和[[自动完成]]功能。<ref>{{cite book|url=https://books.google.com.hk/books?id=0klz4i-wagAC&pg=PA250&dq=Ternary+search+tree&hl=zh-CN&output=html_text&sa=X&ei=8QbPVPODD-rdsATY4oLACg&ved=0CBsQ6AEwAA|title=Advances in Computers: Parallel, Distributed, and Pervasive Computing|author=A. R. Hurson，Marvin Zelkowitz|publisher=Academic Press|year=2005|isbn=9780120121632|access-date=2015-02-02|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304102825/https://books.google.com.hk/books?id=0klz4i-wagAC&pg=PA250&dq=Ternary+search+tree&hl=zh-CN&output=html_text&sa=X&ei=8QbPVPODD-rdsATY4oLACg&ved=0CBsQ6AEwAA|dead-url=no}}</ref>

==描述==
三叉搜索树的每个节点存储了一个字符、一个值对象或值指针以及三个指向子节点的指针。这三个字节点常被称为等位子节点、低位子节点和高位子节点。<ref name="ostrov">{{cite web|last=Ostrovsky|first=Igor|title=Efficient auto-complete with a ternary search tree|url=http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/|accessdate=2015-02-02|archive-date=2015-02-07|archive-url=https://web.archive.org/web/20150207015742/http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/|dead-url=no}}</ref>
==参考文献==
{{reflist}}
{{-}}
{{计算机科学中的树}}

[[Category:树结构]]