Trie Datastructure

GitHub Link : https://github.com/prakashbtech87/PrakashJavaRepository/tree/main/src/main/java/com/prakash/datastructure/trie

A Trie (pronounced like “try”) is a special type of tree-like data structure used mainly for storing and managing strings, particularly for tasks like autocomplete or spell checking. Here’s how it works in simple terms:

The name “Trie” (pronounced like “try”) is derived from the word “retrieval.” It refers to a specific type of tree data structure used primarily for storing and retrieving keys in a way that allows for efficient access.

Basic Concept

• Tree Structure: Think of a Trie as an upside-down tree. The root (top) represents an empty string, and each path from the root downwards represents a string made up of letters.

How It Works

• Inserting Words: When you insert a word (like “cat”), you start from the root and add each letter as a separate branch. So, you’d have a path like this:

root
  └─ c
      └─ a
          └─ t        

• This means that the word “cat” is stored in the Trie.
• Searching for Words: To check if a word is in the Trie, you follow the same path based on the letters. If you can follow the path to the end of the word, then the word exists in the Trie.
• Finding Prefixes: Tries are great for finding words that start with a certain prefix. For example, if you want to find words that start with “ca,” you can go down the path “c” → “a” and then check all branches beneath “a” (which could lead to words like “cat,” “cap,” etc.).

Key Features

1. Space Efficiency: They can be more space-efficient than storing all words as separate strings because they share common prefixes.
2. Fast Search: Searching for words or prefixes is generally fast, as it depends on the length of the word rather than the number of words stored.

Example:

package com.prakash.datastructure.trie;

/**
 * @author prakashkaruppusamy
 */
class TrieNode {
    // Each node can have multiple children (one for each character)
    TrieNode[] children = new TrieNode[26]; // For 'a' to 'z'
    boolean isEndOfWord = false; // Indicates if a word ends at this node

    // Constructor
    public TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = null; // Initialize children to null
        }
    }
}

class Trie {
    private TrieNode root; // Root node of the Trie

    // Constructor
    public Trie() {
        root = new TrieNode(); // Initialize the root node
    }

    // Insert a word into the Trie
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // Get the index for the character (0 for 'a', 1 for 'b', ...)
            if (node.children[index] == null) {
                node.children[index] = new TrieNode(); // Create a new node if it doesn't exist
            }
            node = node.children[index]; // Move to the child node
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word in the Trie
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a'; // Get the index for the character
            if (node.children[index] == null) {
                return false; // If the node doesn't exist, the word isn't in the Trie
            }
            node = node.children[index]; // Move to the child node
        }
        return node.isEndOfWord; // Return true if it's the end of a word
    }

    // Check if there is any word in the Trie that starts with the given prefix
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a'; // Get the index for the character
            if (node.children[index] == null) {
                return false; // If the node doesn't exist, no words with this prefix
            }
            node = node.children[index]; // Move to the child node
        }
        return true; // Found the prefix
    }
}        

Explanation of the Code

TrieNode Class:

• Each TrieNode has an array of children (size 26 for each letter of the alphabet) and a boolean isEndOfWord to indicate if a word ends at that node.
• The constructor initializes the children to null.

Trie Class:

• The Trie class has a root node of type TrieNode.
• The constructor initializes the root node.

Insert Method:

• This method takes a word as input and adds it to the Trie.
• It iterates through each character of the word, calculates its index (0–25), and checks if the corresponding child node exists.
• If it doesn’t exist, a new TrieNode is created.
• After processing all characters, it marks the last node as the end of the word.

Search Method:

• This method checks if a given word exists in the Trie.
• It follows the same process as insertion, but it checks if nodes exist at each character index and returns true only if it reaches the end of the word.

StartsWith Method:

• This method checks if there is any word in the Trie that starts with a given prefix.
• It follows the same process as the search method but returns true if it can traverse the nodes corresponding to the prefix, regardless of whether it reaches an end of a word.

package com.prakash.datastructure.trie;

/**
 * @author prakashkaruppusamy
 */
public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();

        // Insert words into the Trie
        trie.insert("apple");
        trie.insert("app");

        // Search for words
        System.out.println(trie.search("apple")); // true
        System.out.println(trie.search("app"));   // true
        System.out.println(trie.search("appl"));  // false
        System.out.println(trie.startsWith("ap")); // true
        System.out.println(trie.startsWith("b"));   // false
    }
}        

Output:

This simple implementation of a Trie allows you to insert words, search for complete words, and check for prefixes efficiently. It’s particularly useful for applications like autocomplete, spell-checking, and IP routing. The main advantage of using a Trie is that it can provide faster lookup times compared to other data structures like hash tables when dealing with prefix-related queries.