Ternary search tree

In computer science, a ternary search tree (trie,TST) is a ternary (three-way) tree data structure which combines the time efficiency of digital tries with the space efficiency of binary search trees. The resulting structure is faster than hashing for many typical search problems, and supports a broader range of useful problems and operations.

A standard digital trie stores strings; each node represents a particular string prefix, and branches "N" ways, where "N" is the size of the set of characters which could come next in the string. If "N" is large, the nodes may be very large even if the trie is sparsely populated. A ternary search tree may be thought of as a digital trie in which each "N"-way branching node has been replaced with a binary search tree; there are only as many nodes in each of these binary trees as there would be non-empty branches of the corresponding trie node, and the binary nodes have one extra link each, corresponding to what the trie node would link to for that branch.

Tries had traditionally used nodes of fixed size. Each node contained a fixed number of pointers. This led to wastage of space when few keys were used. As an alternative, the nodes were allowed to have variable sizes, by considering each node a doubly-linked list that stored only the necessary pointers. But this made the search less efficient, and wasted even more space as the structure grew. Conceptually, the structure obtained by replacing the doubly-linked list with a binary search tree is same as the TST. Now the search is more efficient because BST searching is much faster than traversing the linked list.

The construction of a binary search tree is closely related to quicksort. Similarly the construction of a TST is closely related to quicksort with three-way partitioning (quick-radix sort, to be exact).

ee also

*Ternary search
*Search algorithm
*Binary search
*Interpolation search
*Linear search

References

*"Algorithms in C/C++/Java", third ed. (Parts 1-4), Robert Sedgewick, Addison Wesley.

External links

* [http://www.cs.princeton.edu/~rs/strings/ Ternary Search Trees]
* [http://www.ddj.com/documents/s=921/ddj9804a/ Ternary Search Trees (Dr. Dobbs)]
* [http://search.cpan.org/~mrogaski/Tree-Ternary-0.03/Ternary.pm Tree::Ternary (Perl module)]
* [http://dasnar.sdf-eu.org/res/ctst-README.html Ternary Search Tree code]
* [http://abc.se/~re/code/tst/ STL-compliant Ternary Search Tree in C++]
* [http://ternary.sourceforge.net Ternary Search Tree in C++]