Path Compression: Radix Tree

A trie node with one child wastes memory:

   c
   |
   o
   |
   m
   |
   p
   |
   u   (only here does it branch)
  / \
 t   l (compute, complete)

A radix tree (or patricia trie) collapses single-child chains:

   "comp"
   /    \
 "ute"  "lete"

Each edge stores a substring instead of a single char. Memory drops dramatically for natural-language data with long common prefixes.

Insertion: walk down matching prefix; SPLIT an edge if you need to diverge mid-string.

Existing: comp -> ute, lete
Insert: complete (matches "comp" + "lete")
Result: same tree, just mark "complete" node as word.

Insert: company (matches "comp", then "u" but not "ute")
Need to split "ute" edge:
  comp
   /\
  u  lete
  |\
 te  any   <- new

Linux's filesystem layer uses a radix tree for the page cache. Most TCP stacks use one for connection lookup.