A spell-checker must search a large set of words, many of which share prefixes. A trie shares those prefixes, but a long stretch with no branch can leave a chain of nodes that serve only as steps toward a key. A radix trie compresses that chain into one edge labeled with a substring rather than a single character. section 6.0 section 6.3
Figure 6.12 Path compression in tries, by merging together edges adjacent to pass-through nodes. Notice that edges in radix tries are labeled with strings, not just characters.
The diagram shows which pass-through nodes disappear when adjacent edges are merged, and why the resulting edges carry strings. section 6.3
Keep nodes that mark stored keys or divide into branches; compress intermediate nodes that neither store a key nor offer a choice. Each node records whether its path is a key. Each outgoing edge holds a label and a destination node. No two edges from the same node share a starting character, so that character identifies the only possible next edge. section 6.3 section 6.3.1
Operations must compare the remaining query with whole edge labels, not just their first characters:
- Exact search follows an edge only when its entire label matches the next part of the query. Once the query is exhausted, it succeeds only at a node marked as a key. section 6.3.2
- Removal first finds a fully matching key, unmarks it, prunes a resulting leaf if needed, and merges edges if cleanup creates a pass-through node. section 6.3.4
- Longest-stored-prefix search remembers marked nodes along a matching path. To list keys starting with a query prefix, also accept a query that ends partway through an edge and traverse its destination subtree. section 6.3.5 section 6.3.6
A prefix without a node
A radix trie can contain words beginning with “anth” even when the path spelling “anth” ends in the middle of an edge. Exact search does not treat that point as a stored key; a keys-starting-with-prefix query continues from the edge’s destination to collect matching words. section 6.3.2 section 6.3.6
Compression reduces unnecessary nodes while retaining trie-style string and prefix queries. It does not eliminate label-comparison work: each candidate edge may contain several characters. Outgoing edges can be kept in a sorted array or in a map keyed by their first character; that choice trades lookup and update behavior against representation costs. The treatment characterizes radix tries as more compact than ordinary tries without a complexity or performance compromise. section 6.3.1 section 6.5
