View source for Ternary search tree

{{Short description|Data structure}}
{{distinguish|Binary tree}}
{{Expert needed|1=Computing | reason="Missing the description of a few but in this case very important operations. Missing the pseudocode of all operations (including the missing ones just mentioned). Pseudocode greatly improves the understanding of the operations. Missing rigorous mathematical analysis of the running time complexities."|date=September 2016}}
{{Infobox data structure
|name=Ternary Search Tree (TST)
|type=tree
|search_avg= O(log ''n'')
|search_worst= O(''n'')
|insert_avg= O(log ''n'')
|insert_worst= O(''n'')
|delete_avg= O(log ''n'')
|delete_worst= 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-check]]ing and [[auto-completion]].

==Description==
Each node of a ternary search tree stores a single [[character (arts)|character]], an [[Abstract object|object]] (or a [[pointer (computer programming)|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)''.<ref name="dobbs">{{cite journal |journal=[[Dr. Dobb's]] |title=Ternary Search Trees |url=http://www.drdobbs.com/database/184410528}}</ref> 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.<ref name="ostrov" /> 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''.<ref name="dobbs" /> The ''equal kid'' points to the next character in the word.
The figure below shows a ternary search tree with the strings "cute","cup","at","as","he","us" and "i":

           c
         / | \
        a  u  h
        |  |  | \
        t  t  e  u
      /  / |   / |
     s  p  e  i  s

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.

==Operations==

===Insertion===

Inserting a value into a ternary search can be defined recursively or iteratively 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.<ref name="dobbs" />  Like [[binary search tree]]s and other [[data structures]], ternary search trees can become degenerate depending on the order of the keys.<ref name=wrobel>{{cite web|last=Wrobel|first=Lukasz|title=Ternary Search Tree|url=http://lukaszwrobel.pl/blog/ternary-search-tree}}</ref>{{self-published inline|date=May 2015}} Inserting keys in alphabetical order is one way to attain the worst possible degenerate tree.<ref name="dobbs" /> Inserting the keys in random order often produces a well-balanced tree.<ref name="dobbs" />
<syntaxhighlight lang="pascal" start="1">
function insertion(string key) is
	node p := root 
    //initialized to be equal in case root is null
	node last := root
	int idx := 0
	while p is not null do
        //recurse on proper subtree
		if key[idx] < p.splitchar then
			last := p
			p := p.left
		else if key[idx] > p.splitchar then
			last := p
			p := p.right
		else:
            // key is already in our Tree
			if idx == length(key) then
				return 
            //trim character from our key 
			idx := idx+1
			last := p
			p := p.mid
	p := node()
    //add p in as a child of the last non-null node (or root if root is null)
    if root == null then
        root := p
	else if last.splitchar < key[idx] then
		last.right := p
	else if last.splitchar > key[idx] then
		last.left := p
	else 
		last.mid := p
	p.splitchar := key[idx]
	idx := idx+1
    // Insert remainder of key
	while idx < length(key) do
		p.mid := node()
        p.mid.splitchar := key[idx]
		idx += 1
</syntaxhighlight>

=== Search ===

To look up a particular node or the data associated with a node, a string key is needed. A lookup procedure begins by checking the root node of the tree and determining which of the following conditions has occurred. If the first character of the string is less than the character in the root node, a recursive lookup can be called on the tree whose root is the lo kid of the current root. Similarly, if the first character is greater than the current node in the tree, then a recursive call can be made to the tree whose root is the hi kid of the current node.<ref name="dobbs" />
As a final case, if the first character of the string is equal to the character of the current node then the function returns the node if there are no more characters in the key. If there are more characters in the key then the first character of the key must be removed and a recursive call is made given the equal kid node and the modified key.<ref name="dobbs" />
This can also be written in a non-recursive way by using a pointer to the current node and a pointer to the current character of the key.<ref name="dobbs" />

==== Pseudocode ====
<syntaxhighlight lang="pascal" start="1">
 function search(string query) is
     if is_empty(query) then
         return false
 
     node p := root
     int idx := 0
 
     while p is not null do
         if query[idx] < p.splitchar then
             p := p.left
         else if query[idx] > p.splitchar then
             p := p.right;
         else
             if idx = length(query) then
                 return true
             idx := idx + 1
             p := p.mid
 
     return false
</syntaxhighlight>

=== Deletion ===

The delete operation consists of searching for a key string in the search tree and finding a node, called firstMid in the below pseudocode, such that the path from the middle child of firstMid to the end of the search path for the key string has no left or right children. This would represent a unique suffix in the ternary tree corresponding to the key string. If there is no such path, this means that the key string is either fully contained as a prefix of another string, or is not in the search tree. Many implementations make use of an end of string character to ensure only the latter case occurs. The path is then deleted from firstMid.mid to the end of the search path. In the case that firstMid is the root, the key string must have been the last string in the tree, and thus the root is set to null after the deletion. 
<syntaxhighlight lang="pascal" start="1">
 function delete(string key) is
     if is_empty(key) then
         return 
 
     node p := root
     int idx := 0

 	 node firstMid := null
     while p is not null do
         if key[idx] < p.splitchar then
             firstMid := null
             p := p.left
         else if key[idx] > p.splitchar then
             firstMid := null
             p := p.right
         else
             firstMid := p
             while p is not null and key[idx] == p.splitchar do
             	idx := idx + 1
             	p := p.mid
             
     if firstMid == null then
         return  // No unique string suffix

     // At this point, firstMid points to the node before the strings unique suffix occurs
     node q := firstMid.mid 
     node p := q
     firstMid.mid := null // disconnect suffix from tree
     while q is not null do //walk down suffix path and delete nodes 
         p := q
         q := q.mid 
         delete(p)			// free memory associated with node p
     if firstMid == root then 
         delete(root)       //delete the entire tree
         root := null
</syntaxhighlight>

=== Traversal ===

{{Clarify | a description of the deletion operation should be provided|date=September 2016}}
{{examples |  it would be nice to have the pseudocode for this operation |date=September 2016}}

=== Partial-match searching ===

{{Clarify | a description of the deletion operation should be provided|date=September 2016}}
{{examples |  it would be nice to have the pseudocode for this operation |date=September 2016}}

=== Near-neighbor searching  ===

{{Clarify | a description of the deletion operation should be provided|date=September 2016}}
{{examples |  it would be nice to have the pseudocode for this operation |date=September 2016}}

==Running time==
The running time of ternary search trees varies significantly with the input. Ternary search trees run best when given several ''similar strings'', especially when those strings ''share a common prefix''. Alternatively, ternary search trees are effective when storing a large number of relatively ''short strings'' (such as words in a [[dictionary]]).<ref name ="dobbs" />
Running times for ternary search trees are similar to [[binary search trees]], in that they typically run in logarithmic time, but can run in linear time in the degenerate (worst) case. Further, the size of the strings must also be kept in mind when considering runtime. For example, in the search path for a string of length ''k'', there will be ''k'' traversals down middle children in the tree, as well as a logarithmic number of traversals down left and right children in the tree. Thus, in a ternary search tree on a small number of very large strings the lengths of the strings can dominate the runtime.<ref name="sedgewick">{{cite web|last1=Bentley|last2=Sedgewick |first1=Jon|first2=Bob|title=Ternary Search Tree|url=https://www.cs.upc.edu/~ps/downloads/tst/tst.html}}</ref>

Time complexities for ternary search tree operations:<ref name="dobbs" />

{| class="wikitable"
|-
!  !! Average-case running time !! Worst-case running time
|-
| Lookup || ''O''(log ''n'' + ''k'') || ''O''(''n''  + ''k'')
|-
| Insertion || ''O''(log ''n''  + ''k'') || ''O''(''n''  + ''k'')
|-
| Delete || ''O''(log ''n''  + ''k'') || ''O''(''n''  + ''k'')
|}

==Comparison to other data structures==

===Tries===
While being slower than other [[trie|prefix tree]]s, ternary search trees can be better suited for larger data sets due to their space-efficiency.<ref name="dobbs" />

===Hash maps===
[[Hashtable]]s can also be used in place of ternary search trees for mapping strings to values. However, hash maps also frequently use more memory than ternary search trees (but not as much as tries). Additionally, hash maps are typically slower at reporting a string that is not in the same data structure, because it must compare the entire string rather than just the first few characters. There is some evidence that shows ternary search trees running faster than hash maps.<ref name="dobbs" /> Additionally, hash maps do not allow for many of the uses of ternary search trees, such as ''near-neighbor lookups''.

===DAFSAs ([[deterministic acyclic finite state automaton]])===
If storing dictionary words is all that is required (i.e., storage of information auxiliary to each word is not required), a minimal deterministic acyclic finite state automaton (DAFSA) would use less space than a trie or a ternary search tree. This is because a DAFSA can compress identical branches from the trie which correspond to the same suffixes (or parts) of different words being stored.

==Uses==
Ternary search trees can be used to solve many problems in which a large number of strings must be stored and retrieved in an arbitrary order. Some of the most common or most useful of these are below:

* Anytime a [[trie]] could be used but a less memory-consuming structure is preferred.<ref name ="dobbs" />
* A quick and space-saving data structure for [[Data mapping|mapping]] strings to other data.<ref name="wrobel" />
* To implement [[auto-completion]].<ref name="ostrov">{{cite web |last1=Ostrovsky |first1=Igor |title=Efficient auto-complete with a ternary search tree |url=http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/}}</ref>{{self-published inline|date=May 2015}}
* As a [[spell check]].<ref name=wally>{{cite web |last1=Flint |first1=Wally |date=2001-02-16 |df=mdy |url=https://www.infoworld.com/article/2075027/plant-your-data-in-a-ternary-search-tree.html |title=Plant your data in a ternary search tree |work=[[JavaWorld]] |access-date=2020-07-19}}</ref>
* [[Nearest neighbor search|Near-neighbor searching]] (of which spell-checking is a special case).<ref name ="dobbs" />
* As a [[database]] especially when indexing by several non-key fields is desirable.<ref name="wally" />
* In place of a [[hash table]].<ref name="wally" />

==See also==
* [[Three-way radix quicksort]]
* [[Trie]]
* [[Binary search tree]]
* [[Hashtable]]

==References==
{{reflist}}

==External links==
* [http://www.cs.princeton.edu/~rs/strings/ Ternary Search Trees ] page with papers (by Jon Bentley and Robert Sedgewick) about ternary search trees and algorithms for "sorting and searching strings"
* [https://www.youtube.com/watch?v=CIGyewO7868/ Ternary Search Tries] – a video by Robert Sedgewick
* [http://algs4.cs.princeton.edu/52trie/TST.java.html TST.java.html] Implementation in Java of a TST by Robert Sedgewick and Kevin Wayne

{{CS-Trees}}
{{Strings |state=collapsed}}

[[Category:Trees (data structures)]]
[[Category:Search algorithms]]