Memory tradeoffs and compressed tries

What is a trie?

A trie, pronounced “try,” is a tree for storing words or other sequences by their prefixes. Each edge advances by one character. Words with the same beginning share a path. A terminal marker records where a complete word ends, since reaching a prefix does not mean that prefix is a stored word.

Example: The words "car" and "cat" share the path c → a. They then branch to r and t, each marked as the end of a word.

Helpful before this chapter

If these ideas are new, begin with:

Strings Hash maps and sets Binary trees

Understand the idea

Tries trade character-level nodes and pointers for prefix queries. A radix/compressed trie collapses nonbranching chains into string-labeled edges; matching then compares segments rather than one character.

Work through an example

dog can be represented as one edge 'dog' when no other d-prefix word branches. Inserting dot splits the edge into 'do' then g/t.

Time and space complexity

Ordinary trie O(total characters) nodes worst case; compressed edges reduce node overhead but still store labels.

Why it works

Compression preserves the same word paths and terminal positions.

Common mistakes

Large alphabet arrays waste memory for sparse children.
Splitting inside an edge must retain the unmatched suffix.

Chapter lab · Python implementation

A trie shares common prefixes rather than repeatedly storing each complete word path. Edges consume characters; a terminal marker distinguishes a complete word from merely a prefix. Our lab inserts cat, car, and dog, then supports exact, prefix, and dot-wildcard matching over code points.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

class Trie:
    def __init__(self): self.root={}
    def insert(self,word):
        node=self.root
        for char in word: node=node.setdefault(char,{})
        node[None]=True
    def locate(self,prefix):
        node=self.root
        for char in prefix:
            if char not in node: return None
            node=node[char]
        return node
    def contains(self,word):
        node=self.locate(word)
        return node is not None and None in node
    def starts_with(self,prefix):
        return self.locate(prefix) is not None
    def matches(self,pattern):
        def visit(node,i):
            if i==len(pattern): return None in node
            char=pattern[i]
            if char=='.':
                return any(visit(child,i+1) for key,child in node.items() if key is not None)
            return char in node and visit(node[char],i+1)
        return visit(self.root,0)

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

t=Trie()
for word in ['cat','car','dog']: t.insert(word)
assert t.contains('cat') and not t.contains('ca')
assert t.starts_with('ca') and not t.starts_with('z')
assert t.matches('c.t') and not t.matches('c..s')
t.insert(''); assert t.contains('')

CHECK YOUR UNDERSTANDING