Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Introduction

Trie is a data structure that resembles a tree and is used to store a collection of strings; it is typically found in dictionaries or search engines. It is also referred to as a digital tree or a prefix tree. In this article, we'll look at how the Trie data structure is implemented in C++ using principles of object-oriented programming (OOP).

Table of contents:

OOP concepts
What is Trie ?
Real-life applications of Trie
Trie Implementation in C++
Advantages of Trie
Conclusion
Complete code of Trie in C++

OOP concepts

Let's briefly go over some OOPs concepts that we will be utilizing in our implementation before getting started on the C++ implementation of Trie.

1.Encapsulation is the process of shielding a class's implementation specifics from the outside world. Encapsulation will be used to shield the user from our Trie class's implementation specifics.

2.Inheritance:The process of constructing a new class from an existing class is known as inheritance. To create a Node class from which our TrieNode class will be derived, we will use inheritance.

3.Polymorphism: The capacity for an object to assume various forms is known as polymorphism. The Trie class's insert() and search() methods will be developed using polymorphism.

4.Abstraction: Abstraction is the process of hiding the implementation details of a system and exposing only the essential features to the user.

What is Trie ?

Trie is a data structure that resembles a tree and is used to store a collection of strings; it is typically found in dictionaries or search engines. It is also referred to as a digital tree or a prefix tree. The term "retrieval," which describes the procedure of obtaining data from a database, is where the word "trie" is derived.

Each node in a trie corresponds to a character in a string. Each child node represents a character in the string, with the root node representing the empty string. Each node has an array of pointers to its child nodes as well as a boolean variable to indicate the end of a word.

Tries can quickly search for and retrieve data based on a prefix or partial match, and they are frequently used in search engines and spell checkers. Large sets of strings can be efficiently stored and searched for using tries.

Real-life applications of Trie

Tries' quick search and retrieval times and effective memory usage enable a wide range of practical applications. Here are a few instances of Tries being used in various contexts:

1.Spell Checkers: Tries are frequently used in spell-checking software to suggest different ways to spell words that are spelt incorrectly. The Trie can quickly find all potential completions as the user types, making it simpler for the user to find the right spelling.

2.Search Engines: In order to index web pages and retrieve results quickly, search engines use various techniques. The Trie can quickly locate all potential completions of a search query as the user types it, making it simpler for the user to find what they are looking for.

3.Text editors: To offer auto-complete suggestions as the user types, text editors use tries. Long words or phrases can be typed more easily because the Trie can quickly find all possible completions as the user types a word.

4.Data compression: By swapping out repetitive substrings with a single reference, it is possible to effectively compress data. Trie compression is a method that is frequently employed in data compression algorithms like Lempel-Ziv-Welch (LZW).

5.Computer networking: Tries are used to store and look up IP addresses in computer networking. Tries can quickly access particular addresses based on their prefixes and handle large sets of IP addresses with efficiency.

Trie Implementation in C++

In order to represent a node in our Trie, let's begin by creating a Node class. The Node class will include an array of pointers to its child nodes as well as a boolean variable to indicate the end of a word.

class Node {
public:
    bool isEndOfWord;
    Node* children[26];
    Node() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

The TrieNode class, which will represent our Trie data structure, will then be created. A pointer to the Trie's root node is included in the TrieNode class.
In order to prevent external access to the root node, which could result in unexpected behaviour or security vulnerabilities, the root node is typically made private. The programmer can manage access to the Trie structure and prevent unintended changes to the Trie's internal state by keeping the root node private. This ensures that the Trie operates as intended and contributes to maintaining the structure's integrity and security.

class TrieNode {
private:
    Node* root;
public:
    TrieNode() {
        root = new Node();
    }
    void insert(string word);
    bool search(string word);
};

Let's now implement the TrieNode class's insert() method. This method will insert a string into the Trie from an input string.

void TrieNode::insert(string word) {
    Node* current = root;
    for (char c : word) {
        int index = c - 'a';
        if (current->children[index] == nullptr) {
            current->children[index] = new Node();
        }
        current = current->children[index];
    }
    current->isEndOfWord = true;
}

Starting at the root node and iterating through each character in the string is what the insert() method does. We determine whether the corresponding child node is present for each character. If not, we make a new node and set it as the current node's child. The word is finally declared to be finished at the last node.

Let's implement our TrieNode class's search() method next. When given a string as input, this method will return true if the string is present in the Trie and false otherwise.

bool TrieNode::search(string word) {
    Node* current = root;
    for (char c : word) {
        int index = c - 'a';
        if (current->children[index] == nullptr) {
            return false;
        }
        current = current->children[index];
    }
    return current->isEndOfWord;
}

We iterate through each character in the string starting at the root node in the search() method. We determine whether the corresponding child node is present for each character. If not, we provide a false response. If the Trie finds the entire string, we return.

A Trie can only be deleted if all of the nodes connected to the string are also deleted. The deletion operation in a Trie data structure is implemented as follows:

void Trie::deleteNode(Node* node, std::string key, int depth)
{
    // If Trie is empty
    if (node == nullptr)
        return;

    // If last character of key is being processed
    if (depth == key.length()) {
        if (node->isEndOfWord) {
            node->isEndOfWord = false;
        }
        return;
    }

    // If not last character, recur for the child node
    int index = key[depth] - 'a';
    deleteNode(node->children[index], key, depth + 1);

    // If the node has no children and is not an end of word, delete it
    if (!node->isEndOfWord) {
        bool isEmpty = true;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            if (node->children[i] != nullptr) {
                isEmpty = false;
                break;
            }
        }
        if (isEmpty) {
            delete node;
            node = nullptr;
        }
    }
}

Advantages of Trie

1.Fast search and retrieval: Tries are a great option for applications that need quick access to big sets of strings because they have a very fast search and retrieval time. By moving down the tree and comparing characters at each node until it reaches the end of the string, Tries can locate a string quickly.

2.Searching for prefixes and suffixes: Tries are particularly helpful for applications that need to search for prefixes or suffixes. A suffix search can locate all strings that end with a specific suffix, whereas a prefix search can locate all strings that start with a specific prefix.

3.Storage efficiency: When it comes to holding big sets of strings, tries are very space-efficient. Tries stores common prefixes as a single node, whereas other data structures store each string separately. This reduces the amount of memory needed to store the strings.

4.Autocomplete: Tries are frequently used in auto-complete applications, such as text editors and search engines. The Trie can quickly find all potential completions as the user types, making it simpler for the user to find what they're looking for.

Conclusion

Trie is a strong data structure that is utilized for effective string storing and searching. Compared to other data structures, tries offer a number of benefits, including quick search and retrieval, prefix and suffix searching, and effective memory usage. Tries have many uses in a variety of industries, including text editors, genome sequencing, data compression, search engines, and spell checkers.

Programmers can create robust applications that can handle large sets of strings and provide quick access to specific strings based on their prefixes or suffixes by understanding the fundamental concepts of Trie and implementing it using OOP concepts in C++. Programmers can also increase the effectiveness of Tries by using memory management strategies and other optimizations to improve their performance.

Tries have evolved into a crucial tool for handling massive sets of strings effectively in today's world where the amount of data is increasing exponentially. Thus, understanding Tries and their applications is a useful skill for any programmer who wants to create high-performance programmers that can effectively handle big sets of strings.

Complete code of Trie in C++

#include <iostream>
#include <string>

const int ALPHABET_SIZE = 26;

class Node {
public:
    bool isEndOfWord;
    Node* children[ALPHABET_SIZE];

    Node() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = nullptr;
        }
    }
};

class Trie {
private:
    Node* root;

    void deleteNode(Node* node, std::string key, int depth) {
        if (node == nullptr) {
            return;
        }

        if (depth == key.length()) {
            if (node->isEndOfWord) {
                node->isEndOfWord = false;
            }
            return;
        }

        int index = key[depth] - 'a';
        deleteNode(node->children[index], key, depth + 1);

        if (!node->isEndOfWord) {
            bool isEmpty = true;
            for (int i = 0; i < ALPHABET_SIZE; i++) {
                if (node->children[i] != nullptr) {
                    isEmpty = false;
                    break;
                }
            }
            if (isEmpty) {
                delete node;
                node = nullptr;
            }
        }
    }

public:
    Trie() {
        root = new Node();
    }

    void insert(std::string key) {
        Node* current = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key[i] - 'a';
            if (current->children[index] == nullptr) {
                current->children[index] = new Node();
            }
            current = current->children[index];
        }
        current->isEndOfWord = true;
    }

    bool search(std::string key) {
        Node* current = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key[i] - 'a';
            if (current->children[index] == nullptr) {
                return false;
            }
            current = current->children[index];
        }
        return (current != nullptr && current->isEndOfWord);
    }

    void deleteString(std::string key) {
        deleteNode(root, key, 0);
    }
};

With this article at OpenGenus, you must have the complete idea of how to implement Trie data structure in C++ Programming Language.

Trie in C++ using OOP concepts

C++ trie Data Structures