Trie Implementation

November 6, 2021

Trie Implementation  in C++

Trie also called suffix trees are important advanced data structures that allows us to search strings in time efficient manner. They are also very efficient to store strings in terms of memory. Tries have many cool applications like auto complete feature in cell phones, searching text, pattern matching etc. Below is a Trie Implementation in C++.

trieIntroImage

Why we need Trie?

We will understand implementation of trie using a problem. Suppose we have to make q queries on a text of length n. In each query we are given a string (pattern) of length m and we need to find whether the given string exists in the text or not.

The basic or naive approach to above problem is to try to match the pattern at each character in the text. The worst case time complexity of matching a string will be O(m*n). For q queries the time complexity will be O(q*n*m).

Tries allow us to perform above operation in O(m) for a single string. Therefore the total time complexity for q queries will be O(q*m). 

Trie Implementation in C++

InsertOperation

Trie Implementation in C++ Algorithm (Insertion):

  • Create a class or a structure for the trie node that can point to child nodes. Here we will be using a hash map for marking child nodes.
  • Add all suffixes of the given text into trie one by one.
  • While adding a suffix to the trie we will check if current node already has a child node for the current character. If node already present we simple move to the child node other wise if node present we create a corresponding node for that character and then move to that newly created node. Repeat this procedure still we reach the end of the suffix.
  • Repeat the above procedure for all suffixes.

Trie Implementation in C++ Algorithm (Searching):

  • The algorithm for searching is similar to the insertion algorithm. We start from the head node and first character of the pattern.
  • If we have a child node for the current character we move to that node and check for next character.
  • Otherwise if we don’t have a node we just return false as this means our pattern is not present in the text.

C++ Code:

#include <bits/stdc++.h>
using namespace std;
class TrieNode
{
public:
    unordered_map<char, TrieNode *> M;
};
void insert(TrieNode *&head, string s)
{
    TrieNode *temp = head;
    for (int i = 0; i < s.length(); i++)
    {
        char c = s[i];
        // Add a new node if not present already
        if (temp->M.find(c) == temp->M.end())
            temp->M[c] = new TrieNode();
        
        // Move to next node
        temp = temp->M[c];
    }
}
bool search(TrieNode *head, string pattern)
{
    TrieNode *temp = head;
    for (int i = 0; i < pattern.length(); i++)
    {
        char c = pattern[i];
        // If node for the charactor is not present this means the pattern is note present in the text
        if (temp->M.find(c) == temp->M.end())
            return false;
        temp = temp->M[c];
    }
    
    return true;
}
int main()
{
    string s = “prepinsta”;
    string pattern = “repin”, pattern2 = “repinx”;
    string suffix;
    TrieNode *head = new TrieNode();
    for (int i = s.length() – 1; i >= 0; i–)
    {
        suffix = s[i] + suffix;
        insert(head, suffix);
        cout << “Inserting Suffix “ << suffix << ” in the trie” << endl;
    }
    if (search(head, pattern))
        cout << “Found “ << pattern << endl;
    if (!search(head, pattern2))
        cout << “Not Found “ << pattern2 << endl;
    return 0;
}

Output:

Inserting Suffix a in the trie
Inserting Suffix ta in the trie
Inserting Suffix sta in the trie
Inserting Suffix nsta in the trie
Inserting Suffix insta in the trie
Inserting Suffix pinsta in the trie
Inserting Suffix epinsta in the trie
Inserting Suffix repinsta in the trie
Inserting Suffix prepinsta in the trie
Found repin
Not Found repinx