A ternary search tree is a special trie data structure where the child nodes of a standard trie are ordered as a binary search tree.
Unlike trie(standard) data structure where each node contains 26 pointers for its children(some pointers are empty), each node in a ternary search tree contains only 3 pointers:
2. The equal pointer points to the node whose value is equal to the value in the current node.
3. The right pointer points to the node whose value is greater than the value in the current node.
An Example Ternary Search Trie with strings [abc, abs, awe, and].
One of the advantage of using ternary search trees over tries is that ternary search trees are a more space efficient (involve only three pointers per node as compared to 26 in standard tries). Further, ternary search trees can be used any time a hashtable would be used to store strings.
Tries are suitable when there is a proper distribution of words over the alphabets so that spaces are utilized most efficiently. Otherwise ternary search trees are better. Ternary search trees are efficient to use(in terms of space) when the strings to be stored share a common prefix.
Ternary search trees are efficient for queries like “Given a word, find the next word in dictionary(near-neighbor lookups)”
Given a word, find the next word in dictionary(near-neighbor lookups)
2. Used in spell checks: Ternary search trees can be used as a dictionary to store all the words. Once the word is typed in an editor, the word can be parallely searched in the ternary search tree to check for correct spelling.
2. Used in spell checks: Ternary search trees can be used as a dictionary to store all the words. Once the word is typed in an editor, the word can be parallely searched in the ternary search tree to check for correct spelling.
struct Node{ char data; // True if this character is last character of one of the words unsigned isEndOfString: 1; struct Node *left, *eq, *right;};// A utility function to create a new ternary search tree nodestruct Node* newNode(char data){ struct Node* temp = (struct Node*) malloc(sizeof( struct Node )); temp->data = data; temp->isEndOfString = 0; temp->left = temp->eq = temp->right = NULL; return temp;}// Function to insert a new word in a Ternary Search Treevoid insert(struct Node** root, char *word){ // Base Case: Tree is empty if (!(*root)) *root = newNode(*word); // If current character of word is smaller than root's character, // then insert this word in left subtree of root if ((*word) < (*root)->data) insert(&( (*root)->left ), word); // If current character of word is greate than root's character, // then insert this word in right subtree of root else if ((*word) > (*root)->data) insert(&( (*root)->right ), word); // If current character of word is same as root's character, else { if (*(word+1)) insert(&( (*root)->eq ), word+1); // the last character of the word else (*root)->isEndOfString = 1; }}// A recursive function to traverse Ternary Search Treevoid traverseTSTUtil(struct Node* root, char* buffer, int depth){ if (root) { // First traverse the left subtree traverseTSTUtil(root->left, buffer, depth); // Store the character of this node buffer[depth] = root->data; if (root->isEndOfString) { buffer[depth+1] = '\0'; printf( "%s\n", buffer); } // Traverse the subtree using equal pointer (middle subtree) traverseTSTUtil(root->eq, buffer, depth + 1); // Finally Traverse the right subtree traverseTSTUtil(root->right, buffer, depth); }}// The main function to traverse a Ternary Search Tree.// It mainly uses traverseTSTUtil()void traverseTST(struct Node* root){ char buffer[MAX]; traverseTSTUtil(root, buffer, 0);}// Function to search a given word in TSTint searchTST(struct Node *root, char *word){ if (!root) return 0; if (*word < (root)->data) return searchTST(root->left, word); else if (*word > (root)->data) return searchTST(root->right, word); else { if (*(word+1) == '\0') return root->isEndOfString; return searchTST(root->eq, word+1); }}private Node get(Node x, String key, int d) { if (key == null) throw new NullPointerException(); if (key.length() == 0) throw new IllegalArgumentException("key must have length >= 1"); if (x == null) return null; char c = key.charAt(d); if (c < x.c) return get(x.left, key, d); else if (c > x.c) return get(x.right, key, d); else if (d < key.length() - 1) return get(x.mid, key, d+1); else return x; } private Node put(Node x, String s, Value val, int d) { char c = s.charAt(d); if (x == null) { x = new Node(); x.c = c; } if (c < x.c) x.left = put(x.left, s, val, d); else if (c > x.c) x.right = put(x.right, s, val, d); else if (d < s.length() - 1) x.mid = put(x.mid, s, val, d+1); else x.val = val; return x; }
http://www.codebytes.in/2015/12/ternary-search-tries-tst-java.htmlhttps://leetcode.com/discuss/36893/ternary-search-trie-implementation-with-java
TST is one of the most common way to implement Trie. Also, R-way needs you to specify the number of children based on different problems, while in TST there are always 3 of them.
class TrieNode {
char val;
TrieNode left, mid, right;
boolean end;
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
if (word != null && !word.isEmpty()) insert(word, 0, root);
}
private TrieNode insert(String word, int index, TrieNode node) {
char ch = word.charAt(index);
if (node == null) node = new TrieNode(ch);
if (ch < node.val) node.left = insert(word, index, node.left);
else if (ch > node.val) node.right = insert(word, index, node.right);
else if (index < word.length() - 1) node.mid = insert(word, index + 1, node.mid);
else node.end = true;
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
if (word == null || word.isEmpty()) return false;
return search(word, 0, root);
}
private boolean search(String word, int index, TrieNode node) {
if (node == null) return false;
char ch = word.charAt(index);
if (ch < node.val) return search(word, index, node.left);
if (ch > node.val) return search(word, index, node.right);
if (index < word.length() - 1) return search(word, index + 1, node.mid);
return node.end;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (prefix == null || prefix.isEmpty()) return false;
return startsWith(prefix, 0, root);
}
private boolean startsWith(String prefix, int index, TrieNode node) {
if (node == null) return false;
char ch = prefix.charAt(index);
if (ch < node.val) return startsWith(prefix, index, node.left);
if (ch > node.val) return startsWith(prefix, index, node.right);
if (index == prefix.length() - 1) return true;
return startsWith(prefix, index + 1, node.mid);
}
}http://hackthology.com/ternary-search-tries-for-fast-flexible-string-search-part-1.html
Usually an R-Way or Multi-Way Trie has a fanout equal to the numbers of characters in the character set or the number of bits in a machine word, half word or byte. So in practice a node in an R-Way Trie might have 256 children or perhaps 2\^16 children. As the fanout (the number of children per node) increases the space efficiency of the Trie decreases. However, the search speed increases. A classic time/space trace off.
Also check http://en.wikipedia.org/wiki/Ternary_search_tree
http://lukaszwrobel.pl/blog/ternary-search-tree
Read full article from Ternary Search Tree | GeeksforGeeks
