Trie Data Structure (Prefix Tree)

A Trie, also known as a prefix tree, is a tree-like data structure that stores a dynamic set or associative array where keys are usually strings. It is highly efficient for retrieval operations especially for prefix-based searches.

Core Operations

Insertion

Insert words letter by letter, branching out nodes as required.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = 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_end_of_word = True

Search

Check if a word or prefix exists by traversing through the node chain.

    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_end_of_word

Deletion

Deletion involves removing words and possibly pruning unnecessary nodes, done recursively.

    def _delete(self, node, word, depth):
        if depth == len(word):
            if not node.is_end_of_word:
                return False
            node.is_end_of_word = False
            return len(node.children) == 0
        char = word[depth]
        if char not in node.children:
            return False
        should_delete_child = self._delete(node.children[char], word, depth + 1)
        if should_delete_child:
            del node.children[char]
            return len(node.children) == 0 and not node.is_end_of_word
        return False

    def delete(self, word):
        self._delete(self.root, word, 0)

Applications of Trie