## 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