Relaxed Radix Balanced Trees
I’m adding immutable vectors to my language, Ivan, and needed to pick a suitable data structure to implement them. Clojure uses Persistent Vectors (PVs) which support lookups, updates, and appends all in ‘effectively’ constant time. However, it doesn’t have efficient insert or merge operations. Relaxed Radix Balanced (RRB) Trees, introduced by Bagwell and Rompf in 2011, address this shortcoming.
I had to read a few different papers to properly understand how they worked so I thought I’d write an introduction in the hope of making it a tad easier for others. I’ll try to convey how they work and some intuition for why, while leaving the deeper mathematical treatment to the academic papers.
I will assume you’re already familiar with how Persistent Vectors work.
Merging Persistent Vectors
Let’s suppose we merge two Persistent Vectors, giving us the following result:
Since we rely on a fixed node size ( M M M) for radix search to work, we must ensure that every node (except the right edge) has M M M children. A tree with this property is said to be leftwise dense. In this example, since the last child of the left vector only has 2 elements we must move 2 elements over from the right vector. Doing so imbalances the first child node of the right vector, so we must repeat the process with its subsequent children until all nodes are balanced. This process involves creating many new replacement nodes (shown in orange). The work that needs to be done is proportional to the size of the right vector.
Relax
We need to relax the leftwise dense constraint, but doing so will introduce two problems:
Radix search relies on each node having the same fixed branching factor. The height of the tree, which is what lets us claim ‘effectively’ constant operations, is bounded by the fixed branching factor.
... continue reading