Rope

A rope is a binary tree where leaves are short strings.

              [concat]
              /       \
        [concat]      "fox"
        /       \
   "The "    "quick brown "

Logical text: "The quick brown fox".

Each internal node stores: total length of left subtree (cached). Lookups by position do binary search through tree.

Operations:

• Index character at position: O(log n).
• Concatenate ropes: O(1) — just create new parent.
• Insert: split at pos, rope-concat 3 parts. O(log n).
• Delete range: similar.
• Substring: walk tree extracting overlapping leaves. O(log n + result length).

Balanced rope (e.g., AVL): keeps depth O(log n).

Splitting:

Insert at pos:

Pros:

• O(log n) for all ops.
• No buffer locking; just create new tree.
• Trivially supports multiple versions (persistent data structure).

Cons:

• Memory: each node has overhead.
• Cache-unfriendly (pointer chasing).
• Modern CPUs prefer linear data.

Used by:

• Xi editor (Google, abandoned).
• Some VCSes for diff/merge.
• Some functional languages (immutable strings).

Trade-offs:

• Rope: best for huge files + multi-version.
• Piece table: best for sequential edits, easy undo.
• Gap buffer: best for single-cursor, smaller files.

Most modern editors (VS Code, Sublime, JetBrains) use piece tables.