Ternary search tree

From Wikipedia, the free encyclopedia

This article may be confusing or unclear to readers. Please help clarify the article; suggestions may be found on the talk page. (December 2006)

In computer science, a ternary search tree is a ternary (three-way) tree data structure of strings which combines the speed of a prefix search tree, or trie, with the space efficiency of a binary search tree.^[1]

Binary trees and tries represent different approaches to looking up strings. In a binary tree, each node represents one string in the data set. Thus, the number of nodes is minimized. Also, each node contains links to only two other nodes. Thus, the size of each node is minimal. Binary search trees are very compact. However, to find a string within the tree, that entire string must be compared with the entire string contained at each node searched. This is slow.

A trie is optimized for speed at the expense of size. Descending the trie only involves looking at each character once, eliminating string comparisons. In the most basic implementation, each node has as many children as letters in the string's alphabet. The trie is navigated by looking up the string's characters in sequence and descending through the nodes. The process is fast, but the number and size of the nodes is large.

The ternary search tree replaces each node of the trie with a modified binary search tree. For sparse tries, this binary tree will be smaller than a trie node. Each binary tree implements a single-character lookup. It has the typical left and right children which are checked if the lookup character is greater or less than the node's character, respectively. A third child is used if the lookup character is found on that particular node. Unlike the other children, it links to the root of the binary search tree for the next character in the string.

Therefore, string lookup in a ternary search tree consists of a series of binary searches for individual characters.

Ternary search trees are usually rejected in modern practice in favor of hash tables. Also, there are other ways to construct a trie. For example, a radix tree trie in which each node stores a bit string, and has two children for the possible next bits, may be more compact than a ternary search tree without being slow.

[edit] See also

• Ternary search
• Search algorithm
• Binary search
• Interpolation search
• Linear search

[edit] References

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

[edit] External links

• Ternary Search Trees
• Ternary Search Trees (Dr. Dobbs)
• Tree::Ternary (Perl module)
• Ternary Search Tree code
• STL-compliant Ternary Search Tree in C++
• Ternary Search Tree in C++

v • d • e Trees in Computer Science Binary trees Binary search tree (BST) · Van Emde Boas tree · Cartesian tree · Top Tree · T-tree Self-balancing binary search trees Red-black tree · AVL tree · AA tree · Splay tree · Scapegoat tree · Treap B-trees B+ tree · B*-tree · UB-tree · 2-3 tree · 2-3-4 tree · (a,b)-tree · Dancing tree · Htree · Bx-tree Tries Suffix tree · Radix tree · Ternary search tree Binary space partitioning (BSP) trees Quadtree · Octree · kd-tree (implicit) · VP-tree Non-binary trees Exponential tree · Fusion tree · Interval tree · PQ tree · Range tree · SPQR tree Trees used in computer graphics R-tree · X-tree · Segment tree Other trees Heap · Hash tree · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · Expectiminimax tree · iDistance

This data structure-related article is a stub. You can help Wikipedia by expanding it. v • d • e