Summary: Trie Data Structure

Implement a Trie Data Structure, and search() & insert() function:

we need to implement both Class Trie and Class TrieNode

Class Trie:

 1 import java.util.ArrayList;
 2 import java.util.List;
 3 
 4 public class Trie
 5 {
 6    private TrieNode root;
 7    
 8    /**
 9     * Constructor
10     */
11    public Trie()
12    {
13       root = new TrieNode();
14    }
15    
16    /**
17     * Adds a word to the Trie
18     * @param word
19     */
20    public void addWord(String word)
21    {
22       root.addWord(word.toLowerCase());
23    }
24    
25    /**
26     * Get the words in the Trie with the given
27     * prefix
28     * @param prefix
29     * @return a List containing String objects containing the words in
30     *         the Trie with the given prefix.
31     */
32    public List getWords(String prefix)
33    {
34       //Find the node which represents the last letter of the prefix
35       TrieNode lastNode = root;
36       for (int i=0; i<prefix.length(); i++)
37       {
38       lastNode = lastNode.getNode(prefix.charAt(i));
39       
40       //If no node matches, then no words exist, return empty list
41       if (lastNode == null) return new ArrayList();      
42       }
43       
44       //Return the words which eminate from the last node
45       return lastNode.getWords();
46    }
47 }

Class TrieNode:

  1 import java.util.ArrayList;
  2 import java.util.List;
  3 
  4 public class TrieNode
  5 {
  6    private TrieNode parent;
  7    private TrieNode[] children;
  8    private boolean isLeaf;     //Quick way to check if any children exist
  9    private boolean isWord;     //Does this node represent the last character of a word
 10    private char character;     //The character this node represents
 11 
 12    /**
 13     * Constructor for top level root node.
 14     */
 15    public TrieNode()
 16    {
 17       children = new TrieNode[26];
 18       isLeaf = true;
 19       isWord = false;
 20    }
 21 
 22    /**
 23     * Constructor for child node.
 24     */
 25    public TrieNode(char character)
 26    {
 27       this();
 28       this.character = character;
 29    }
 30    
 31    /**
 32     * Adds a word to this node. This method is called recursively and
 33     * adds child nodes for each successive letter in the word, therefore
 34     * recursive calls will be made with partial words.
 35     * @param word the word to add
 36     */
 37    protected void addWord(String word)
 38    {
 39       isLeaf = false;
 40       int charPos = word.charAt(0) - 'a';
 41       
 42       if (children[charPos] == null)
 43       {
 44       children[charPos] = new TrieNode(word.charAt(0));
 45       children[charPos].parent = this;
 46       }
 47       
 48       if (word.length() > 1)
 49       {
 50       children[charPos].addWord(word.substring(1));
 51       }
 52       else
 53       {
 54       children[charPos].isWord = true;
 55       }
 56    }
 57    
 58    /**
 59     * Returns the child TrieNode representing the given char,
 60     * or null if no node exists.
 61     * @param c
 62     * @return
 63     */
 64    protected TrieNode getNode(char c)
 65    {
 66       return children[c - 'a'];
 67    }
 68    
 69    /**
 70     * Returns a List of String objects which are lower in the
 71     * hierarchy that this node.
 72     * @return
 73     */
 74    protected List getWords()
 75    {
 76       //Create a list to return
 77       List list = new ArrayList();
 78       
 79       //If this node represents a word, add it
 80       if (isWord)
 81       {
 82       list.add(toString());
 83       }
 84       
 85       //If any children
 86       if (!isLeaf)
 87       {
 88       //Add any words belonging to any children
 89       for (int i=0; i<children.length; i++)
 90       {
 91          if (children[i] != null)
 92          {
 93             list.addAll(children.getWords());
 94 
 95      }
 96 
 97      }
 98 
 99 }
100 
101 return list; 
102 
103 }
104 
105 
106 
107 /**
108 
109 * Gets the String that this node represents.
110 
111 * For example, if this node represents the character t, whose parent
112 
113 * represents the charater a, whose parent represents the character
114 
115 * c, then the String would be "cat".
116 
117 * @return
118 
119 */
120 
121 public String toString()
122 
123 {
124 
125 if (parent == null)
126 
127 {
128 
129      return "";
130 
131 }
132 
133 else
134 
135 {
136 
137      return parent.toString() + new String(new char[] {character});
138 
139 }
140 
141 } 
142 
143 }