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 Black.
Entry modified 25 February 2019.
HTML page formatted Wed Mar 13 12:42:46 2019.
Cite this as:
Paul E. Black, "ternary search tree", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 25 February 2019. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/ternarySearchTree.html