Trie | (Delete) | DSA in C++ - Software Development PDF Download

Introduction

The Trie data structure, also known as a prefix tree, is an efficient tree-based data structure used to store and search for strings. It provides fast operations for inserting, searching, and deleting strings in linear time. In this article, we will explore the basics of Trie data structure and specifically focus on how to delete nodes from a Trie in C++. We will cover the concepts, provide simple code examples, explain their functionality, and conclude with some sample problems and solutions.

Overview of Trie

• Definition: A Trie is a tree-based data structure used to efficiently store and search for strings.
• Each node in the Trie represents a character, and the edges represent possible characters that can follow that node.
• The root node represents an empty string, and each path from the root to a leaf node forms a string stored in the Trie.

Trie Node Structure

To implement Trie, we need a node structure that can hold characters and pointers to child nodes. Here's an example implementation in C++:

struct TrieNode {

    TrieNode* children[26];  // Assuming only lowercase English alphabets

    bool isEndOfWord;        // Flag to indicate the end of a word

    TrieNode() {

        for (int i = 0; i < 26; ++i)

            children[i] = nullptr;

        isEndOfWord = false;

    }

};

Inserting Strings into Trie

To insert a string into a Trie, we traverse the Trie from the root node, creating new nodes for each character if they don't already exist. Here's an example implementation:

void insert(TrieNode* root, const string& word) {

    TrieNode* curr = root;

    for (char c : word) {

        int index = c - 'a';

        if (curr->children[index] == nullptr)

            curr->children[index] = new TrieNode();

        curr = curr->children[index];

    }

    curr->isEndOfWord = true;

}

Searching for Strings in Trie

To search for a string in a Trie, we traverse the Trie from the root node, following the edges corresponding to each character. Here's an example implementation:

bool search(TrieNode* root, const string& word) {

    TrieNode* curr = root;

    for (char c : word) {

        int index = c - 'a';

        if (curr->children[index] == nullptr)

            return false;

        curr = curr->children[index];

    }

    return curr != nullptr && curr->isEndOfWord;

}

Deleting Nodes in Trie

Deleting nodes from a Trie involves marking the last node of a string as not the end of the word and then recursively deleting any unnecessary nodes in reverse order. Here's an example implementation:

bool deleteNode(TrieNode* root, const string& word, int depth = 0) {

    if (root == nullptr)

        return false;

    if (depth == word.length()) {

        if (!root->isEndOfWord)

            return false;

        root->isEndOfWord = false;

        return isNodeEmpty(root);

    }

    int index = word[depth] - 'a';

    if (deleteNode(root->children[index], word, depth + 1)) {

        delete root->children[index];

        root->children[index] = nullptr;

        return isNodeEmpty(root);

    }

    return false;

}

bool isNodeEmpty(TrieNode* node) {

    for (int i = 0; i < 26; ++i) {

        if (node->children[i] != nullptr)

            return false;

    }

    return true;

}

Sample Problems and Solutions

Problem 1: Implement a function to delete a word from a Trie.

// Assuming the Trie is already built

void deleteWord(TrieNode* root, const string& word) {

    deleteNode(root, word);

}

Problem 2: Find the count of all distinct words in a Trie.

int countDistinctWords(TrieNode* root) {

    int count = 0;

    if (root->isEndOfWord)

        ++count;

    for (int i = 0; i < 26; ++i) {

        if (root->children[i] != nullptr)

            count += countDistinctWords(root->children[i]);

    }

    return count;

}

Conclusion

In this article, we explored the Trie data structure and learned how to insert, search, and delete nodes in a Trie using simple code examples. Tries are powerful data structures for storing and efficiently searching for strings. By understanding the concepts and implementing the provided code examples, beginners can begin utilizing Tries in their C++ programs.
Remember to handle memory deallocation appropriately when deleting nodes from a Trie to avoid memory leaks. Additionally, further exploration of advanced Trie operations and optimizations can enhance your understanding and utilization of this data structure.