RRB-Trees

Basic idea

Relaxed Radix Balanced trees: a persistent vector that adds $O(\log n)$ concat and split to Clojure-style 32-way trie vectors by allowing slightly-unbalanced subtrees (“relaxed” nodes carry a size table).

Key formulas

• Lookup / update / append: $O(\log_{32} n)$ — effectively constant
• Concat / split: $O(\log n)$
• Branching factor: 32

##Resources

• EPFL

Siblings

• Adaptive Radix Tree
• Bloom filter
• Cache Oblivious Algorithms & Datastructures
• Count-min sketch
• CTrie
• Disjoint Set
• Fenwick tree
• Fibonacci heaps
• Finger-Trees
• GeoHash
• Hash Array Mapped Tries
• Hash Tables
• Hilbert-R Tree
• HyperLogLog
• Judy Arrays
• k-d Tree
• Links
• M Tree
• Pairing heaps
• R tree
• Segment Trees
• Sparse Sets
• Succint Datastructures