[Solved]: How append, prepend, and generally insertAt work in RRB-tree

Problem Detail: 

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?

Asked By : Tvaroh

Answered By : Jean Niklas L'orange

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), concat(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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28526

3.2K people like this

 Download Related Notes/Documents