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.

Clear all your Software Development doubts with EduRev Join for Free

Join for Free

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.

Download the notes Introduction to Trie

Download as PDF

Download as PDF

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

Take a Practice Test Test yourself on topics from Software Development exam

Practice Now

Practice Now

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.