What are Trie Trees?
Trie is an efficient information retrieval data structure. A Trie is a tree in which each node has many children. The value at each node consists of 2 things. 1) A character 2) A boolean to say whether this character represents the end of a word. Tries are also known as Prefix Trees.
Below is the visual representation of a Trie:
Visual representation of Trie
The root node is an empty node from which all other nodes branch out. The nodes shown in green mark the end of a word. The time complexity of searching a word in Trie is O(M), where M is the length of the word string we intend to search.
Tries can be extremely useful in searching for a word in a dictionary of words.
Let?s now see how we can build such a data structure.
First, let us create a class for the nodes of the Trie tree. I have created a class called TrieNode.java. The class TrieNode.java consists of 3 things, 1) a character to hold the current character at this node, 2) a map which holds all the children, 3) a boolean variable to tell us whether this node or character represents the end of a word.
public class TrieNode { private char c; private HashMap<Character, TrieNode> children = new HashMap<>(); private boolean isLeaf; public TrieNode() {} public TrieNode(char c){ this.c = c; } public HashMap<Character, TrieNode> getChildren() { return children; } public void setChildren(HashMap<Character, TrieNode> children) { this.children = children; } public boolean isLeaf() { return isLeaf; } public void setLeaf(boolean isLeaf) { this.isLeaf = isLeaf; }}
Next, let us create a class which is going to handle all the operations on the Trie nodes. I have created a class called Trie.java which handles 2 operations, 1) insert the characters of a word into the Trie, 2) search whether a word exists in our created Trie.
public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { HashMap<Character, TrieNode> children = root.getChildren(); for(int i = 0; i < word.length(); i++) { char c = word.charAt(i); TrieNode node; if(children.containsKey(c)) { node = children.get(c); } else { node = new TrieNode(c); children.put(c, node); } children = node.getChildren(); if(i == word.length() – 1) { node.setLeaf(true); } } } public boolean search(String word) { HashMap<Character, TrieNode> children = root.getChildren(); TrieNode node = null; for(int i = 0; i < word.length(); i++) { char c = word.charAt(i); if(children.containsKey(c)) { node = children.get(c); children = node.getChildren(); } else { node = null; break; } } if(node != null && node.isLeaf()) { return true; } else { return false; } }}
The insert method adds words into the Trie character by character. Note that for the words having common prefixes, the common characters are added only once.
The search method searches whether all the characters in a word are present in subsequent nodes of the tree in the same order. Also, for the node of the last character in the word, its isLeaf should be set.
For the entire code of the project, refer to my Github repo: https://github.com/avadhaniamogh/trie_tree_search
