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?
How append, prepend, and generally insertAt work in RRB-tree
trees;persistent data structure
Currently there's no magic trick to do an insertAt for RRB-trees: It can be implemented by doingconcat(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.