Trie, often called a prefix tree and named after the term reTRIEval, is a tree-like data structure tailored for string operations. Instead of housing data within its nodes, a Trie utilizes its edges to encode information.

Key Features

• Fast String Operations: Tries streamline operations such as search, insert, and delete for strings, offering an edge over arrays and hash tables in specific scenarios.
• Efficient Prefix Searches: Their hierarchical structure facilitates easy traversal, making operations like autocomplete and prefix-based searches efficient.
• Memory Compactness: While they can be more space-intensive than hash tables for smaller dictionaries, Tries can store large dictionaries compactly, suiting tasks like natural language processing, spell-checking, and IP routing.

Core Components

Trie Nodes

The root node doesn’t carry a character value but acts as the starting point. Each subsequent child node corresponds to a distinct character. Some nodes might denote the end of a string while simultaneously representing characters.

Node Pointers

Nodes in the Trie hold references to child nodes. For instance, when dealing with the English alphabet, an array of 26 elements can map characters to respective child nodes.

Visual Representation

Complexity Analysis

• Time Complexity:

  • Insertion, Search, and Deletion: $O(m)$ on average, where $m$ is the length of the word.
  • Prefix Search: $O(p)$, where $p$ is the number of words sharing the prefix.

• Space Complexity: Roughly $O(n \cdot \sigma)$, where $n$ is the total word count and $\sigma$ represents the size of the alphabet.

Code Example: Trie

Here is the Python code:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word_end = True
        
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_word_end

# Usage example
trie = Trie()
for word in ["a", "to", "tea", "ted", "ten", "in", "inn"]:
    trie.insert(word)

print(trie.search("tea"))  # True
print(trie.search("tedd")) # False