Relaxed radix balanced trees: efficient immutable vectors

Immutable vectors are a convenient data structure for func-
tional programming and part of the standard library of modern languages
like Clojure and Scala. The common implementation is based on wide
trees with a xed number of children per node, which allows fast in-
dexed lookup and update operations. In this paper we extend the vector
data type with a new underlying data structure, Relaxed Radix Balanced
Trees (RRB-Trees), and show how this structure allows immutable vector
concatenation, insert-at and splits in O(logN) time while maintaining the
index, update and iteration speeds of the original vector data structure.

They compare this new structure to finger trees, which I used for Radian’s array container:

2-3 finger trees achieve a lgN time for indexing and update while at the sametime maintaining an amortized constant time for adding items to the vector. Concatenation can be accomplished in lgN time too. Although attractive, using this data structure for vectors does compromise the 1/5 lgN time for index, making it theoretically 5 times slower.