Trie | (Insert and Search) | DSA in C++ - Software Development PDF Download

Introduction

The Trie data structure, also known as a prefix tree, is a versatile and efficient data structure used for storing and searching strings. In this article, we will explore the implementation of Trie in C++ and understand how to perform insertion and search operations. We will cover the basic concepts, provide clear code examples, and offer sample problems to solidify your understanding.

What is a Trie?

A Trie is a tree-like data structure that stores strings in a way that allows for efficient retrieval. It is commonly used in applications such as auto-complete, spell checkers, and IP routing. Each node in the Trie represents a character, and the edges represent possible next characters. The root node represents an empty string, and each path from the root to a leaf node forms a valid word.

Trie Node Structure

In C++, we can define a Trie node as a structure containing a boolean flag to mark the end of a word and an array/vector of child nodes representing the possible characters.

struct TrieNode {

    bool isEndOfWord;

    vector<TrieNode*> children;

};

Trie Insertion Operation

The insertion operation adds a new word to the Trie. We traverse the Trie from the root, creating new nodes as necessary.

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

    TrieNode* curr = root;

    for (char c : word) {

        int index = c - 'a'; // assuming lowercase alphabets

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

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

        }

        curr = curr->children[index];

    }

    curr->isEndOfWord = true;

}

Trie Search Operation:

The search operation determines whether a word exists in the Trie. We traverse the Trie, following the characters of the word.

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

}

Code Examples:

Let's put the Trie operations to use with some code examples:

int main() {

    TrieNode* root = new TrieNode();

    // Inserting words

    insertWord(root, "apple");

    insertWord(root, "banana");

    insertWord(root, "cat");

    // Searching words

    cout << searchWord(root, "apple") << endl;   // Output: 1 (true)

    cout << searchWord(root, "ball") << endl;    // Output: 0 (false)

    cout << searchWord(root, "cat") << endl;     // Output: 1 (true)

    return 0;

}

Output Explanation:

• "apple" is present in the Trie, so the search returns true (1).
• "ball" is not present in the Trie, so the search returns false (0).
• "cat" is present in the Trie, so the search returns true (1).

Sample Problems:

Problem 1: Given a list of words, find the longest word that can be formed by other words in the list.

We can build a Trie with all the words and perform a depth-first search (DFS) to find the longest word.

Problem 2: Implement auto-complete functionality using a Trie.

Build a Trie with a dictionary of words and provide suggestions based on the entered prefix.

Conclusion:

In this article, we explored the Trie data structure and learned how to perform insertion and search operations in C++. Tries provide an efficient way to store and search strings, making them a valuable tool in various applications. By understanding the basic concepts and practicing with the code examples and sample problems, you can confidently leverage Tries in your programming endeavors.