Get the latest tech news
Relaxed Radix Balanced Trees (2024)
I’m adding immutable vectors to my language, Ivan, and needed to pick a suitable data structure to implement them. Closure uses Persistent Vectors (PVs) which support lookups, updates, and appends all in ‘effectively’ constant time.
To address the second problem, that the tree height is no longer bounded, we’ll reintroduce an invariant similar to the original Persistent Vector requirement that all nodes, except the rightmost edge, must contain MMM slots. This may not seem like much, since the trees in this example are shallow and we’re using a branching factor of 4 but we no longer need to shuffle every element in the right vector to the left which means we will be able to leave entire subtrees untouched when merging. Let’s say that we allow some constant, EEE, of additional extra search steps then the total number of slots SSS we may use to contain PPP nodes is given by the inequality S≤⌈P/M⌉+ES \le \lceil P / M \rceil + ES≤⌈P/M⌉+E.
Or read this on Hacker News