In this article, we will discuss the trie data structure in C++ with its properties, operations, and examples.
Trie data structure is a type of multi-way tree that is used for storing different strings. Each string consists of characters that are stored in a tree-like structure , i.e., Trie data structure . It is also called a radix tree or prefix tree , or digital tree . Basically, the word " trie " comes from the word "re trie val", which means retrieving or getting back something. It is used for various tasks such as s pell-checking, searching words, auto-completion , etc.
Properties of Trie data structure:
There are various properties of the trie data structure . Some main properties of the trie data structure are as follows:
- Trie data structure is the form of a tree structure where each node represents a single character of a string, and the path covered from root to node represents a specific string .
- The trie data structure starts from the root node , which is always empty and represents a null character . From the root node, various other branches emerge that hold other characters of a string.
- The end of a string in a trie data structure is called a leaf node . Each leaf node may contain extra information.
It can store and share a common initial part of a string which refers to the shared prefix . Sharing a common prefix makes it easier to search a set of strings efficiently.
Operations in a Trie data structure:
There are three operations that can be accomplished in a trie data structure:
- Insert operation:
This operation is used to add a new node , i.e., a new string , into the Trie .
- Search operation:
This operation is used to find a specific string and check if it exists in the Trie data structure .
- Delete operation:
This operation is used to remove a string that is present in the Trie data structure .
Example:
Let's take an example to implement trie data structures in C++ to perform insert, search, and delete operations.
Code:
#include <iostream>
using namespace std;
//Describing the size of the character.
#define CHAR_SIZE 128
//Here is a class that can be used to store a Trie node.
class Trie
{
public:
bool isLeaf;
Trie* character[CHAR_SIZE];
Trie()
{
this->isLeaf = false;
for (int k = 0; k< CHAR_SIZE; k++) {
this->character[k] = nullptr;
}
}
void insert(string);
bool search(string);
bool haveChildren(Trie const*);
bool deletion(Trie*&, string);
};
//Here is an iterative function for inserting a key in a Trie.
void Trie::insert(string key)
{
//Beginning from the root node.
Trie* curr = this;
for (int k = 0; k< key.length(); k++)
{
//If the path does not exist, a new node will be created.
if (curr->character[key[k]] == nullptr) {
curr->character[key[k]] = new Trie();
}
//Moving to the next node.
curr = curr->character[key[k]];
}
//Current node is marked as a leaf.
curr->isLeaf = true;
}
bool Trie::search(string key)
{
//If the Trie is empty, then return false.
if (this == nullptr) {
return false;
}
Trie* curr = this;
for (int k = 0; k< key.length(); k++)
{
curr = curr->character[key[k]];
if (curr == nullptr) {
return false;
}
}
return curr->isLeaf;
}
//Determines whether or not a specified node has any child nodes.
bool Trie::haveChildren(Trie const* curr)
{
for (int k = 0; k< CHAR_SIZE; k++)
{
if (curr->character[k]) {
return true; //A child has beenfound.
}
}
return false;
}
//Here is a recursive function that can be used to delete a key from a Trie.
bool Trie::deletion(Trie*& curr, string key)
{
//If the Trie is empty, then return false.
if (curr == nullptr) {
return false;
}
if (key.length())
{
if (curr != nullptr &&
curr->character[key[0]] != nullptr &&
deletion(curr->character[key[0]], key.substr(1)) &&
curr->isLeaf == false)
{
if (!haveChildren(curr))
{
delete curr;
curr = nullptr;
return true;
}
else {
return false;
}
}
}
//If the end of the key has been reached.
if (key.length() == 0 && curr->isLeaf)
{
if (!haveChildren(curr))
{
//Delete the current node.
delete curr;
curr = nullptr;
//Delete the parent nodes that are not at the leaf level.
return true;
}
else {
curr->isLeaf = false;
return false;
}
}
return false;
}
//Trie data structure C++ implementation
int main()
{
Trie* head = new Trie();
head->insert("java");
cout << head->search("java") << " "; //Returns 1 (If found)
head->insert("javacpptutorial");
cout << head->search("javacpptutorial") << " "; //Returns1
cout << head->search("javaa") << " "; //Returns0 (If not found)
head->insert("javac");
cout << head->search("javac") << " "; //Returns1
head->insert("j");
cout << head->search("j"); //Returns1
cout << endl;
head->deletion(head, "java");
cout << head->search("java") << " "; //Returns0
cout << head->search("javacpptutorial") << " "; //Returns1
cout << head->search("javac"); //Returns1
cout << endl;
head->deletion(head, "j");
cout << head->search("j") << " "; //Returns0
cout << head->search("javac") << " "; //Returns1
cout << head->search("javacpptutorial"); //Returns1
cout << endl;
head->deletion(head, "javacpptutorial");
cout << head->search("javacpptutorial") << " "; //Returns0
cout << head->search("javac") << " "; //Returns1
head->deletion(head, "javac");
cout << head->search("javac"); //Returns0
cout << endl;
if (head == nullptr) {
cout << "Empty!!\n"; //Trie is empty now
}
cout << head->search("javac"); //Returns0
return 0;
}
Output:
Explanation of the above C++ program:
- Firstly, C++ libraries are included in the program.
- We have assumed a Marco " CHAR_SIZE ", which has 128 characters .
- The class called "Trie" is created, which has four member functions: insert, search, haveChildren, and deletion .
- The " insert " function is used to add a string to a Trie .
- The "search" function is used to search for a string in the Trie and returns true if the string is discovered.
- The " haveChildren " function checks for non-zero children in a given Trie node .
- The " delete " function is a recursive function that delete a string from the Trie .
- Various strings, which are " java ", " javacpptutorial ", " javac ", and " j " are inserted using the " insert "
- The presence of various strings is checked using the " search " When the string " java " is searched, it returns true . Similarly, when the string " javacpptutorial " is searched, it returns true . When the string " javaa " is searched, it returns false because this string is not present in the Trie . When the string " javac " is searched, it returns true , and when the string " j " is searched, it returns true .
- After that, the strings, which are " java ", " javacpptutorial ", " javac " and " j " are deleted using the " deletion "
- After the deletion operation , the " search " method is called again to verify that the strings have been successfully deleted from the Trie .
- If the search operation is successful, it returns 1 when the string is found and returns 0 when the string is not found .
- The final output will show that the Trie is empty. It prints "Empty!!" and returns O .
Conclusion:
In this article, we have understood the Trie data structure , a tree-like structure that stores a collection of strings. It has various applications like word search, spell-check, auto-completion , etc. We have understood the various operations of the Trie data structure, which performs insert, search, and delete operations.