Java Implementation of Trie Data Structure
Trie is a tree-based data structure used for efficient retrieval of a key in a huge word set. In this post, we will implement the Trie data structure in Java.
In the previous post, we discussed a Trie data structure in detail and covered its C implementation. In this post, the Trie data structure’s Java implementation is discussed, which is way cleaner than the C implementation.
Following is the Java implementation of the Trie data structure, which supports insertion and search operations. The implementation currently supports only lowercase English characters (a – z), but we can easily extend the solution to support any set of characters.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
import java.util.ArrayList; import java.util.Collections; import java.util.List; // A class to store a Trie node class Trie { // Define the alphabet size (26 characters for `a – z`) private static final int CHAR_SIZE = 26; private boolean isLeaf; private List<Trie> children = null; // Constructor Trie() { isLeaf = false; children = new ArrayList<>(Collections.nCopies(CHAR_SIZE, null)); } // Iterative function to insert a string into a Trie public void insert(String key) { System.out.println("Inserting \"" + key + "\""); // start from the root node Trie curr = this; // do for each character of the key for (char c: key.toCharArray()) { // create a new Trie node if the path does not exist if (curr.children.get(c - 'a') == null) { curr.children.set(c - 'a', new Trie()); } // go to the next node curr = curr.children.get(c - 'a'); } // mark the current node as a leaf curr.isLeaf = true; } // Iterative function to search a key in a Trie. It returns true // if the key is found in the Trie; otherwise, it returns false public boolean search(String key) { System.out.print("Searching \"" + key + "\" : "); Trie curr = this; // do for each character of the key for (char c: key.toCharArray()) { // go to the next node curr = curr.children.get(c - 'a'); // if the string is invalid (reached end of a path in the Trie) if (curr == null) { return false; } } // return true if the current node is a leaf node and the // end of the string is reached return curr.isLeaf; } } class Main { public static void main (String[] args) { // construct a new Trie node Trie head = new Trie(); head.insert("techie"); head.insert("techi"); head.insert("tech"); System.out.println(head.search("tech")); // true System.out.println(head.search("techi")); // true System.out.println(head.search("techie")); // true System.out.println(head.search("techiedelight")); // false head.insert("techiedelight"); System.out.println(head.search("tech")); // true System.out.println(head.search("techi")); // true System.out.println(head.search("techie")); // true System.out.println(head.search("techiedelight")); // true } } |
The space complexity of a Trie data structure is O(N × M × C), where N is the total number of strings, M is the maximum length of the string, and C is the alphabet’s size.
The storage problem can be alleviated if we only allocate memory for alphabets in use and don’t waste space storing null pointers. Following is a memory-efficient implementation of Trie data structure in Java, which uses HashMap to store a node’s children:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
import java.util.HashMap; import java.util.Map; // A class to store a Trie node class Trie { private boolean isLeaf; private Map<Character, Trie> children; // Constructor Trie() { isLeaf = false; children = new HashMap<>(); } // Iterative function to insert a string into a Trie public void insert(String key) { System.out.println("Inserting \"" + key + "\""); // start from the root node Trie curr = this; // do for each character of the key for (char c: key.toCharArray()) { // create a new node if the path doesn't exist curr.children.putIfAbsent(c, new Trie()); // go to the next node curr = curr.children.get(c); } // mark the current node as a leaf curr.isLeaf = true; } // Iterative function to search a key in a Trie. It returns true // if the key is found in the Trie; otherwise, it returns false public boolean search(String key) { System.out.print("Searching \"" + key + "\" : "); Trie curr = this; // do for each character of the key for (char c: key.toCharArray()) { // go to the next node curr = curr.children.get(c); // if the string is invalid (reached end of a path in the Trie) if (curr == null) { return false; } } // return true if the current node is a leaf node and the // end of the string is reached return curr.isLeaf; } } class Main { public static void main (String[] args) { // construct a new Trie node Trie head = new Trie(); head.insert("techie"); head.insert("techi"); head.insert("tech"); System.out.println(head.search("tech")); // true System.out.println(head.search("techi")); // true System.out.println(head.search("techie")); // true System.out.println(head.search("techiedelight")); // false head.insert("techiedelight"); System.out.println(head.search("tech")); // true System.out.println(head.search("techi")); // true System.out.println(head.search("techie")); // true System.out.println(head.search("techiedelight")); // true } } |
Also see:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)