Persistent Rope

A rope is a balanced binary tree for strings:

• Leaves store string chunks
• Internal nodes store length of left subtree

Ropes support efficient:

• Concatenation: $O(\log n)$ by creating new root
• Split: $O(\log n)$ by path copying
• Index access: $O(\log n)$ using lengths

Persistent ropes enable undo/redo in text editors:

versions := []
function edit(version, pos, text)
    newRope := insert(versions[version], pos, text)
    versions.append(newRope)

function undo()
    return versions[len(versions) - 2]

Each edit creates a new version sharing most of the old rope.