Ternary search tries

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