codebytes: 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:
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"); } }Read full article from codebytes: R-Way Tries Implementation - Java