Data Structures · Cluster
Tries and Radix Structures
Prefix sharing and compressed keys.
- 01 Child Representation and the Branching Factor Problem in Tries A trie costs one child lookup per key byte, so the node layout decides memory and speed. Compares dense arrays, sorted and linked child lists, bitmaps with rank, and double-array layouts.
- 02 Marking Key Boundaries in a Trie A trie node must distinguish a prefix from a stored key. The terminal marker costs one bit, one child slot, or one pointer depending on layout, and each choice changes lookup and iteration.
- 03 Lexicographic Enumeration and Range Scans over a Trie A trie yields keys in sorted order without a sort step. How depth-first traversal, ordered child storage, and iterator state interact, and why range scans cost what they cost.
- 04 Path Compression and the Patricia Trie Single-child chains inflate a trie by one node per byte. Patricia compression stores only branching nodes plus a skip value, changing lookup, insertion, and deletion in specific ways.
- 05 Radix Trees over Fixed-Width Integer Keys Indexing by bit fields instead of by bytes turns a trie into a fixed-height array of tables. Why integer radix trees need no rebalancing, how their height is computed, and where they lose to hash tables.
- 06 Adaptive Radix Tree Node Layouts ART keeps fan-out high without paying a 256-way node per prefix: four node widths, a 256-entry indirection table, path compression inside the header, and lazy expansion of leaves.
- 07 Multibit Tries and Longest-Prefix Matching for Address Lookups Walking one bit per level is too slow for router tables. Stride compression, prefix expansion, and stored prefix lengths trade table size against lookup depth under a fixed memory budget.
- 08 Concurrent Readers on a Mutating Trie Lookups traverse many dependent loads, so per-node locking is untenable. How publish-then-swap, deferred reclamation, and path copying keep readers safe while nodes grow and split.
- 09 From Suffix Trie to Suffix Array: Implicit Nodes and Intervals A suffix trie over a text is quadratic in nodes; a suffix tree keeps only branching positions; a suffix array replaces the nodes with sorted offsets plus an LCP array. What is gained and lost at each step.
- 10 Subtree Deduplication and the DAWG Two trie nodes with identical subtrees are indistinguishable, so one of them is redundant. Bottom-up merging turns a trie into a DAG whose size depends on the number of distinct suffixes, not prefixes.