Trie(Prefix Tree)

A trie, also known as a prefix tree, is a tree-like data structure used to store an associative array where the keys are sequences, usually strings. Each node of a trie corresponds to a character of a key, and the position of a node in the trie defines the key with which it is associated.

A trie is an efficient way to store a large set of strings, by organizing them in a tree-like structure, where each node represents a single character of a string. The root of the tree represents an empty string, and each path from the root to a leaf node represents a string stored in the trie.

Tries are used to search for words in a dictionary, spelling correction, IP routing, searching for DNA sequences, and many more. Tries are particularly useful for searching and inserting strings in a large dataset as they are efficient in terms of time and space.

Tries are efficient in searching and inserting operations because, in the worst case, the time complexity is O(n) where n is the length of the key. This is because the trie is a tree-like structure, and in the worst case, we might have to traverse all the way down to the leaf node, where the key is located.

In terms of space, a trie can be more efficient than a hash table or a binary search tree because it only stores the common prefixes of the keys, which can be shared among many keys, therefore reducing the overall space requirements.

A trie can also be implemented using a Map in Java. A Map is a collection that maps keys to values and can be used to implement the nodes of a trie. Here is an example of how to implement a trie data structure using a Map in Java:

import java.util.HashMap;
import java.util.Map;

class Trie {
    private class TrieNode {
        Map<Character, TrieNode> children;
        boolean endOfWord;

        TrieNode() {
            children = new HashMap<>();
            endOfWord = false;
        }
    }

    private final TrieNode root;

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

    // Insert a word into the trie
    public void insert(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            if (node == null) {
                node = new TrieNode();
                current.children.put(ch, node);
            }
            current = node;
        }
        current.endOfWord = true;
    }

    // Search for a word in the trie
    public boolean search(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.children.get(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return current.endOfWord;
    }
    
    // Search for a prefix in the trie
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            TrieNode node = current.children.get(ch);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return true;
    }
    
    public static void main(String args[]) {
        Trie trie = new Trie();
        String keys[] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
        for(int i=0 ; i < keys.length; i++){
            trie.insert(keys[i]);
        }
        System.out.println(trie.search("answer"));
        System.out.println(trie.search("ans"));
        System.out.println(trie.startsWith("ans"));
    }
}

true
false
true

In this implementation, each node of the trie is represented by an instance of the TrieNode class, which contains a Map of children and a boolean flag endOfWord to indicate if the node represents the end of a word.

The insert() method adds a word to the trie by iterating through the characters of the word and adding new nodes to the trie as needed.

The search() method checks if a word is present in the trie by iterating through the characters of the word and checking if the corresponding nodes exist in the trie.

The startsWith() method takes a prefix as an input and iterates through the characters of the prefix. For each character, it checks if the corresponding node exists in the trie using the get() method of the Map. If a node is not found, the method returns false as the prefix is not present in the trie. If all the characters of the prefix are found in the trie, the method returns true as the prefix is present in the trie as a prefix of one or more words.