Tree trie

Understanding Trie

A trie (pronounced "try"), also known as a prefix tree, is a type of search tree used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key it is associated with. All descendants of a node have a common prefix of the string associated with that node.

Key Features of a Trie

• Insertion: Efficiently insert words.
• Search: Quickly search for a word or prefix.
• Deletion: Remove words from the trie.

Java Implementation of a Trie

Here's how you can implement a Trie in Java:

TrieNode Class

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // Assuming only lowercase English letters
        isEndOfWord = false;
    }
}

Trie Class with Basic Operations

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Function to insert a word into the trie
    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEndOfWord = true;
    }

    // Function to search for a word in the trie
    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node != null && node.isEndOfWord;
    }

    // Function to 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 ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();

        trie.insert("apple");
        System.out.println(trie.search("apple"));   // returns true
        System.out.println(trie.search("app"));     // returns false
        System.out.println(trie.startsWith("app")); // returns true
        trie.insert("app");   
        System.out.println(trie.search("app"));     // returns true
    }
}

Explanation

1. TrieNode Class: ```java class TrieNode { TrieNode[] children; boolean isEndOfWord;

   public TrieNode() { children = new TrieNode[26]; // Assuming only lowercase English letters isEndOfWord = false; } } `` TheTrieNode` class represents each node in the Trie. Each node contains an array of child nodes for each character in the alphabet (assuming lowercase English letters), and a boolean to indicate if the node represents the end of a word.

2. Trie Class:

3. Constructor: java public Trie() { root = new TrieNode(); } The Trie class contains a root node, which is the starting point of the Trie.

4. Insert Function: java public void insert(String word) { TrieNode node = root; for (char ch : word.toCharArray()) { int index = ch - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEndOfWord = true; } This function inserts a word into the Trie. It iterates over each character of the word, calculates the index for the child array, and creates a new node if necessary. Finally, it marks the last node as the end of a word.

5. Search Function: java public boolean search(String word) { TrieNode node = root; for (char ch : word.toCharArray()) { int index = ch - 'a'; if (node.children[index] == null) { return false; } node = node.children[index]; } return node != null && node.isEndOfWord; } This function searches for a word in the Trie. It iterates over each character of the word and checks if the corresponding child node exists. If the word is found and the last node is marked as the end of a word, it returns true.

6. StartsWith Function: java public boolean startsWith(String prefix) { TrieNode node = root; for (char ch : prefix.toCharArray()) { int index = ch - 'a'; if (node.children[index] == null) { return false; } node = node.children[index]; } return true; } This function checks if there is any word in the Trie that starts with the given prefix. It iterates over each character of the prefix and checks if the corresponding child node exists. If all characters of the prefix are found, it returns true.

7. Main Method: ```java public static void main(String[] args) { Trie trie = new Trie();

   trie.insert("apple"); System.out.println(trie.search("apple")); // returns true System.out.println(trie.search("app")); // returns false System.out.println(trie.startsWith("app")); // returns true trie.insert("app");
   System.out.println(trie.search("app")); // returns true } ```

Conclusion

This example demonstrates the basic operations of a Trie in Java, including insertion, searching for a word, and checking if a prefix exists in the Trie. The Trie class provides an efficient way to store and search strings, making it a powerful tool for various applications such as autocomplete, spell checker, and IP routing.