Trie Data Structure in C++ - Coding

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:

Example: Trie Data Structure

Basic operations on Trie Data Structure

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

Operation	Description	Time Complexity	Space Complexity
Insert	Inserts a new word into the trie.	O(n)	O(n)
Search	Searches for a word in the trie.	O(n)	O(1)
Delete	Removes a word from the trie.	O(n)	O(1)
StartsWith	Checks if there is any word in the trie that starts with the given prefix	O(m)	O(1)

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++

// 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.

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

Reffered: https://www.geeksforgeeks.org

C++

Related
How to Implement Interfaces Using Abstract Class in C++
Inorder Tree Traversal of Binary Tree in C++
How to Convert wstring to double in C++
Graph Cycle Detection in C++
How to Read Binary Search Tree from File in C++?

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	18