Ternary search tree
| Ternary Search Tree (TST) | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | tree | ||||||||||||||||
| Time complexity in big O notation | |||||||||||||||||
|
|||||||||||||||||
| Algorithm | Average | Worst Case | |
|---|---|---|---|
| Search | O(log n) | O(n) | |
| Insert | O(log n) | O(n) | |
| Delete | O(log n) | O(n) |
In computer science, a ternary search tree is a type of trie (sometimes called a prefix tree) where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Like other prefix trees, a ternary search tree can be used as an associative map structure with the ability for incremental string search. However, ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. Common applications for ternary search trees include spell-checking and auto-completion.
Each node of a ternary search tree stores a single character, an object (or a pointer to an object depending on implementation), and pointers to its three children conventionally named equal kid, lo kid and hi kid, which can also be referred respectively as middle (child), lower (child) and higher (child). A node may also have a pointer to its parent node as well as an indicator as to whether or not the node marks the end of a word. The lo kid pointer must point to a node whose character value is less than the current node. The hi kid pointer must point to a node whose character is greater than the current node.The equal kid points to the next character in the word. The figure below shows a ternary search tree with the strings "as", "at", "cup", "cute", "he", "i" and "us":
As with other trie data structures, each node in a ternary search tree represents a prefix of the stored strings. All strings in the middle subtree of a node start with that prefix.
Inserting a value into a ternary search can be defined recursively much as lookups are defined. This recursive method is continually called on nodes of the tree given a key which gets progressively shorter by pruning characters off the front of the key. If this method reaches a node that has not been created, it creates the node and assigns it the character value of the first character in the key. Whether a new node is created or not, the method checks to see if the first character in the string is greater than or less than the character value in the node and makes a recursive call on the appropriate node as in the lookup operation. If, however, the key's first character is equal to the node's value then the insertion procedure is called on the equal kid and the key's first character is pruned away. Like binary search trees and other data structures, ternary search trees can become degenerate depending on the order of the keys. Inserting keys in alphabetical order is one way to attain the worst possible degenerate tree. Inserting the keys in random order often produces a well-balanced tree.
...
Wikipedia