Ternary Search Tries TSTs Character based Operations - Java

Additional functions added -

1. Iterable<String> keys()                   - all keys

2. Iterable<String> keysWithPrefix(String s) - keys having s as a prefix 

3. String longestPrefixOf(String s)          - longest key that is a prefix of s

Source:

import java.util.LinkedList;
import java.util.Queue;


public class TSTFunctions<T> {
    class Node{
        char c;
        T v;
        Node left, mid, right;
        
        Node(){}
        Node(char c){this.c = c;}
        Node(T v){this.v = v;}
        Node(char c, T v){this.c = c;this.v = v;}
    }
    
    Node root; 
    
    public void add(String s, T value){ 
       root = add(root, s, 0, value);
    }
    
    private Node add(Node n, String s, int i, T value){  
        if(n==null){ 
            n = new Node(s.charAt(i));
            if(i==s.length()-1){n.v = value; return n;}
        }
        if(s.charAt(i)==n.c){
            if(i==s.length()-1){n.v = value; return n;}
            n.mid = add(n.mid, s, i+1, value);
        }
        else if(s.charAt(i)<n.c){
            n.left = add(n.left, s, i, value);
        }
        else{
            n.right = add(n.right, s, i, value);
        }
        return n;
    }
    
    public boolean findKey(String s){ 
        return findKey(root, s, 0); 
    }
    
    private boolean findKey(Node n, String s, int i){  
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){
                if(n.v!=null){System.out.println(n.v); return true;} 
                else {
                    return false;
                }
            }
        }else if(i>s.length())return false; 
        if(s.charAt(i)==n.c){
            return findKey(n.mid, s, i+1);
        }
        else if(s.charAt(i)<n.c){
            return findKey(n.left, s, i);
        }
        else {
            return findKey(n.right, s, i);
        }        
    }
    
    public void delete(String s){
        delete(root, s, 0);
    }
    
    private boolean delete(Node n, String s, int i){
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){
                if(n.v!=null){n.v = null;return true;}
                else return false;
            }
        }else if(i>s.length())return false; 
        
        boolean r;
        if(s.charAt(i)==n.c){
            if((r=delete(n.mid, s, i+1))){ 
                if(n.mid.v == null && n.mid.left == null 
                   && n.mid.mid == null && n.mid.right == null)n.mid = null;
            }
        }else if(s.charAt(i)<n.c){
            if((r=delete(n.left, s, i))){ 
                if(n.left.v == null && n.left.left==null 
                   && n.left.mid == null && n.left.right == null)n.left = null;
            }
        }else{
            if((r=delete(n.right, s, i))){ 
                if(n.right.v == null && n.right.left == null 
                   && n.right.mid == null && n.right.right == null)n.right = null; 
            } 
        }
        return r;
    }
    
    public Iterable<String> keys(){
        Queue<String> al = new LinkedList<>();
        String string = "";
        findKeys(root, al, string);  
        return al;
    }
    
    private void findKeys(Node n, Queue<String> al, String s){
        if(n==null)return;
        if(n.v!=null){al.add(s+n.c);}
        findKeys(n.left, al, s);
        
        String s2 = s+n.c;
        findKeys(n.mid, al, s2);
        
        findKeys(n.right,al, s);
    }
    
    public Iterable<String> keysWithPrefix(String prefix){
        Queue<String> al = new LinkedList<>();
        String string = "";
        System.out.println("\n\nFinding keys with prefix \""+prefix+"\"\n\n");
        findKeysP(root, al, string, prefix);  
        return al;
    }
    
    private void findKeysP(Node n, Queue<String> al, String s, String p){
        if(n==null)return;
        System.out.println("Working with string \""+s+"\" with prefix \""+p+"\"");
        if(s.length()<=p.length() && s.length()!=0 && s.charAt(s.length()-1)!=p.charAt(s.length()-1)){
            System.out.println("Above string rejected");
            return;
        }
        System.out.println("Above string accepted");
        if(n.v!=null){

            if(s.length()<p.length()&&n.c==p.charAt(s.length()))al.add(s+n.c);
            else if(s.length()>p.length())al.add(s+n.c);

        }
        findKeysP(n.left, al, s, p);
        
        String s2 = s+n.c;
        findKeysP(n.mid, al, s2, p);
        
        findKeysP(n.right,al, s, p);
    }
    
    public String longestPrefixOf(String s){
        String string = "";
        System.out.println("\n\nFinding the longest prefix of \""+s+"\"\n\n"); 
        int l = longestPrefixOf(root, l=0, s);  
        return s.substring(0, l+1);
    }
    
    private int longestPrefixOf(Node n, int i, String p){ 
        if(n==null)return i-1;
        if(i>=p.length()){System.out.println("Node "+n.c+" rejected");return i-1; }
         
        int l,m=Integer.MIN_VALUE,r;
        l = longestPrefixOf(n.left, i, p);
        if(n.c==p.charAt(i)){System.out.println("Node "+n.c+" accepted"); m = longestPrefixOf(n.mid, i+1, p);}
        r = longestPrefixOf(n.right, i, p);
        return Math.max(l, Math.max(m, r));
    }
    
    public static void main(String[] args){
        TSTFunctions<Integer> tst = new TSTFunctions<>();
        String s = "she sells seashells by the sea the shells she sells are surely seashells";
        String a[] = s.split(" ");
        
        int i = 0;
        for(String ss:a)tst.add(ss, i++); 
        
        //All keys
        for(String ss:tst.keys())System.out.println(ss);
        
        //Keys with prefix
        for(String ss:tst.keysWithPrefix("sea")) System.out.println(ss); 
        for(String ss:tst.keysWithPrefix("sh")) System.out.println(ss);
        
        //Longest Prefix Of
        System.out.println(tst.longestPrefixOf("are"));
        System.out.println(tst.longestPrefixOf("seashel"));
        System.out.println(tst.longestPrefixOf("seaXshell"));
        System.out.println(tst.longestPrefixOf("seashells"));
        System.out.println(tst.longestPrefixOf("seashellsxx"));
    }
}

Output:

are
by
sea
seashells
sells
she
shells
surely
the


Finding keys with prefix "sea"


Working with string "" with prefix "sea"
Above string accepted
Working with string "" with prefix "sea"
Above string accepted
Working with string "" with prefix "sea"
Above string accepted
Working with string "a" with prefix "sea"
Above string rejected
Working with string "b" with prefix "sea"
Above string rejected
Working with string "s" with prefix "sea"
Above string accepted
Working with string "s" with prefix "sea"
Above string accepted
Working with string "se" with prefix "sea"
Above string accepted
Working with string "se" with prefix "sea"
Above string accepted
Working with string "sea" with prefix "sea"
Above string accepted
Working with string "seas" with prefix "sea"
Above string accepted
Working with string "seash" with prefix "sea"
Above string accepted
Working with string "seashe" with prefix "sea"
Above string accepted
Working with string "seashel" with prefix "sea"
Above string accepted
Working with string "seashell" with prefix "sea"
Above string accepted
Working with string "sel" with prefix "sea"
Above string rejected
Working with string "sh" with prefix "sea"
Above string rejected
Working with string "s" with prefix "sea"
Above string accepted
Working with string "su" with prefix "sea"
Above string rejected
Working with string "" with prefix "sea"
Above string accepted
Working with string "t" with prefix "sea"
Above string rejected
sea
seashells


Finding keys with prefix "sh"


Working with string "" with prefix "sh"
Above string accepted
Working with string "" with prefix "sh"
Above string accepted
Working with string "" with prefix "sh"
Above string accepted
Working with string "a" with prefix "sh"
Above string rejected
Working with string "b" with prefix "sh"
Above string rejected
Working with string "s" with prefix "sh"
Above string accepted
Working with string "s" with prefix "sh"
Above string accepted
Working with string "se" with prefix "sh"
Above string rejected
Working with string "sh" with prefix "sh"
Above string accepted
Working with string "she" with prefix "sh"
Above string accepted
Working with string "shel" with prefix "sh"
Above string accepted
Working with string "shell" with prefix "sh"
Above string accepted
Working with string "s" with prefix "sh"
Above string accepted
Working with string "su" with prefix "sh"
Above string rejected
Working with string "" with prefix "sh"
Above string accepted
Working with string "t" with prefix "sh"
Above string rejected
shells


Finding the longest prefix of "are"


Node a accepted
Node r accepted
Node e accepted
are


Finding the longest prefix of "seashel"


Node s accepted
Node e accepted
Node a accepted
Node s accepted
Node h accepted
Node e accepted
Node l accepted
Node l rejected
seashel


Finding the longest prefix of "seaXshell"


Node s accepted
Node e accepted
Node a accepted
sea


Finding the longest prefix of "seashells"


Node s accepted
Node e accepted
Node a accepted
Node s accepted
Node h accepted
Node e accepted
Node l accepted
Node l accepted
Node s accepted
seashells


Finding the longest prefix of "seashellsxx"


Node s accepted
Node e accepted
Node a accepted
Node s accepted
Node h accepted
Node e accepted
Node l accepted
Node l accepted
Node s accepted

seashells

Ternary Search Tries TST - Java Implementation

Ternary search tries are similar to R-way tries but more space efficient.

TST Performance:

Search hit         :   L+ln N
Search miss        :   ln N
Insert             :   L + ln N
Space (references) :   4 N + R^2

Source - Keys are strings, values are generic:

public class TST<T> {
    class Node{
        char c;
        T v;
        Node left, mid, right;
        
        Node(){}
        Node(char c){this.c = c;}
        Node(T v){this.v = v;}
        Node(char c, T v){this.c = c;this.v = v;}
    }
    
    Node root; 
    
    public void add(String s, T value){
       System.out.println("\nAdding ["+s+" : "+value+"]");
       root = add(root, s, 0, value);
    }
    
    private Node add(Node n, String s, int i, T value){ 
        System.out.println("Adding "+s.charAt(i));
        if(n==null){
            System.out.println("Creating new node for "+s.charAt(i));
            n = new Node(s.charAt(i));
            if(i==s.length()-1){n.v = value; return n;}
        }
        if(s.charAt(i)==n.c){
            if(i==s.length()-1){System.out.println("Overwriting ");n.v = value; return n;}
            System.out.println("Going down from node "+n.c);
            n.mid = add(n.mid, s, i+1, value);
        }
        else if(s.charAt(i)<n.c){
            System.out.println("Going left from node "+n.c);
            n.left = add(n.left, s, i, value);
        }
        else{
            System.out.println("Going right from node "+n.c);
            n.right = add(n.right, s, i, value);
        }
        return n;
    }
    
    public boolean findKey(String s){ 
        System.out.println("\nFinding key ["+s+"] root = "+root.c);
        return findKey(root, s, 0); 
    }
    
    private boolean findKey(Node n, String s, int i){  
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){

                System.out.println("Last node found: "+n.c+" Checking the presence of a value");
                if(n.v!=null){System.out.println(n.v); return true;} 
                else {
                    System.out.println("n.v was null n.v = "+n.v);
                    return false;
                }
            }
        }else if(i>s.length())return false; 
        if(s.charAt(i)==n.c){
            System.out.println("Going down from node "+n.c);
            return findKey(n.mid, s, i+1);
        }
        else if(s.charAt(i)<n.c){
            System.out.println("Going left from node "+n.c);
            return findKey(n.left, s, i);
        }
        else {
            System.out.println("Going right from node "+n.c);
            return findKey(n.right, s, i);
        }        
    }
    
    public void delete(String s){
        System.out.println("\n\nDeleting key "+s+":\n");
        delete(root, s, 0);
    }
    
    private boolean delete(Node n, String s, int i){
        if(n==null) return false;
        if(i==s.length()-1){
            if(n.c==s.charAt(i)){

                System.out.println("Last node found: "+n.c+" Checking the presence of a value");
                if(n.v!=null){System.out.println("Deleting "+n.c+" : "+n.v); n.v = null;return true;}
                else {
                    System.out.println("n.v was null n.v = "+n.v);
                    return false;
                }
            }
        }else if(i>s.length())return false; 
        
        boolean r;
        if(s.charAt(i)==n.c){
            System.out.println("Going down from node "+n.c);
            if((r=delete(n.mid, s, i+1))){ 
                if(n.mid.v == null && n.mid.left == null && n.mid.mid == null && n.mid.right == null){
                    System.out.println("Setting "+n.c+" node's mid to null");
                    n.mid = null;
                }
            }
        }
        else if(s.charAt(i)<n.c){
            System.out.println("Going left from node "+n.c);
            if((r=delete(n.left, s, i))){ 
                if(n.left.v == null && n.left.left==null && n.left.mid == null && n.left.right == null){
                    System.out.println("Setting "+n.c+" node's left to null");
                    n.left = null;
                }
            }
        }
        else{
            System.out.println("Going right from node "+n.c);
            
            if((r=delete(n.right, s, i))){ 
                if(n.right.v == null && n.right.left == null && n.right.mid == null && n.right.right == null){
                    System.out.println("Setting "+n.c+" node's right to null");
                    n.right = null;
                }
            } 
        }
        return r;
    }
    
    public static void main(String[] args){
        TST<Integer> tst = new TST<>();
        String s = "she sells seashells by the sea the shells she sells are surely seashells";
        String a[] = s.split(" ");
        
        int i = 0;
        for(String ss:a){
            tst.add(ss, i++);
        }
        
        tst.findKey("seashells");
        tst.findKey("seashell");
        tst.findKey("z");
        tst.delete("seashell");
        tst.delete("seashells");
        tst.findKey("seashells");     
        tst.findKey("sea");
    }
}

Output:

Adding [she : 0]
Adding s
Creating new node for s
Going down from node s
Adding h
Creating new node for h
Going down from node h
Adding e
Creating new node for e

Adding [sells : 1]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Creating new node for e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding l
Creating new node for l
Going down from node l
Adding s
Creating new node for s

Adding [seashells : 2]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding a
Going left from node l
Adding a
Creating new node for a
Going down from node a
Adding s
Creating new node for s
Going down from node s
Adding h
Creating new node for h
Going down from node h
Adding e
Creating new node for e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding l
Creating new node for l
Going down from node l
Adding s
Creating new node for s

Adding [by : 3]
Adding b
Going left from node s
Adding b
Creating new node for b
Going down from node b
Adding y
Creating new node for y

Adding [the : 4]
Adding t
Going right from node s
Adding t
Creating new node for t
Going down from node t
Adding h
Creating new node for h
Going down from node h
Adding e
Creating new node for e

Adding [sea : 5]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding a
Going left from node l
Adding a
Overwriting 

Adding [the : 6]
Adding t
Going right from node s
Adding t
Going down from node t
Adding h
Going down from node h
Adding e
Overwriting 

Adding [shells : 7]
Adding s
Going down from node s
Adding h
Going down from node h
Adding e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding l
Creating new node for l
Going down from node l
Adding s
Creating new node for s

Adding [she : 8]
Adding s
Going down from node s
Adding h
Going down from node h
Adding e
Overwriting 

Adding [sells : 9]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding l
Going down from node l
Adding l
Going down from node l
Adding s
Overwriting 

Adding [are : 10]
Adding a
Going left from node s
Adding a
Going left from node b
Adding a
Creating new node for a
Going down from node a
Adding r
Creating new node for r
Going down from node r
Adding e
Creating new node for e

Adding [surely : 11]
Adding s
Going down from node s
Adding u
Going right from node h
Adding u
Creating new node for u
Going down from node u
Adding r
Creating new node for r
Going down from node r
Adding e
Creating new node for e
Going down from node e
Adding l
Creating new node for l
Going down from node l
Adding y
Creating new node for y

Adding [seashells : 12]
Adding s
Going down from node s
Adding e
Going left from node h
Adding e
Going down from node e
Adding a
Going left from node l
Adding a
Going down from node a
Adding s
Going down from node s
Adding h
Going down from node h
Adding e
Going down from node e
Adding l
Going down from node l
Adding l
Going down from node l
Adding s
Overwriting 

Finding key [seashells] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Going down from node l
Last node found: s Checking the presence of a value
12

Finding key [seashell] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Last node found: l Checking the presence of a value
n.v was null n.v = null

Finding key [z] root = s
Going right from node s
Going right from node t


Deleting key seashell:

Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Last node found: l Checking the presence of a value
n.v was null n.v = null


Deleting key seashells:

Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a
Going down from node s
Going down from node h
Going down from node e
Going down from node l
Going down from node l
Last node found: s Checking the presence of a value
Deleting s : 12
Setting l node's mid to null
Setting l node's mid to null
Setting e node's mid to null
Setting h node's mid to null
Setting s node's mid to null
Setting a node's mid to null

Finding key [seashells] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Going down from node a

Finding key [sea] root = s
Going down from node s
Going left from node h
Going down from node e
Going left from node l
Last node found: a Checking the presence of a value
5