Updated April 1, 2023
Introduction to Trie Data Structure in Java
The following article provides an outline for Trie Data Structure in Java. Basically, data structure plays a very important part in computer programming and also, we must know when and why we use different types of data structure in computer programming. Normally trie is a discrete data structure, and this is not familiar, or we can say that this is not a widely used data structure but this used in the typical algorithm, a trie is also known as a digital tree; it also has another name that is radix or prefix.
Using a trie data structure, we search the element by prefixes in a well-structured tree with a key, and it is advantageous to store the strings. Moreover, we can perform the different operation trie data structure such as insertion, deletion and searching.
Syntax of Trie Data Structure in Java
Given below is the syntax mentioned:
public void insert_node(specified string of word){
TrieNode present = rootNode;
For (char i: word.toCharArray()){
Present = present.getChildren().computeIfAbsent(I, c->new TrieNode());
}
Present.setEndOfWord(true)
}Explanation:
By using the above syntax, we try to insert elements into the trie data structure; for that, we need to follow the following steps as follows:
- First, we need to set the present node as a root node for insertion operation.
- After that, we need to set the present character as the first character of the word.
- If a present node exists in the digital tree, then reference to the present character, and if a present node does not exist, we need to create the new node.
- Finally, we can use the Trie key for digital traversing.
Similarly, we can write syntax for delete and search operations.
How does Trie Data Structure work in Java?
Given below shows how trie data structure works in java:
Normally we can perform 3 different operations in a trie data structure as follows:
1. Insert Element Operation
We already explain how insertion operation works in java on the above point. The complexity of insertion operation is O (n), where n represents the size of the key.
2. Finding Element Operation
After insertion operation, we can perform the search or find operation on trie data structure by using the following algorithm as follows.
Code:
public void find_node(specified string of word){
TrieNode present = rootNode;
For (char j = 0; j < word.length(); j++){
char c = word.charAt(j);
TrieNode node = present.getChildren().get(c);
If (node = = null){
return false;
}
Present = node;
}
return present.isEndOfWord();
}Explanation:
Now follow the following steps for the search element in a trie data structure as follows:
- First, get the child node from the root.
- After we need to iterate each and every character in the string.
- Now check whether that specified character is present, or we can say it is part of the sub trie; if the specified character is not a part of sub trie, then return the false and exit.
- Repeat the second and third steps until there is no character present in the string.
- The complexity of insertion operation is O (n), where n represents the size of the key.
3. Delete Element Operation
Besides insertion operation and find the element; clearly, we likewise should have the option to delete operation, so we need to follow the following steps as follows.
- Check whether the specified element is as of now part of the trie.
- In the event that the element is found, eliminate it from the trie.
- The intricacy of this calculation is O(n), where n addresses the length of the key.
Example of Trie Data Structure in Java
Given below is the example of Trie Data Structure in Java:
Code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// created class to store node into the trie data structure
class trie_data
{
// Define the size of alphabet size
private static final int CHAR_AlPHA_SIZE = 26;
private boolean isLeaf;
private List<trie_data> child = null;
// Created Constructor of class
trie_data()
{
isLeaf = false;
child = new ArrayList<>(Collections.nCopies(CHAR_AlPHA_SIZE, null));
}
// function for insertion operation
public void trie_insert(String id)
{
System.out.println("We inserted new element into the data structure \"" + id + "\"");
// Staritng from the parent node that is root node
trie_data present = this;
for (char ch: id.toCharArray())
{
// if node is not exist then create new node in trie
if (present.child.get(ch - 'a') == null) {
present.child.set(ch - 'a', new trie_data());
}
// visit next node
present = present.child.get(ch - 'a');
}
// mark present as leaf node
present.isLeaf = true;
}
// search function to search element into trie data structure
// if key value is not present then it return the false
public boolean trie_search(String id)
{
System.out.print("We searched element\"" + id + "\" : ");
trie_data present = this;
for (char ch: id.toCharArray())
{
// visit next node
present = present.child.get(ch - 'a');
if (present == null) {
return false;
}
}
return present.isLeaf;
}
}
class Main
{
public static void main (String[] args)
{
// construct a new Trie node
trie_data head = new trie_data();
head.trie_insert("the");
head.trie_insert("they");
head.trie_insert("final");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // false
head.trie_insert("Sample");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // true
}
}Explanation:
- In the above example, we try to implement the trie data structure in java, here first we created a class to store the node into the trie data structure. Then, we defined the alphabet size by using CHAR_AlPHA_SIZE. Then, we created a constructor for the class.
- There is a function for insertion operation ‘trie_insert’ () as well as for searching elements from the trie data structure as shown in the above program. At the end of the program, we just call the insert and search function with different values that we need to insert and search in the trie data structure.
Output:
Conclusion
From the above article, we saw the basic syntax of Trie data structure, and we also saw different examples of Trie data structure. From this article, we saw how and when we use the Trie data structure in Java.
Recommended Articles
This is a guide to Trie Data Structure in Java. Here we discuss the introduction, how trie data structure works in Java? and an example. You may also have a look at the following articles to learn more –
