Ternary Search Tree Algorithm

A ternary search tree is a trie-like data structure, sometimes described as a type of prefix tree, whose nodes are arranged similarly to a binary search tree but with up to three children rather than two. Each node stores a single character together with three child pointers, a low child for characters that sort before it, a high child for characters that sort after it, and an equal child that leads to the next character of the same string, so that walking down a path of equal children spells out a stored string one character at a time. This layout makes ternary search trees more space efficient than a standard prefix trie at some cost in lookup speed, and they are well suited to storing large numbers of relatively short strings that share common prefixes, with common applications including spell checking, autocompletion, near-neighbor string search and database indexing.