Ternary search tree

From Wikipedia, the free encyclopedia

All or part of this article may be confusing or unclear.
Please help clarify the article. Suggestions may be on the talk page. (August 2006)

This article or section is in need of attention from an expert on the subject.
Please help recruit one or improve this article yourself. See the talk page for details.
Please consider using {{Expert-subject}} to associate this request with a WikiProject

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).