Definition: A 3-way tree where every node's left subtree has keys less than the node's key, every middle subtree has keys equal to the node's key, and every right subtree has keys greater than the node's key. If the key is a multikey (string, array, list, etc.), the middle subtree organizes by the next subkey (character, array or list item, etc.)
Also known as TST.
Generalization (I am a kind of ...)
k-ary tree with k=3, search tree.
See also trie, binary search tree, multikey Quicksort.
The wikipedia entry.
Although not named, ternary search trees are described in
Jon Louis Bentley and James B. Saxe, Algorithms on Vector Sets, SIGACT News, pages 36-39, Fall 1979.
Jon Bentley and Robert Sedgewick, Ternary Search Trees, Dr. Dobb's Journal, April 1998.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 26 July 2010.
HTML page formatted Tue Dec 6 16:16:33 2011.
Cite this as:
Paul E. Black, "ternary search tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 26 July 2010. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/ternarySearchTree.html