The Radix Trees How IntMap Works
summary
Explains how IntMap implements a compressed binary trie with three constructors: Leaf(key,value), Branch(prefix,mask,left,right) and Empty, where lookups test a mask with single one bit via a fast bitwise AND to choose left or right. Shows path compression that makes operations proportional to key length, describes node-span tradeoffs (byte-at-a-time yields 256 children) and the adaptive radix tree variants (N4/N16/N48/N256) that pick node representations to reduce space without growing height. Notes a Java persistent ART benchmarks well but Haskell implementations struggle due to boxed arrays and thunk overhead.
AI-written summary · about
chapters (6)
- 0:00Start
- 0:20Radix Trees How IntMap Works
- 1:42Functional Graphs
- 4:36Practical Algorithm to Retrieve Information Coded in Alphanumeric
- 13:24Tries retrieve key character by character
- 38:23Questions?
related talks
10mFunctional Data Structures
01h 06mPostmodern immutable data structures
48mPurely Functional Data Structures
01h 32mAlgorithms for Trees - Foldable, Applicative, Traversable
24mTruly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)
47mPurely Dysfunctional Data Structures
34mImmutability: Putting The Dream Machine To Work
32mFunctional implementation of Finger Trees in JavaScript