Trie (Prefix Tree) Implementation in C++

A Trie (pronounced as “try”) is a tree-like data structure used to store a dynamic set of strings, where the keys are usually strings. It is an efficient information retrieval data structure, often used for searching and storing strings with a common prefix. Operations like insertion, deletion, and search can be performed in O(L) time complexity, where L is the length of the word.

Program Structure

The C++ implementation of a Trie will include:

1. Trie Node Structure: Defining the structure of a node in the Trie.
2. Trie Class: Implementing the Trie with functions for inserting, searching, and deleting words.
3. Example Usage: Demonstrating the insertion, search, and deletion of words.

Code Implementation

#include <iostream>
#include <unordered_map>
#include <string>

class TrieNode {
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode* root;

    bool deleteHelper(TrieNode* node, const std::string &word, int depth) {
        if (node == nullptr) {
            return false;
        }

        if (depth == word.size()) {
            if (!node->isEndOfWord) {
                return false;
            }
            node->isEndOfWord = false;

            return node->children.empty();
        }

        char ch = word[depth];
        if (deleteHelper(node->children[ch], word, depth + 1)) {
            delete node->children[ch];
            node->children.erase(ch);

            return node->children.empty() && !node->isEndOfWord;
        }

        return false;
    }

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

    void insert(const std::string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    bool search(const std::string &word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            node = node->children[ch];
        }
        return node->isEndOfWord;
    }

    void deleteWord(const std::string &word) {
        deleteHelper(root, word, 0);
    }
};

// Main function to demonstrate the Trie operations
int main() {
    Trie trie;

    trie.insert("hello");
    trie.insert("hell");
    trie.insert("heaven");
    trie.insert("heavy");

    std::cout << "Search results:" << std::endl;
    std::cout << "hello: " << (trie.search("hello") ? "Found" : "Not Found") << std::endl;
    std::cout << "heaven: " << (trie.search("heaven") ? "Found" : "Not Found") << std::endl;
    std::cout << "hell: " << (trie.search("hell") ? "Found" : "Not Found") << std::endl;
    std::cout << "he: " << (trie.search("he") ? "Found" : "Not Found") << std::endl;

    trie.deleteWord("hell");
    std::cout << "After deleting 'hell':" << std::endl;
    std::cout << "hell: " << (trie.search("hell") ? "Found" : "Not Found") << std::endl;
    std::cout << "hello: " << (trie.search("hello") ? "Found" : "Not Found") << std::endl;

    return 0;
}

Explanation

Trie Node Structure

The TrieNode class represents a node in the Trie. It contains:

• children: An unordered map that stores pointers to the child nodes. Each key is a character, and the corresponding value is a pointer to the child node associated with that character.
• isEndOfWord: A boolean flag indicating if the node marks the end of a word.

Trie Class

The Trie class manages the overall Trie structure and provides the following functions:

• insert(): Adds a word to the Trie by traversing the Trie from the root node, creating new nodes for each character as needed.
• search(): Searches for a word in the Trie by traversing through the nodes corresponding to each character of the word. Returns true if the word is found and false otherwise.
• deleteWord(): Deletes a word from the Trie using a recursive helper function deleteHelper(). The function removes the nodes corresponding to the characters of the word if they do not form part of another word.

Example Usage

In the main() function, the program demonstrates the insertion, search, and deletion operations of the Trie. It inserts several words, searches for some words, deletes a word, and then performs searches again to verify the deletion.

Conclusion

The Trie is a powerful data structure for managing and searching strings, particularly when dealing with large datasets where prefix-based searches are frequent. This C++ implementation covers the essential operations of a Trie, including word insertion, search, and deletion, making it suitable for various applications such as autocomplete, spell checking, and dictionary implementations.