The ternary search tree is a trie. Each node arranged similarly to a binary search tree. It supports up to three children rather than the two children (binary trees limit of two).
Write a program to implement Ternary search tries.
Algorithm Explanation
![]() | Build ternary search tree using strings. |
![]() | Insert operation uses root node and calls utility function. The utility function inserts the array of characters into the tree. |
![]() | The left pointer contains less than the current node value. |
![]() | The equal pointer contains equal to the current node value. |
![]() | A right pointer contains greater to the current node value. |
![]() | Delete operation compare the word pointer to data. If the data is greater than word pointer, delete recursively left subtree. If less than, delete right subtree recursively. |
Source Code
package com.dsacode.DataStructre.trie; import java.util.ArrayList; class TSTNode { char data; boolean isEnd; TSTNode left, middle, right; public TSTNode(char data){ this.data = data; this.isEnd = false; this.left = null; this.middle = null; this.right = null; } } public class TernarySearchTree { private TSTNode root; private ArrayList < String > al; public TernarySearchTree() { root = null; } public boolean isEmpty() { return root == null; } public void makeEmpty() { root = null; } public void insert(String word) { root = insert(root, word.toCharArray(), 0); } private TSTNode insert(TSTNode r, char[] word, int ptr){ if (r == null) r = new TSTNode(word[ptr]); if (word[ptr] < r.data) r.left = insert(r.left, word, ptr); else if (word[ptr] > r.data) r.right = insert(r.right, word, ptr); else { if (ptr + 1 < word.length) r.middle = insert(r.middle, word, ptr + 1); else r.isEnd = true; } return r; } public void delete(String word) { delete(root, word.toCharArray(), 0); } private void delete(TSTNode r, char[] word, int ptr) { if (r == null) return; if (word[ptr] < r.data) delete(r.left, word, ptr); else if (word[ptr] > r.data) delete(r.right, word, ptr); else { if (r.isEnd && ptr == word.length - 1) r.isEnd = false; else if (ptr + 1 < word.length) delete(r.middle, word, ptr + 1); } } public boolean search(String word){ return search(root, word.toCharArray(), 0); } private boolean search(TSTNode r, char[] word, int ptr) { if (r == null) return false; if (word[ptr] < r.data) return search(r.left, word, ptr); else if (word[ptr] > r.data) return search(r.right, word, ptr); else { if (r.isEnd && ptr == word.length - 1) return true; else if (ptr == word.length - 1) return false; else return search(r.middle, word, ptr + 1); } } public String toString() { al = new ArrayList < String >(); traverse(root, ""); return "Ternary Search Tree : "+ al; } private void traverse(TSTNode r, String str) { if (r != null) { traverse(r.left, str); str = str + r.data; if (r.isEnd) al.add(str); traverse(r.middle, str); str = str.substring(0, str.length() - 1); traverse(r.right, str); } } public static void main(String[] args) { TernarySearchTree tst = new TernarySearchTree(); System.out.println("Insert values into Ternary Search Tree"); tst.insert( "bug" ); tst.insert( "cat" ); tst.insert( "cats" ); tst.insert( "can" ); tst.insert( "dog" ); tst.insert( "dump" ); System.out.println(tst.toString()); System.out.println("\nSearch 'cats' in Ternary search tree result : "+ tst.search( "cats" )); System.out.println("Delete 'cat' in Ternary search"); tst.delete( "cat" ); System.out.println(tst.toString()); System.out.println("Empty Status : "+ tst.isEmpty() ); System.out.println("Clear Ternary Search Tree"); tst.makeEmpty(); } }
Output
Insert values into Ternary Search Tree Ternary Search Tree : [bug, can, cat, cats, dog, dump] Search 'cats' in Ternary search tree result : true Delete 'cat' in Ternary search Ternary Search Tree : [bug, can, cats, dog, dump] Empty Status : false Clear Ternary Search Tree