Tries in Data Structures

In the world of data structures, Tries (pronounced as “trees” or “try”) hold a special place when it comes to efficient retrieval of strings, especially in applications like autocomplete, spell checking, and IP routing. Also known as Prefix Trees, Tries offer a unique and powerful alternative to other tree structures for dealing with textual data. Learn about Tries in Data Structures, a powerful tree-based data structure used for efficient searching, storing strings, and implementing autocomplete systems. Discover What is Test Driven Development (TDD)? Learn how writing tests before code improves software quality, reduces bugs, and speeds up the development process.

In this blog, we’ll explore the concept of Tries, their implementation, applications, and advantages over other data structures.

What is a Trie?

A Trie is a tree-like data structure used to store a dynamic set of strings, where each node typically represents a single character of a word. The root node is usually empty, and every path from the root to a leaf node represents a complete string or word.

The primary idea behind Tries is prefix sharing. For example, the words "top", "to", and "today" share a common prefix "to", so they can branch off from the same starting path.

Structure of a Trie Node:-

Each node in a Trie generally contains:

• A character.
• An array/map of child nodes, one for each possible character.
• A boolean flag indicating if the node represents the end of a valid word (isEndOfWord).

Example:-

Let's say we insert "cat", "car", and "dog" into a Trie:

         (root)

        /     \

      c         d

     /           \

    a             o

   /               \

  t                 g

  |

  r

• • The path c -> a -> t represents "cat".
• • The path c -> a -> r represents "car".
• • The path d -> o -> g represents "dog".

Trie Operations:-

Here are the most common operations performed on a Trie:

1. Insert a Word

To insert a word, start from the root node. For each character:

• If the character exists in the current node’s children, move to that child.
• If not, create a new node.
• Mark the last node as the end of a word.

2. Search for a Word

To search for a word:

• Start at the root and follow the path for each character.
• If at any point the path does not exist, the word is not present.
• If the path exists and the last node is marked as the end of a word, the word is found.

3. Prefix Search

Instead of checking for a complete word, you can search for a prefix to suggest or retrieve all words starting with it—useful in autocomplete systems.

Advantages of Tries:-

1. 1. Fast Lookup Time: Searching in a Trie takes O(L) time, where L is the length of the word, much faster than searching through a list.
2. 2. Efficient Prefix Matching: Excellent for tasks involving prefix-based searches or autocomplete features.
3. 3. Space Optimization for Shared Prefixes: Words with common prefixes use shared nodes, reducing memory usage.

Disadvantages of Tries:-

1. 1. High Memory Usage: In worst-case scenarios (sparse data), each node can have multiple pointers (especially for large alphabets).
2. 2. Complex Implementation: Compared to arrays or hash maps, Tries can be harder to implement and manage.

Applications of Tries:-

1. 1. Autocomplete Systems (e.g., Google Search).
2. 2. Spell Checkers.
3. 3. IP Routing (Longest Prefix Match).
4. 4. Word Games & Solvers (like Boggle, Scrabble).
5. 5. Search Engines and Text Editors.
6. 6. Dictionary Storage and Search.

Trie vs Hash Map vs Binary Search Tree:-

Basic C++ Implementation of a Trie:-

#include <iostream>

using namespace std;

const int ALPHABET_SIZE = 26;

// Trie Node definition

struct TrieNode {

    TrieNode* children[ALPHABET_SIZE];

    bool isEndOfWord;

    TrieNode() {

        isEndOfWord = false;

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

            children[i] = nullptr;

    }

};

// Trie class

class Trie {

private:

    TrieNode* root;

public:

    Trie() {

        root = new TrieNode();

    }

    // Insert word into Trie

    void insert(const string& word) {

        TrieNode* current = root;

        for (char ch : word) {

            int index = ch - 'a';

            if (!current->children[index])

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

            current = current->children[index];

        }

        current->isEndOfWord = true;

    }

    // Search word in Trie

    bool search(const string& word) {

        TrieNode* current = root;

        for (char ch : word) {

            int index = ch - 'a';

            if (!current->children[index])

                return false;

            current = current->children[index];

        }

        return current->isEndOfWord;

    }

    // Check if any word starts with given prefix

    bool startsWith(const string& prefix) {

        TrieNode* current = root;

        for (char ch : prefix) {

            int index = ch - 'a';

            if (!current->children[index])

                return false;

            current = current->children[index];

        }

        return true;

    }

};

int main() {

    Trie trie;

    trie.insert("apple");

    trie.insert("app");

    cout << boolalpha;

    cout << "Search 'apple': " << trie.search("apple") << endl; // true

    cout << "Search 'app': " << trie.search("app") << endl; // true

    cout << "Search 'ap': " << trie.search("ap") << endl; // false

    cout << "StartsWith 'ap': " << trie.startsWith("ap") << endl; // true

    return 0;

}

Thus, Tries are a powerful and versatile data structure for handling string-based operations, especially when prefix searches are involved. While they may consume more memory than other structures, their performance in tasks like autocomplete and dictionary implementation makes them indispensable in real-world applications.

If your application involves a lot of string matching or suggestions, implementing a Trie could drastically improve speed and efficiency.

Do visit our channel to explore more: SevenMentor

Author :- Sarika kore