ternary search tree

(data structure)

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.

Author: PEB

Implementation

papers, demos, and code (C). Richard McGraw's explanation, example, and links to other implementations (C++, Java) and his implementations called ctst-dist-0.30.tar.* (C). Ternary Search Tree Dictionary in (C#): Faster String Dictionary! by Jonathan de Halleux.

More information

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.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 13 January 2014.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "ternary search tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 13 January 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/ternarySearchTree.html