Updated April 7, 2023
Definition of Trie Data Structure C++
Trie Data Structure in C++ is defined as a tree-based implementation of a type of data structure that enables efficient retrieval of a key from a pool of large datasets of strings. The search complexities in a trie based data structure implementation can be narrowed down to the most optimal length i.e. key length comparing to the cases of a binary search tree where even a well-balanced binary tree has a time complexity proportional to M * log (N) where M is the maximum string length and N represents the number of keys in a binary search tree. Obviously, the efficiency comes at the cost of Trie storage requirements. In this article, we will look at the implementation of trie data structure in C++ and specifically understand the working of trie data structure.
Syntax
The idea of having a trie data structure started gaining popularity when it proved to be an efficient algorithm in terms of retrieving a key from a pool of datasets large enough to make the search complicated. The search operation in a trie data structure can be managed to have a search complexity as optimal as just the “key length”. Here in this section we will look at the syntax perspective of the trie implementation in C++ and understand the prerequisites from a syntax perspective, so that while having hands-on experience of trie data structure implementation in C++ and also understanding the working of trie, knowing the syntax will help map the larger picture with a code touch!
Creating a structure:
struct name_of_structure{
member_number 1;
.
.
.
member_number N;
};Declaring a function in C++:
<return type> <function name>(<parameters separated by comma and precedes with the data type)
{
//Write the code here!
}In case of return type as void, there is no need for a return statement but if it is anything apart from the void, we would need to mention the variable that function has to return.
For loop in C++:
for (int i = <start index>; i < <max value it can attain>; i++)
{
//Perform the steps which needs to run within for loop.
}Declaring pointer in C++:
<data type of pointer> *<pointer variable’s name>;How Trie data structure works in C++?
By now we do understand that trie data structure enables efficient search algorithm and hence mainly used for storing characters or alphabets of a word because of lexicographical interpretation. The structure is such that, the words or strings are easily retrievable by the algorithm once it traverses down a branch path of the tree structure. Now, coming to the main part and that is what is the working of trie data structure.
The trie consists of an empty root node, that contains the references of other nodes in the tree. These references are of that of its children. Now at the very first insert of words, each of the characters in the world will correspondingly represent a chronological sequence of alphabets in the word as branches with mentioning the last alphabet as the end node. Now, as and when the next words come in, it tries to find the lexicographical similarity with already existing words in the branches and drills down in the branch till a point where the sequence of the word is the same and then split for the alphabets when it starts differentiating. For example, let’s say the first word is “educba” and the next word one would want to enter is education, then the drill down in the tree will be same till edu and then one branch having the rest “cba” and the other having “cation” along with the condition that the last character will have flag mentioning that it is the end of the word.
Now in order to find a word in the tree, each of the characters in the search word is passed and if the word is found within the chronological traversal of the word and also the last character mentioning itself as a flag equal to the end of a word, we return that the word has been found, otherwise return that the word is not found. For example, if we have 2 words, “educba” and “education” in the array and we want to find 3 words namely: “trie”, “edu” and “educba”. For the first one, we start with the letter “t” and see that there is no node where we would see “t” as the first node of the tree and hence return that the word is not found. Now for “edu” we start the tree traversal and land up at the word “u” and see that it is not flagged as the end of the word and hence return that the word is not found. Finally, in the word “educba” we start the traversal and end up at the word “a” which also signifies the end of the word flag and hence return that the word is found.
We hereby see that the time complexity is just the length of the string, but as and when the number of words increases, the space complexity increases as well! in the next section we will look at the hands-on experience of trie data structure.
Examples
Let us discuss examples of Trie Data Structure C++.
Example #1
Implementation of trie data structure in C++
Code:
#include <bits/stdc++.h>
using namespace std;
const int NUM_OF_ALPHABETS = 26;
// Construction the Trie node structure
struct TrieNodeDS
{
struct TrieNodeDS *childNode[NUM_OF_ALPHABETS];
// nodeEnd is true if the node represents
// the ending of a word
bool nodeEnd;
};
// New NULL Trie node is returned
struct TrieNodeDS *getNode(void)
{
struct TrieNodeDS *nodePointer = new TrieNodeDS;
nodePointer->nodeEnd = false;
for (int i = 0; i < NUM_OF_ALPHABETS; i++)
nodePointer->childNode[i] = NULL;
return nodePointer;
}
//Insert Algorithm in Trie
void insertFunc(struct TrieNodeDS *headRoot, string searchKey)
{
struct TrieNodeDS *crawlPointer = headRoot;
for (int i = 0; i < searchKey.length(); i++)
{
int head = searchKey[i] - 'a';
if (!crawlPointer->childNode[head])
crawlPointer->childNode[head] = getNode();
crawlPointer = crawlPointer->childNode[head];
}
// End of node is marked as true; to point that the search will end here
crawlPointer->nodeEnd = true;
}
//Search Algorithm in Trie
bool searchFunc(struct TrieNodeDS * headRoot, string searchKey)
{
struct TrieNodeDS *crawlPointer = headRoot;
for (int i = 0; i < searchKey.length(); i++)
{
int head = searchKey[i] - 'a';
if (!crawlPointer->childNode[head])
return false;
crawlPointer = crawlPointer->childNode[head];
}
return (crawlPointer != NULL && crawlPointer->nodeEnd);
}
// Main Function for execution
int main()
{
// we will use only lowercase characters to keep consistency
string arrayWords[] = {"educba", "provides", "best",
"online", "education", "proven",
"by", "quality" };
int n = sizeof(arrayWords)/sizeof(arrayWords[0]);
struct TrieNodeDS * headRoot = getNode();
// Construct trie
for (int i = 0; i < n; i++)
insertFunc(headRoot, arrayWords[i]);
cout<< "---------List of words:-----------\n";
for (int i = 0; i < n; i++)
cout<< arrayWords[i] << "\n";
// Search for different words
cout<< "---------Search starts:-----------\n";
cout<< "Since 'edu' is not present as a word, but only present by sub-characters and 'u' in 'edu' doesn't represent end of node, the output will be No\n";
searchFunc(headRoot, "edu")? cout << "edu Found: Yes\n" :
cout << "edu Found: No\n";
cout<< "Since 'education' is present as a word, 'n' in 'education' represents the end of node, the output will be Yes \n";
searchFunc(headRoot, "education")? cout << "education Found: Yes\n" :
cout << "education Found: No\n";
return 0;
}Output:
Conclusion
To conclude, in this article we looked at the working of trie data structure in C++. Though we learned about the tree traversal for words, we can also store numbers as “strings of bits” in the same way though it is not the preferred way of storing numbers. It is left as an exercise for readers to try out!
Recommended Articles
This is a guide to Trie Data Structure C++. Here we discuss Definition, syntax, How Trie data structure works in C++? examples with code implementation. You may also have a look at the following articles to learn more –
