Tries

A trie stores strings by their characters along tree paths, giving lookup time proportional to key length rather than the number of keys.

A tree keyed by characters

A trie, also called a prefix tree, stores a set of strings so that each edge is labelled with a character and each root-to-node path spells a prefix. A node is marked as a word end when its path spells a complete stored key. Because keys with a common prefix share the same initial path, storage and search both exploit shared prefixes.

Length-bounded operations

To look up, insert, or delete a string of length L, you follow or create L edges from the root. This costs O(L) and, crucially, does not depend on how many strings the trie holds. A hash table also offers roughly O(L) lookup once hashing is counted, but a trie additionally supports prefix queries a hash cannot.

• Insert a key of length L: O(L)
• Search a key of length L: O(L)
• Enumerate all keys with a given prefix: O(size of that subtree)
• Space: proportional to total characters, less when prefixes are shared

Prefix power

The trie's signature strength is prefix work: autocomplete, dictionary lookup, and IP routing all ask for every key sharing a prefix, which is just the subtree below the prefix node. This is why tries back spell-checkers, predictive text, and routing tables.

Space and compression

A plain trie can waste memory when many nodes have a single child. A radix tree (or Patricia trie) compresses each chain of single-child nodes into one edge labelled with a substring, shrinking the structure. For fixed alphabets a bitwise trie is common in networking.

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

def insert(root, word):
    node = root
    for c in word:
        node = node.children.setdefault(c, TrieNode())
    node.end = True