I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient in this data structure describe this procedure?

  • $\begingroup$ Can you treat insertion at an index as a special case of concatenation? $\endgroup$ – D.W. Jul 18 '14 at 22:06
  • $\begingroup$ Probably I should. Found this new thesis today about RRB trees: hypirion.com/musings/thesis Will see if it will be helpful. $\endgroup$ – Tvaroh Jul 21 '14 at 7:26

Currently there's no "magic trick" to do an insertAt for RRB-trees: It can be implemented by doing

concat(append(leftSlice(rrb, i), elt), rightSlice(rrb, i))

Append can (as I've shown in my thesis) be very efficient. If you don't want to focus on transients and tails, then chapter 5 explains how you modify the persistent vector append algorithm to work for RRB-trees. In short, you have to first find the path to walk, then walk and update it just as in the persistent vector, but in addition you have to update the slot sizes.

Prepend is simply a special case of concatenation.


How cool is it to be in a field and an age where Jean Niklas L'orange can answer your questions? That's a great response!

Another approach to consider is to localize the "focus". The focus is analogous to the "tail" in Rich Hickey's PersistentVector. It's a little buffer to take new items added to the vector without having to update the tree for each of those items. The difference being that the tail always comes at the end and the focus can move around.

If inserts are localized (meaning each insert is within a few indices of the previous) you can simply move the focus to where the inserts are happening. This can be great for building a tree by inserting at zero. The "insert(0)" tab of this spreadsheet shows a few RRB-Tree implementations kicking java.util.ArrayList's butt, above 100 items. Both axes are logarithmic.

It's worth noting that you can often wait until the focus is the size of the strict-node-length and push it into the tree without copying it. This means you never have to deal with any non-full leaf node in a strict tree, or too-small node in a relaxed tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.