> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures/adaptive_radix_tree.md).

# Adaptive Radix Tree

## Basic idea

A radix tree whose internal nodes adapt their fan-out (4/16/48/256) to actual key density at each level. Keeps the cache-friendliness of dense arrays for hot nodes while bounding memory for sparse ones. Comparable to hash tables but ordered.

## Key formulas

* Lookup/insert/delete: $O(k)$ where $k$ is key length in bytes (independent of $n$)
* Space: $O(n \cdot k)$ worst-case, much less in practice
* Node sizes: 4 / 16 / 48 / 256 entries