A trie with single-child chains compressed into string-labeled edges. Insert splits an edge where keys diverge; longest-prefix match (LPM) descends to the deepest matching stored key — the operation behind IP routing.
| Operation | Time | Notes |
|---|---|---|
| Insert (with split) | O(L) | ≤ 2 new nodes per insert |
| Search | O(L) | independent of key count N |
| StartsWith | O(L) | prefix may end mid-edge |
| Delete (with merge) | O(L) | fuse single-child node back |
| Longest-prefix match | O(L) | IP routing operation |
| Total nodes | O(N) | ≤ 2N−1, key-length independent |
| Total space | O(N + chars) | vs O(chars×Σ) for plain trie |