Meetings With Remarkable Trees - Bodil Stokke

Everybody knows the classic cons list. Clojeurs brag about their bitmapped vector tries. Haskell weenies took it up a notch with their impossible finger trees. Rustaceans turned back the clock and gave us simple arrays again.
All of these have shortcomings. Hickey tries are magically indexable but the only other thing you can do to them is add things to the end. Finger trees are absurdly flexible but you can’t index them efficiently. And so the search goes on…
And today, you’re going to learn about the ultimate list data structure: the RRB tree (“relaxed radix balanced tree”) is an improved version of the tried and tested Hickey trie, which has achieved the impossible: every basic operation is efficient - push and pop on either end, index lookup, split and join. RRB trees pull no punches.
Watch as Bodil shows you diagrams with brightly coloured boxes in an enthusiastic effort to explain why RRB trees are amazingly exciting.

[@LinusBerglund]

So, if I read the Bagwell paper correctly, the invariant for rrb trees would be node sizes of m to m-1 (for 5 bits, 32 and 31). But how hard do we need to maintain the invariant?? Dropping elements at the front means you could end up with the most leftwise branch containing 1 element - and a rebalance would be expensive. Insertion could lead to the same problem.