Introduction to Trie | DSA in C++ - Software Development PDF Download

Introduction

• Tries, also known as prefix trees, are tree-based data structures commonly used for efficient string operations.
• Tries offer fast insertion, deletion, and search operations for strings, making them a valuable tool in various applications, including text processing, spell checking, and autocomplete.

What is a Trie?

• A Trie is a tree-like data structure where each node represents a character or a partial string.
• The root of the Trie represents an empty string, and each path from the root to a leaf node represents a complete string.
• Unlike binary search trees or hash tables, Tries store information in a tree structure, making them well-suited for handling strings efficiently.

Key Features of Tries

• Fast Lookup: Tries provide efficient search operations for strings, typically with a time complexity of O(M), where M is the length of the search string.
• Prefix Matching: Tries excel at finding strings with a common prefix, making them ideal for autocompletion or spell checking.
• Space Efficiency: While Tries offer fast operations, they may consume more memory compared to other data structures.
• Easy String Operations: Tries simplify various string operations like insertion, deletion, and traversal.

Trie Implementation in C++:

• Let's understand how to implement a Trie data structure in C++ using classes and pointers.
• We'll start by defining the TrieNode class and its essential functions.

Code Example 1: TrieNode Class Implementation

class TrieNode {

public:

    bool isEndOfWord;

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

    TrieNode() {

        isEndOfWord = false;

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

            children[i] = nullptr;

        }

    }

};

Explanation:

• The 'TrieNode' class represents a single node in the Trie.
• It consists of a boolean flag 'isEndOfWord' to mark the end of a word and an array 'children' to store references to child nodes for each lowercase alphabet.
• In the constructor, 'isEndOfWord' is set to 'false', and the 'children' array is initialized with 'nullptr' values.

Code Example 2: Trie Class Implementation

class Trie {

    TrieNode* root;

public:

    Trie() {

        root = new TrieNode();

    }

    void insert(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;

    }

    bool search(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->isEndOfWord;

    }

};

Explanation:

• The 'Trie' class represents the Trie data structure.
• It includes a pointer 'root' to the root node of the Trie.
• The constructor initializes the Trie by creating a new root node.
• The 'insert' function inserts a word into the Trie by traversing the Trie and creating new nodes as needed.
• The 'search' function checks if a given word exists in the Trie by traversing the Trie and returning 'true' if the word is found and the corresponding 'isEndOfWord' flag is set.

Sample Usage:

Trie trie;

// Inserting words into the Trie

trie.insert("apple");

trie.insert("banana");

trie.insert("orange");

// Searching for words in the Trie

cout << trie.search("apple") << endl;   // Output: 1 (true)

cout << trie.search("banana") << endl;  // Output: 1 (true)

cout << trie.search("grape") << endl;   // Output: 0 (false)

Explanation:

In the sample usage, we create a Trie object and insert three words: "apple," "banana," and "orange."

We then perform search operations to check if specific words exist in the Trie using the 'search' function.

Sample Problems

Problem 1: Implement a function to count the number of words starting with a given prefix in a given Trie.

• Input: Trie and a prefix string
• Output: Count of words starting with the given prefix

Problem 2: Given a list of words, find the longest common prefix among them.

• Input: List of words
• Output: Longest common prefix

Problem 3: Implement a function to remove a word from a Trie.

• Input: Trie and a word to be removed
• Output: Updated Trie without the specified word

Note: For the solutions to the sample problems, refer to the accompanying code samples and explanations.
By following the concepts and examples presented in this article, you can gain a solid understanding of Tries and their implementation in C++.

Conclusion

• Tries are powerful data structures for handling strings efficiently, providing fast search and string operation capabilities.
• By implementing Tries in C++, you can leverage their benefits in various applications that involve extensive string processing.