Thursday, December 10, 2015

R-Way Tries Implementation - Java

R-Way tries are useful for operations on strings. Tries trade-off space for computational time.

Search hit : L
Search miss : log (base R) N
Insert : L
Space(references) : (R+1)N

N - Number of strings
R - Radix
L - Length of string

Source:

class Node{
        
        public char c;
        public Object v = null;
        public int n;
        public Node[] next;
        
        Node(char c, int R){
            this.c = c; 
            next = new Node[R]; 
        }
        Node(int R) {next = new Node[R];}
        
        public String toString(){return ""+c;}
}

public class Trie <T>{ 
    
    private final int R;
    private Node root; 
    
    public void add(String s, T t){   
        root.next[s.charAt(0)] = addHelper(root.next[s.charAt(0)], s, 0, t);
    }
    
    private Node addHelper(Node node, String s, int i, T value){   
        if(node==null){
            Node n = new Node(s.charAt(i), R);
            node = n; 
        } 
        if(i+1==s.length()){node.v = value; return node; }
        if(node.next[s.charAt(i+1)]==null)node.n++;
        node.next[s.charAt(i+1)] = addHelper(node.next[s.charAt(i+1)], s, i+1, value); 
        return node;   
    }
     
    public boolean delete(String s){ 
        boolean r = deleteHelper(root.next[s.charAt(0)], s, 0);
        if(r && (--root.next[s.charAt(0)].n)==0){
            root.next[s.charAt(0)]=null;
            return true;
        } else return false;
    }
    
    private boolean deleteHelper(Node node, String s, int i){ 
        if(i <s.length() && node==null){ 
            return false;
        }
        else if(i==s.length()-1){
            if(node.n==0) return true;
            else return false;
        }
        else{ 
            boolean t = deleteHelper(node.next[s.charAt(i+1)], s, i+1);
            
            if(t && (--node.next[s.charAt(i+1)].n)==0){
                node.next[s.charAt(i+1)] =null; 
                return true;
            }else return false;
        }
    }
    
    public boolean hasKey(String s){ 
        return hasKeyHelper(root.next[s.charAt(0)], s, 0);
    }
    
    private boolean hasKeyHelper(Node node, String s, int i){  
        if(i<s.length() && node==null)return false; 
        else if(i==s.length()-1){
            if(node.v!=null){
                System.out.println(node.v);
                return true;
            }else return false;
        }else return hasKeyHelper(node.next[s.charAt(i+1)], s, i+1);
    }
    
    Trie(int rway){
        R = rway;
        root = new Node(R);
    }
    
    public static void main(String[] args){ 
        Trie<Integer> t = new Trie<>(257); 
        t.add("courage", 1772);
        t.add("couragei", 177);
        t.add("Avichal", 994); 
        
        t.hasKey("courage");
        t.hasKey("Avi");
        t.hasKey("random");
        
        t.add("Avi", 99);
        t.hasKey("Avi");
         
    }
}

Output:

1772
99

No comments:

Post a Comment