Radix tree - Wikipedia

Abstraction: Space-optimized trie merging single-child nodes for efficient string storage

Key points:

• Radix tree (compact prefix tree) merges nodes with only one child into their parent; edges labeled with string sequences not just single characters
• All operations (lookup, insert, delete) run in O(k) where k is maximum string length, independent of tree size n
• Comparison with balanced trees: BST comparisons are O(k) worst-case due to long common prefixes; radix tree comparisons are O(1) per node but requires m comparisons for length-m string
• Primary applications: IP routing tables, inverted indexes for information retrieval, Linux kernel page cache
• PATRICIA trie (radix-2): stores only the first differentiating bit position per node, not full keys; one node per unique key; requires one full key comparison at the end to confirm match
• Adaptive Radix Tree (ART) uses variable-size nodes based on number of children, improving space efficiency; published 2013 by Leis et al. for main-memory databases

Connections: Donald Knuth · Radix Tree · Trie · Data Structures

Source: http://en.wikipedia.org/wiki/Radix_tree