The developers use the Trie data structure because they are particularly useful when users need to search for words or strings based on their prefixes. They can also predict the upcoming word or quickly suggest word completions based on the user’s input. Tries are also helpful in spell-checking, correction applications, and analyzing the frequency of words in a given text.
This article demonstrates a practical procedure to implement a trie data structure in Java.
How to Implement Trie Data Structure in Java?
The Trie data structure offers fast search and retrieval operations, and is memory-efficient, especially when dealing with a large number of words. They are also well-suited for scenarios where the input stream is dynamic and frequently changing.
Follow the below multiple code snippets in a sequence, to implement a trie data structure in Java:
static final int characterSize= 26;
static class TrieNode
boolean isEndOfWord;
{
TrieNode[] children = new TrieNode[characterSize];
TrieNode(){
isEndOfWord = false;
for (int j = 0; j < characterSize; j++)
children[j] = null;
}
};
static TrieNode rootNode;
In the above code block:
- First, a public class is created inside it the value of “26” is provided to the “characterSize” variable representing the alphabet characters. In this case, only lowercase letters from “a” to “z” are assumed.
- Below it, the “TrieNode” named static nested class is created. It contains an array of TrieNode references called “children” to store child nodes for each alphabet symbol.
- In addition, the “TrieNode” class constructor initializes the “isEndOfWord” boolean as false and uses a “for” loop to set all children nodes to null.
- Also, the variable named “rootNode” having a type of “TrieNode” is declared to represent the root node of the Trie.
Now, create a nested “insertion()” function that is getting “key” as an argument from the “main()” function. This function is used for inserting children into the TrieNode:
{
int nodeLevel;
int lengths = key.length();
int position;
TrieNode pcra = rootNode;
for (nodeLevel = 0; nodeLevel < lengths; nodeLevel++)
{
position = key.charAt(nodeLevel) - 'a';
if (pcra.children[position] == null)
pcra.children[position] = new TrieNode();
pcra = pcra.children[position];
}
pcra.isEndOfWord = true;
}
Description of the “insertion()” function:
- First, declare “nodeLevel”, “lengths” and “position” variables. Also, initialize the “lengths” variable with the length of the key string that comes via argument.
- Next, create an instance of TrieNode named “pcra”. And utilize the “for” loop to traverse through all nodes. Also, use the “if” statement and “position” variable in conjunction to fill each node using the “children” array.
Now create a function for “search”, it also takes “key” as an argument:
{
int nodeLevel;
int lengths = key.length();
int position;
TrieNode pCrawling = rootNode;
for (nodeLevel = 0; nodeLevel < lengths; nodeLevel++)
{
position = key.charAt(nodeLevel) - 'a';
if (pCrawling.children[position] == null)
return false;
pCrawling = pCrawling.children[position];
}
return (pCrawling.isEndOfWord);
}
Description of the “search” function:
- First, create the “nodeLevel”, “lengths” and “position” variables of type “int”.
- Next, declare an instance of “TrieNode” named “pCrawling”. And utilize the “for” loop to traverse through all node’s positions of the Trie.
- Inside it, utilize the loop in conjunction with the conditional “if” statement to take a string ‘key’ as input and search for it in the Trie.
- If the “Key” is found the statement returns true and vice versa.
Now, let us handle the “main()” method from where the compilation phase starts:
{
String keys[] = {"scarlet", "witch", "jackson", "harry", "john", "oddinson", "flash", "mendus", "shawn"};
String Status[] = {"Not available in trie", "available in trie"};
rootNode = new TrieNode();
int j;
for (j = 0; j < keys.length; j++)
{
insertion(keys[j]);
}
if(search("scarlet") == true)
System.out.println("Provided value 'scarlet' is----- " + Status[1]);
else System.out.println("Provided value 'scarlet' is----- " + Status[0]);
if(search("shawn") == true)
System.out.println("Provided value 'shawn' is----- " + Status[1]);
else System.out.println("Provided value 'shawn' is----- " + Status[0]);
if(search("mendus") == true)
System.out.println("Provided value 'mendus' is----- " + Status[1]);
else System.out.println("Provided value 'mendus' is----- " + Status[0]);
if(search("brook") == true)
System.out.println("Provided value 'brook' is----- " + Status[1]);
else System.out.println("Provided value 'brook' is----- " + Status[0]);
}
}
Description of “main()” method:
- First, declares a String type array named “keys[]” that stores the data that will be inserted on each node.
- Along with it, initialize another array named “Status[]” that contains two messages that appear according to the availability of a specific node value.
- Next, create a new instance of “TrieNode” and assign it to the root variable, representing the root node of the Trie.
- Then, the “for” loop Iterates over each key in the keys array and inserts them into the Trie using the “insertion()” method.
- After that, utilize multiple “if/else” statements that search for the word passed inside the search method parenthesis in the Trie. And prints a corresponding message from the “Status[]” array indicating whether it is available or not.
After executing the above code snippets, the result appears like this:
The snapshot shows that data has been inserted in the tire and function also illustrating the availability of data on the trie.
Conclusion
Trie data structure is implemented by first creating a trie structure and then inserting values on each node by traversing through each level using a “for” loop. It offers efficient string searching, prefix-based operations, and memory efficiency, making it valuable in applications like autocomplete, spell checking, text prediction, and various data processing tasks. This article has explained the procedure to implement a trie data structure.
