Trie in Java

Trie is a good datastucture, details can be found here - http://en.wikipedia.org/wiki/Trie . I came across Trie while performing "Prefix" based searching. Have you ever Wondered what Data Structure is used behind the Mobile SMSes ? When we type SMS, it finishes the words or proposes what could be the end of the word. They are usually done by Trie or data structures like Trie.
Trie consumes less space so they are hot favourite data structures on PDAs or devices with less memory. Searching of a string in Trie takes around O(m) where m = length of the key. Compare it with Binary Tree which is O(logn) where n = number of elements in the tree. For a dictionary, this n could be real large.

Here is a simple implimentation of the Trie..
One class is called Node class which holds the Key and the value.

1. public class Node {




3. private char key;


4. private String value;


5. private List children;


6. private boolean isTerminal;


7. public boolean isTerminal() {


8. return isTerminal;


9. }


10. public void setTerminal(boolean isTerminal) {


11. this.isTerminal = isTerminal;


12. }


13. public Node(char key,String value)


14. {


15. this(key,value,new ArrayList());


16. }


17. public Node(char key, String value, List children) {


18. super();


19. this.key = key;


20. this.value = value;


21. this.children = children;


22. }




24. public char getKey() {


25. return key;


26. }


27. public void setKey(char key) {


28. this.key = key;


29. }


30. public String getValue() {


31. return value;


32. }


33. public void setValue(String value) {


34. this.value = value;


35. }


36. public List getChildren() {


37. return children;


38. }


39. public void setChildren(List children) {


40. this.children = children;


41. }




43. public void addChildren(Node child)


44. {


45. this.children.add(child);


46. }

}

And the Main Trie class which builds the tree and finds any key...

package com.ds.trie;

1. import java.io.BufferedReader;


2. import java.io.File;


3. import java.io.FileNotFoundException;


4. import java.io.FileReader;


5. import java.io.IOException;


6. import java.util.ArrayList;


7. import java.util.LinkedList;


8. import java.util.List;


9. import java.util.Queue;




11. public class Trie {




13. private Node root;


14. private File fname;




16. public Trie (String filename)


17. {


18. this.root = new Node('r',"root");


19. this.fname = new File(filename);


20. }




22. public void buildTrie()


23. {


24. try {




26. if (!fname.isFile())


27. throw new FileNotFoundException("");


28. BufferedReader f = new BufferedReader(new FileReader(fname));


29. String key;


30. try {


31. while ((key = f.readLine()) != null)


32. {


33. // making value = full name only = key


34. build(key,root,key);


35. }


36. } catch (IOException e) {


37. // TODO Auto-generated catch block


38. e.printStackTrace();


39. }


40. } catch (FileNotFoundException e) {


41. // TODO Auto-generated catch block


42. e.printStackTrace();


43. }


44. }




46. // key = shamik


47. private void build(String key,Node root,String value) {


48. // TODO Auto-generated method stub


49. char c = key.charAt(0); // c = s


50. String tail = null;


51. if (key.length() > 1)


52. tail = key.substring(1); // hamik


53. Node resultNode = findKeyinChildren(root,c); // find 's' in the children


54. if (resultNode == null)


55. {


56. // this is a new key


57. Node newNode = new Node(c,value);


58. if (tail == null)


59. newNode.setTerminal(true);


60. else


61. newNode.setTerminal(false);




63. root.addChildren(newNode);


64. if (tail == null)


65. {


66. return;


67. }


68. else


69. build(tail,newNode,value);


70. }


71. else // got the key - s


72. {


73. if (tail == null)


74. return;


75. build (tail,resultNode,value);


76. }


77. }




79. private Node findKeyinChildren(Node root, char c) {


80. // TODO Auto-generated method stub


81. List list = root.getChildren();


82. if (list == null || list.size() == 0)


83. return null;


84. for (int i=0; i < list.size(); i++)


85. {


86. Node oneNode = list.get(i);


87. if (oneNode.getKey() == c)


88. return oneNode;


89. }


90. return null;


91. }




93. public List findKey(String key)


94. {




96. String value = null;


97. List values = new ArrayList();




99. Node resultNode = findinTrie(key,root);




101. if (resultNode == null)


102. {


103. value = "Not found";


104. values.add(value);




106. }


107. else


108. {




110. printTree(resultNode,values);




112. }


113. return values;




115. }




117. private void printTree(Node resultNode,List values) {


118. // TODO Auto-generated method stub


119. List list = resultNode.getChildren();




121. if (resultNode.isTerminal())


122. values.add(resultNode.getValue());




124. if (list.size() == 0)


125. {




127. return;




129. }


130. else


131. {


132. for (int i=0; i<list.size();i++)


133. {


134. Node oneNode = list.get(i);


135. printTree(oneNode,values);


136. }


137. }


138. }




140. private Node findinTrie(String key, Node root) {


141. // TODO Auto-generated method stub


142. // Implementing the Breath First Traversal


143. char first = key.charAt(0);


144. String tail = null;


145. if (key.length() > 1)


146. tail = key.substring(1);




148. Node resultNode = this.findKeyinChildren(root, first);


149. if (resultNode == null)


150. {


151. return null;


152. }


153. else


154. {


155. if (tail == null)


156. return resultNode;


157. else


158. resultNode = findinTrie(tail,resultNode );


159. }




161. return resultNode;


162. }




164. public static void main(String[] args)


165. {


166. if (args.length <= 0)


167. {


168. System.out.println("Usage : Trie ");


169. System.exit(1);


170. }


171. Trie trie = new Trie("C:\\test\\dictionary");


172. trie.buildTrie();


173. System.out.println("Going to look for " + args[0]);


174. List vals = trie.findKey(args[0]);


175. for (int i=0; i<vals.size(); i++)


176. {


177. System.out.println("possible value = " + vals.get(i));


178. }




180. }




182. }