Relaxed Radix Balanced Trees (2024)

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 ... Read full article.