Rope — Efficient Text Editing

Concat

Create new root with two subtrees. O(1) time. Rebalance later if needed.

Index i

If i < weight, descend left. Else descend right with i -= weight. O(log N).

Insert

Rope insert(Rope r, int i, Rope s) {
  (left, right) = split(r, i);
  return concat(concat(left, s), right);
}

Balance maintenance

Ropes can become unbalanced. Fibonacci threshold rebalance keeps ops amortized O(log N).