Ternary search tree
In computer science, a ternary search tree is a type of prefix tree where nodes are arranged as a binary search tree. 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.
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.
In this blog post I present a c# version of Ternary Search Tree.
The interface
The interface above defines the API for the data structure. Lets take a deeper look.
void Add(string key, T value) Add a key value pair in the tree. bool Contains(string key) Check whether a key is in tree. IEnumerable Keys Return all keys in the tree. int Length Returns the length of the tree. IEnumerable NearSearch(string query, int distance) Returns all values for keys in the dictionary that are within a given Hamming distance of a query. IEnumerable PrefixMatch(string prefix) Returns all keys starting with a given prefix. IEnumerable Search(string prefix) Searches all values of keys starting with given prefix. T this[string key] Gets the node value with the specified key IEnumerable WildcardMatch(string pat) Returns all keys matching given wilcard pattern.
The Trie Node
The Class is mostly self explanatory, but the key points to note is that it contains three internal node(sub-tries) unlike a traditional trie node.
Adding node in the data structure
Get
and finally
PrefixMatch
To see a complete working example check out the Github page here.
Full repo can be found here. There is a test web application demonstrating auto suggest included in the project, I will write more about it in a later post.