R-way trie

Cost and properties

search hit	O(L) — key length
search miss	sublinear — often 1–2 characters
space	R links per node
extras	prefix and wildcard queries

Reference: Sedgewick & Wayne, §5.2; Fredkin 1960.

R-way trie in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class TrieST:
    # Nodes hold no key: THE KEY IS THE PATH from the root. A node's value
    # is set only if the path to it spells a key that was inserted.
    R = 26                                # 'a'..'z' in this demo

    class _Node:
        __slots__ = ('val', 'next')
        def __init__(self):
            self.val = None
            self.next = [None] * TrieST.R

    def __init__(self):
        self.root = None

    def _index(self, c):
        return ord(c) - ord('a')

    def put(self, key, val):
        self.root = self._put(self.root, key, val, 0)

    def _put(self, x, key, val, d):
        if x is None:
            x = TrieST._Node()            # create the node we walked into
        if d == len(key):
            x.val = val                   # end of key: store the value HERE
            return x
        c = self._index(key[d])
        x.next[c] = self._put(x.next[c], key, val, d + 1)
        return x

    def get(self, key):
        x = self._get(self.root, key, 0)
        return None if x is None else x.val

    def _get(self, x, key, d):
        if x is None:
            return None                   # no link: the key is absent
        if d == len(key):
            return x
        return self._get(x.next[self._index(key[d])], key, d + 1)

Why it works

Nothing is stored in a node

A trie node holds only a value slot and R links. The characters live on the links, so the key is spelled out by the path taken to reach a node — which means keys with a shared prefix share the nodes for that prefix, once. This is why a trie's shape reflects the structure of your key set rather than its insertion order (a BST) or a hash (a hash table).

Why search misses are so fast

A hit costs one array access per character, so O(L) for a key of length L — independent of the number of keys. A miss usually stops far sooner: as soon as a needed link is null. For a random key against a large trie the expected number of characters examined is about log_R n, which is why tries are the structure of choice for spell-checking and routing lookups.

The space problem

Every node carries R links, most of them null. With R = 256 and short keys, memory is dominated by null pointers — the classic figure is 256 links per node for a structure holding a handful of characters. The fixes are the rest of the lecture: a ternary search trie (three links per node, so space is proportional to the actual characters) or a compressed / Patricia trie that collapses one-child chains.

What tries do that hashing cannot

• Prefix queries: “all keys starting with sh” — walk to the node for sh and collect everything below. This is autocomplete.
• Longest prefix of a query: the IP-routing operation.
• Wildcards and ordered iteration.

A hash table destroys the structure of the key, so none of these are available. Choosing a symbol table is choosing which operations you want.

What to try in the animation

Lower-case letters only. Watch a search miss stop after one or two characters — that is the property no hash table or BST has.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• seashells (course) — insert: she sells sea shells by the shore · search: sea shell
• shared prefixes — insert: car cart card care cat · search: car cab
• one key is a prefix of another — insert: in inn into · search: in inner
• no shared prefixes — insert: apple banana cherry · search: apple durian

Open R-way trie in the player →