Recipe

Radix tree primer

A radix tree (also called a compact prefix tree or PATRICIA trie) is a space-optimized trie where every node that is the only child is merged with its parent. It is the data structure of choice for routing tables, longest-prefix matching, autocomplete indexes, and IP lookup. This primer walks through the shape, the three core operations, and a minimal Python sketch you can lift into production.

1.Shape and invariants

Each edge is labeled with a non-empty string. No two edges leaving the same node share a common prefix. Every internal node either marks the end of a key or has at least two children. These three invariants are what give the radix tree its compactness compared to a character-per-node trie, and they are what every insertion and deletion must restore.

2.The three operations

Lookup walks edges by matching the longest prefix of the remaining query against the edge label. Insert follows the same walk and, on a partial match, splits the offending edge into a shared head plus two tails. Delete removes the terminal mark and, if the node now has a single child, merges the edge back into its parent to restore the compactness invariant.

3.Minimal Python sketch

The skeleton below is intentionally under fifty lines. It supports insert and lookup with edge splitting. Production variants add deletion, iteration, and a tighter children container (often a sorted array or a small map keyed by first byte).

class Node:
    def __init__(self):
        self.children = {}  # first_byte -> (label, Node)
        self.terminal = False

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

    def insert(self, key):
        node = self.root
        while key:
            head = key[0]
            if head not in node.children:
                child = Node()
                child.terminal = True
                node.children[head] = (key, child)
                return
            label, child = node.children[head]
            i = 0
            while i < len(label) and i < len(key) and label[i] == key[i]:
                i += 1
            if i == len(label):
                node, key = child, key[i:]
                continue
            split = Node()
            node.children[head] = (label[:i], split)
            split.children[label[i]] = (label[i:], child)
            if i == len(key):
                split.terminal = True
            else:
                leaf = Node(); leaf.terminal = True
                split.children[key[i]] = (key[i:], leaf)
            return
        node.terminal = True