The Radix Tree (Patricia Trie)

Why the radix tree matters

Tries are beautiful in theory and wasteful in practice. Store the single key "internationalization" in a plain character trie and you spend twenty nodes to represent a path that never branches — nineteen of them exist only to point at exactly one child. Multiply that by a dictionary of long, prefix-sharing strings and most of your memory goes to pointers that carry no decision. The radix tree fixes this with one rule: if a node has exactly one child, merge them. Every maximal run of non-branching nodes collapses into a single edge whose label is the concatenated string. What remains are only the nodes where something actually happens — a branch, or the end of a key.

The payoff is threefold. Memory drops from O(total key length) nodes to at most 2n − 1 nodes for n keys, so it no longer scales with how long your strings are. Cache behavior improves because you chase far fewer pointers per lookup. And the operations stay O(k) in the key length, which for fixed-width keys like IP addresses is a hard constant — a radix tree of a million routes answers just as fast as one of ten. That combination is exactly what a packet-forwarding fast path or a kernel page cache needs: predictable, key-length-bounded time with a memory footprint tied to the number of entries, not their bulk.

How it works, step by step

A radix tree is a rooted tree where edges, not nodes, carry the information. Each edge is labeled with a non-empty string, and no node (except a leaf) has two outgoing edges whose labels begin with the same character — that shared-prefix-uniqueness is the invariant that keeps the structure canonical and lookups deterministic.

Lookup. Start at the root with the full key. At each node, look at the first remaining character of the key and follow the edge whose label starts with it. Consume as many characters as the edge label is long, checking they match; if any character disagrees, the key is absent. Repeat until the key is exhausted. A node explicitly flagged isKey marks a stored string. Because every step eats at least one character, the walk is bounded by the key length — O(k).

Insertion. Walk down as in lookup. Three cases arise at the point where the key and the tree diverge:

• Exact edge consumed, key continues: descend to the child node and keep going, or create a fresh edge for the leftover suffix if no matching child exists.
• Edge label is a strict prefix of the remaining key: follow it and recurse on the shorter remaining key.
• Edge label and remaining key share only a partial prefix: split the edge. Introduce a new internal node at the divergence point; the old edge's leftover suffix and the new key's leftover suffix become its two children.

That edge-splitting is the whole trick. Inserting "team" into a tree whose only edge is labeled "test" splits at the common prefix "te": a new branch node holds "te" above it, with children "st" (the old key) and "am" (the new one). (The interactive visualization above shows the sibling case: inserting "team" when "tea" is already a key just grows a new "m" edge, since "tea" is a full prefix — no split needed.)

Deletion. Remove the key's terminal flag or leaf. Then restore the invariant: if the deletion leaves an internal node with a single remaining child, merge that node back into its parent by concatenating their edge labels. This is the inverse of a split and keeps the tree canonical, so two trees holding the same set of keys are always structurally identical.

Longest-prefix match and IP routing

The radix tree's killer application is longest-prefix match in packet forwarding. A routing table maps address prefixes to next hops: 10.0.0.0/8 → A, 10.1.0.0/16 → B, 0.0.0.0/0 → default. When a packet for 10.1.2.3 arrives, the router must choose the most specific prefix that covers it — the /16, not the /8.

Key the tree on the bits of the address (radix 2 — this is exactly PATRICIA). A node at depth d corresponds to a d-bit prefix, i.e. a /d. To route, walk down consuming destination-address bits and remember the deepest node along the path that is flagged as a real route. When you can descend no further, that remembered node is the longest matching prefix. The walk is bounded by the address width W — 32 bits for IPv4, 128 for IPv6 — so forwarding is O(W), a fixed cost regardless of table size. The classic 4.3BSD kernel, and early Linux, used precisely a PATRICIA trie for this; modern Linux uses fib_trie, a level-compressed variant (LC-trie) that fans several bits out at once to trade memory for fewer hops.

PATRICIA: the bit-level radix tree

PATRICIA — Practical Algorithm To Retrieve Information Coded In Alphanumeric, Donald R. Morrison, 1968 — is the radix tree taken to radix 2 with two extra refinements. First, every node stores a bit index: the position of the next bit that distinguishes the keys below it. Testing that single bit tells you whether to go left or right, so runs of shared bits are skipped without being stored — the tree never spends a node on a bit that doesn't branch. Second, PATRICIA has no null child pointers and no separate leaf nodes; keys are held at internal nodes and branches loop back via upward links, which is why a PATRICIA tree on n keys has exactly n nodes. The bit-index skip means a search does one full key comparison only at the very end to confirm the match, after O(W) cheap bit tests on the way down.

Radix tree vs standard trie vs hash table

	Radix tree (PATRICIA)	Standard trie	Balanced BST	Hash table
Lookup time	O(k)	O(k)	O(k · log n)	O(k) avg, O(k · n) worst
Nodes for n keys	≤ 2n − 1	O(total key length)	n	n slots + overhead
Edge/level holds	A string (or bit run)	One character/bit	—	—
Sorted / ordered traversal	Yes (lexicographic)	Yes (lexicographic)	Yes	No
Prefix & range queries	Native (subtree = prefix)	Native	Awkward	No
Longest-prefix match	Native, O(W)	Native, O(W)	No	No
Cache locality	Good (few nodes)	Poor (deep chains)	Moderate	Good

The headline distinction from a plain trie is that a radix tree stores strings on edges and only keeps branching nodes, whereas a trie stores one symbol per level and keeps a node for every symbol. Against a hash table, the radix tree gives up nothing on average-case lookup time yet adds ordered iteration, prefix queries, longest-prefix match, and a worst case that stays O(k) rather than degrading with collisions.

Implementation in Python

class Node:
    __slots__ = ("children", "is_key")
    def __init__(self):
        self.children = {}   # first-char -> (edge_label, child Node)
        self.is_key = False

class RadixTree:
    def __init__(self):
        self.root = Node()

    def _common_prefix(self, a, b):
        i = 0
        while i < len(a) and i < len(b) and a[i] == b[i]:
            i += 1
        return i

    def insert(self, key):
        node = self.root
        while key:
            first = key[0]
            if first not in node.children:
                # No matching edge: hang the whole remaining key here.
                leaf = Node(); leaf.is_key = True
                node.children[first] = (key, leaf)
                return
            label, child = node.children[first]
            n = self._common_prefix(key, label)
            if n == len(label):
                # Edge fully matched — descend and consume it.
                key = key[n:]
                node = child
                if not key:
                    child.is_key = True
                    return
            else:
                # Partial match: split the edge at the divergence point.
                branch = Node()
                node.children[first] = (label[:n], branch)
                branch.children[label[n]] = (label[n:], child)
                rest = key[n:]
                if rest:
                    leaf = Node(); leaf.is_key = True
                    branch.children[rest[0]] = (rest, leaf)
                else:
                    branch.is_key = True
                return
        node.is_key = True

    def search(self, key):
        node = self.root
        while key:
            first = key[0]
            if first not in node.children:
                return False
            label, child = node.children[first]
            if not key.startswith(label):
                return False   # partial mismatch — key absent
            key = key[len(label):]
            node = child
        return node.is_key

The children dictionary is keyed on the first character of each edge label, which enforces the shared-prefix-uniqueness invariant automatically — at most one edge can start with a given character. The insert path is the algorithm in miniature: match, and if the match is partial, split. For a bit-level PATRICIA over IP addresses you would replace the character dictionary with a two-way branch keyed on a stored bit index, and add the "remember the deepest flagged ancestor" logic to turn search into longest-prefix match.

Common misconceptions and pitfalls

• "O(k) means it beats a hash table." Both are O(k) to touch the key; a hash still has to hash all k characters. The radix tree wins on ordered operations — prefix scans, range queries, longest-prefix match — not on raw point-lookup speed.
• Forgetting to re-merge on delete. If deletion leaves a node with a single child, you must concatenate labels and remove the node. Skip it and the tree is no longer canonical: two equal key sets can produce different, slower trees, and prefix reasoning breaks.
• Confusing "radix" with numeric base. Here radix is the branching factor / alphabet size. A radix-2 tree branches on bits (PATRICIA); a radix-256 tree branches on bytes. It has nothing to do with radix sort's digit grouping beyond the shared idea of processing keys symbol by symbol.
• Assuming worst-case depth is small. Depth is bounded by key length, not log n. Adversarial keys sharing enormous prefixes then diverging can make paths long; the guarantee is O(k), never O(log n).
• Storing the terminal flag wrong on prefix keys. If "test" and "tester" are both keys, the internal node for "test" must carry is_key = True while also having a child edge "er". Treating every key as a leaf loses proper-prefix keys.

A short history

Morrison introduced PATRICIA in 1968 to index sparse, variable-length text keys efficiently; Knuth analyzed it in The Art of Computer Programming, Vol. 3 as a foundational compressed digital search tree. Sedgewick's Algorithms popularized the "radix tree / radix trie" framing for the multi-way generalization. The structure moved into systems software through BSD's radix.c routing table in the 1980s, then into Linux — first as the routing PATRICIA trie and the page-cache radix_tree, later refined into fib_trie's LC-trie and the general-purpose XArray. The modern high-performance descendant is the Adaptive Radix Tree (ART) from Leis, Kemper, and Neumann (2013), which varies node fan-out (4, 16, 48, 256) to stay cache-friendly and is used inside main-memory databases. Same 1968 idea; still the backbone of prefix search nearly sixty years on.