Trie Data Structure in C++

A Trie, also known as a prefix tree, is a tree-like data structure used to store a dynamic set of strings. It is particularly useful for efficient retrieval of keys in a large dataset of strings. In this article, we will explore the Trie data structure, its operations, implementation in C++, and its advantages, disadvantages, and applications.

What is a Trie?

A Trie data structure is a tree-like data structure where each node represents a character of a string sequence. The root node represents an empty string, and each edge represents a character. The path from the root to a node represents a prefix of a string stored in the Trie. This structure allows for efficient insertion, deletion, and search operations.

For example, if we consider a Trie for storing strings with only lowercase characters then each node of the trie will consist of 26 children each representing the presence of letters from a-z. Following are some properties of the trie data structure:

• Each node will represent a single character of the string.
• The root node represents an empty string.
• Each path of the tree represents a word.
• Each node of the trie will have 26 pointers to represent the letters from a-z.
• A boolean flag is used to mark the end of a word in the path of a Trie.

Trie Representation in C++

To represent a node of a Trie in C++, we can declare a class TrieNode in which each node contains an array of pointers to its children and a boolean flag to indicate the end of a word.

class TrieNode {

 TrieNode* childrens[26];
 bool endofWord;
};

Here,

• childrens[]: is an array of pointers to represent the children of each trie node. To represent letters from a-z the size of the array is declared as 26 where children[0] represents a, children[1] represents b and so on.
• endofWord: is a flag variable that will denote the end of a word in a path of the trie. At any node if the value of endofWord is true it indicates the end of a word in the trie.

The following diagram represents how the words geek, geeks, code, coder and coding will be stored in a Trie:

Basic operations on Trie Data Structure

Following are some of the basic operations performed on a Trie data structure:

Here, n represents the length of the word and m represents the length of the prefix.

Insertion Implementation

Following is the algorithm for inserting a word in a trie:

• Initialize a temporary pointer to the root node of the trie.
• For each character in the word:
  • Find the index of the character.
  • If the character doesn't exists in the current node's children, create a new node for this character.
  • Move the pointer to the child node.
• Mark the last node's as the endofWord as true.

Search Implementation

Following is the algorithm for searching a word in a trie:

• Initialize a temporary pointer to the root node of the trie.
• For each character of the word:
  • Calculate the index of the character.
  • If the corresponding child node doesn't exists return false and return.
  • If the child node exists move the pointer to the child node.
• Return true if the endofWord of the last character is true otherwise return false.

Deletion Implementation

Following is the algorithm for deleting a word in a trie:

• Initialize a temporary pointer to the root node of the trie.
• For each character of the word to be deleted:
  • Calculate the index of the character.
  • If the corresponding child node doesn't; exists return as the word is not present in the trie.
  • If the child node exists move the pointer to the child node.
  • If the endofWord for the child node is true mark it false and return.

StartsWith Operation Implementation

Following is the algorithm to check if a prefix exits in a trie or not:

• Initialize a temporary pointer to the root node of the trie.
• For each character of the prefix:
  • Calculate the index of the character.
  • If the corresponding child node doesn't exists return false and return.
  • If the child node exists move the pointer to the child node.
• Return true if you have reached at the last character of the prefix.

C++ Program to Implement Trie Data Structure

The following program demonstrates the basic operations on a Trie: insertion, searching, and deletion.

// C++ Program to implement trie #include <iostream> #include <string> using namespace std; // class for a node of the trie class TrieNode { public:  bool endofWord;  TrieNode* children[26];  // Constructore to initialize a trie node  TrieNode()  {  endofWord = false;  for (int i = 0; i < 26; i++) {  children[i] = nullptr;  }  } }; // class for the Trie implementation class Trie { private:  TrieNode* root; public:  Trie() { root = new TrieNode(); }  // Function to insert a word into the trie  void insert(string word)  {  TrieNode* node = root;  for (char c : word) {  int index = c - 'a';  if (!node->children[index]) {  node->children[index] = new TrieNode();  }  node = node->children[index];  }  node->endofWord = true;  }  // Function to search a word in the trie  bool search(string word)  {  TrieNode* node = root;  for (char c : word) {  int index = c - 'a';  if (!node->children[index]) {  return false;  }  node = node->children[index];  }  return node->endofWord;  }  // Function to check if there is any word in the trie  // that starts with the given prefix  bool startsWith(string prefix)  {  TrieNode* node = root;  for (char c : prefix) {  int index = c - 'a';  if (!node->children[index]) {  return false;  }  node = node->children[index];  }  return true;  }  // Function to delete a word from the trie  void deleteWord(string word)  {  TrieNode* node = root;  for (char c : word) {  int index = c - 'a';  if (!node->children[index]) {  return;  }  node = node->children[index];  }  if (node->endofWord == true) {  node->endofWord = false;  }  }  // Function to print the trie  void print(TrieNode* node, string prefix) const  {  if (node->endofWord) {  cout << prefix << endl;  }  for (int i = 0; i < 26; i++) {  if (node->children[i]) {  print(node->children[i],  prefix + char('a' + i));  }  }  }  // Function to start printing from the root  void print() const { print(root, ""); } }; int main() {  // Create a Trie  Trie trie;  // Insert words into the trie  trie.insert("geek");  trie.insert("geeks");  trie.insert("code");  trie.insert("coder");  trie.insert("coding");  // Print the trie  cout << "Trie contents:" << endl;  trie.print();  // Search for words in the trie  cout << "\nSearch results:" << endl;  cout << "geek: " << trie.search("geek") << endl;  cout << "geeks: " << trie.search("geeks") << endl;  cout << "code: " << trie.search("code") << endl;  cout << "coder: " << trie.search("coder") << endl;  cout << "coding: " << trie.search("coding") << endl;  cout << "codex: " << trie.search("codex") << endl;  // Check if prefixes exist in the trie  cout << "\nPrefix results:" << endl;  cout << "ge: " << trie.startsWith("ge") << endl;  cout << "cod: " << trie.startsWith("cod") << endl;  cout << "coz: " << trie.startsWith("coz") << endl;  // Delete words from the trie  trie.deleteWord("coding");  trie.deleteWord("geek");  // Print the trie after deletions  cout << "\nTrie contents after deletions:" << endl;  trie.print();  // Search for words in the trie after deletions  cout << "\nSearch results after deletions:" << endl;  cout << "coding: " << trie.search("coding") << endl;  cout << "geek: " << trie.search("geek") << endl;  return 0; } 

Output

Trie contents:
code
coder
coding
geek
geeks

Search results:
geek: 1
geeks: 1
code: 1
coder: 1
coding: 1
codex: 0

Prefix results:
ge: 1
cod: 1
coz: 0

Trie contents after deletions:
code
coder
geeks

Search results after deletions:
coding: 0
geek: 0

Applications of Trie

Following are some of the common applications of the trie data structure:

• Tries are used to implement the auto complete feature in various search engines.
• Used to implement dictionaries as the allow efficient search for words.
• Used in computer networking to store the routing tables.
• Used by the search engines to index web pages for quick retrieval of pages containing specific keywords.
• Used in phone directory applications to allows users to search for the required contacts efficiently.

Advantages of Trie

• Tries provide efficient search operations with a time complexity of O(m), where m is the length of the key.
• Tries are ideal for prefix-based searches and autocomplete features.
• Tries can be more memory-efficient than hash tables for storing large datasets of strings.

Disadvantages of Trie

• Tries can consume a lot of memory, especially when storing a large number of short strings.
• Implementing a Trie can be more complex compared to other data structures like hash tables.

Related Articles:

You can also go through the following articles to improve your understanding about the trie data structure:

• Trie Data Structure | Insert and Search
• Auto-complete feature using Trie
• Trie Data Structure Tutorial
• Applications, Advantages and Disadvantages of Trie