↩ back to Node-Linked Trees

Rope

A plain string is fast to index (s[i], one address computation) but expensive to edit in the middle: JavaScript strings are immutable, so s.slice(0, i) + x + s.slice(i) copies the entire string just to insert a few characters, and concatenating two long strings copies both of them into a third. A linked list of characters fixes the mid-edit cost — splice in a node, relink two pointers — but gives up indexing entirely: finding character 500 means walking 500 pointers one at a time. A rope gets close to both: instead of one contiguous block or one character per node, it stores the string as a binary tree whose leaves hold small chunks of text, and whose internal nodes cache just enough information — the total length of everything under their left child, called the node's weight — to route an index lookup, or a split at a given position, straight down one root-to-leaf path without ever measuring the whole string.

The payoff shows up most in the two operations a flat string is worst at. Concatenation is O(1): joining rope a and rope b is just allocating one new internal node with left = a, right = b, and weight = length(a) — no characters move. Splitting at any position is O(log n): descend the tree once, and at each internal node either the whole subtree belongs to one side (nothing to do) or the split has to continue one level deeper — never more than the tree's depth. Insert and delete are both built entirely out of split and concat, so they inherit the same O(log n) bound, no matter how long the string is or how close to the middle the edit lands.

Try it

Builds new chunks are capped at 4 characters per leaf (LEAF_SIZE), so even a short string shows real tree structure. Build replaces the whole rope with the text field's contents, splitting it in half recursively until every chunk fits. Char at walks down using the index field, highlighting the path. Insert splices the text field's contents in at index; Delete removes count characters starting at index. Nodes outlined in the accent color are ones the last operation actually created — everything else in the tree is the exact same node object as before, reused unchanged. The default 16-character rope is small enough that an edit touches most of it; build a longer string first (up to 40 characters) and insert into the middle of that instead — the outlined fraction shrinks fast as the tree grows, which is the whole point.

Core operations

• index(node, i) — at a leaf, return character i of its chunk directly. At an internal node, compare i against weight (the left subtree's total length): if i < weight the target character is on the left, recurse there with i unchanged; otherwise it's on the right, recurse with i - weight — the same "subtract what you skipped" shift a Fenwick Tree or binary lifting jump makes, just over string length instead of a numeric index.
• split(node, i) — returns two ropes, everything before position i and everything from i on. At a leaf, slice the chunk in two (or hand the whole leaf to one side, if i lands exactly on a boundary). At an internal node, the split has to recurse into whichever child straddles position i, then reattach the untouched half of that recursive result to the untouched sibling with concat — so a split touches exactly the nodes on one root-to-leaf path, and reuses every other subtree as-is.
• concat(a, b) — one new internal node, left = a, right = b, weight = length(a). Handles a or b being empty (null) as a special case so trees never accumulate dead empty branches.
• insert(node, i, str) — split at i, build a small rope out of str, and concat all three pieces back together left-to-right.
• delete(node, i, count) — split at i, split the remainder again at count to peel off the doomed piece, then concat the two surviving pieces, discarding the middle.
• toString(node) — the one O(n) operation: an in-order walk (every leaf, left to right) concatenating chunks back into a flat string, needed only when the actual text has to leave the tree — printing it, sending it over a wire, handing it to a regular-expression engine.

Reference implementation

const LEAF_SIZE = 4;

function makeLeaf(s) {
  return { leaf: s, left: null, right: null, weight: s.length, length: s.length };
}
function makeInternal(left, right) {
  return { leaf: null, left, right, weight: left.length, length: left.length + right.length };
}

function buildRope(s) {
  if (s.length === 0) return null;
  if (s.length <= LEAF_SIZE) return makeLeaf(s);
  const mid = Math.ceil(s.length / 2);
  return makeInternal(buildRope(s.slice(0, mid)), buildRope(s.slice(mid)));
}

function ropeIndex(node, i) {
  if (node.leaf !== null) return node.leaf[i];
  if (i < node.weight) return ropeIndex(node.left, i);
  return ropeIndex(node.right, i - node.weight);
}

function ropeConcat(a, b) {
  if (a === null) return b;
  if (b === null) return a;
  return makeInternal(a, b);
}

function ropeSplit(node, i) {
  if (node === null) return [null, null];
  if (node.leaf !== null) {
    if (i <= 0) return [null, node];
    if (i >= node.length) return [node, null];
    return [makeLeaf(node.leaf.slice(0, i)), makeLeaf(node.leaf.slice(i))];
  }
  if (i < node.weight) {
    const [ll, lr] = ropeSplit(node.left, i);
    return [ll, ropeConcat(lr, node.right)];
  } else if (i > node.weight) {
    const [rl, rr] = ropeSplit(node.right, i - node.weight);
    return [ropeConcat(node.left, rl), rr];
  } else {
    return [node.left, node.right];
  }
}

function ropeInsert(node, i, s) {
  const [l, r] = ropeSplit(node, i);
  return ropeConcat(ropeConcat(l, buildRope(s)), r);
}

function ropeDelete(node, i, count) {
  const [l, rest] = ropeSplit(node, i);
  const [, r] = ropeSplit(rest, count);
  return ropeConcat(l, r);
}

function ropeToString(node) {
  if (node === null) return '';
  if (node.leaf !== null) return node.leaf;
  return ropeToString(node.left) + ropeToString(node.right);
}

Every node caches both fields it needs — a leaf caches its own length, an internal node caches weight (left subtree length) and length (both subtrees combined) once, at construction — so nothing above ever re-walks a subtree just to ask how long it is; root.length alone answers "how long is this whole rope" in O(1). Verified against a plain-string oracle: 300 random strings (1-30 characters), each put through 100 interleaved index/insert/delete/ split-then-reconcat operations (30,000 operations total), comparing ropeToString against the oracle string after every single one, plus a standing invariant checked after every operation that ropeToString(rope).length always matches the cached root.length field. 0 mismatches. Separately measured the structural-sharing claim made above: building a rope from a random 2,000-character string (1,023 nodes total, depth 10) and inserting 8 characters in the middle creates exactly 5 new node objects — everything else in the result, all 1,018 other nodes, is the identical object reference from before the insert, not a copy. See /tmp/rope_verify.js, /tmp/rope_pitfall.js, and /tmp/rope_persist.js, scratch, not committed.

Pitfalls

The weight comparison's strict inequality is load-bearing, and getting it wrong fails silently. index and split both have to route "exactly at the boundary" (i === weight) to the right subtree, since weight counts positions 0 through weight - 1 as left. Changing ropeIndex's check from i < node.weight to i <= node.weight looks like a harmless off-by-one, but it sends every boundary index into the left subtree at one position past where that subtree's characters actually end. Verified directly on "the quick brown fox" (19 characters, no trailing letter needing a bounds check): the broken version returns undefined for 6 of 19 characters (31.6%) — every single one a boundary case — and never throws, since leaf[weight] on a leaf whose chunk has exactly weight characters is simply undefined in JavaScript, not an error. A caller trusting the return value gets a silently wrong string with a hole in it, not a crash pointing at the bug.

Nothing above rebalances, so an adversarial edit pattern degrades the tree to a linked list. buildRope only produces a balanced tree once, at construction; every later concat just grafts two subtrees together exactly as given, with no check on the result's shape. Verified concretely: building the same 1,000-character string in one shot gives a tree of depth 9 (log₂(1000/4) ≈ 7.97, matching the balanced-build bound), but appending it one character at a time — 1,000 separate single-character ropeConcat calls, the pattern a naive "type one letter, append it" text editor would produce if it never rebuilt anything — gives a tree of depth 1,000, a fully degenerate right-leaning chain. Every operation on that tree is now O(n), the exact cost a rope exists to avoid, and nothing about the API signals it happened. Real rope implementations (the original Boehm/Atkinson/Plass 1995 "Ropes: An Alternative to Strings" paper, and SGI's Cord library that shipped alongside it) rebalance periodically using a Fibonacci-sequence-based height bound — not covered here, since it's a genuinely separate algorithm layered on top of split/concat/insert/delete rather than a variation on them.

Splitting and concatenating never copy a leaf's text — which means mutating a leaf in place corrupts every other rope that still references it. This implementation is persistent by construction, the same "path copying" this site's Persistent Segment Tree page names directly: an edit only ever allocates new nodes on the one path it touches, so an older rope kept around after a concat or insert stays valid forever, sharing every untouched node with the new one. That guarantee depends entirely on never writing to an existing leaf's .leaf string field — and a "fast path" implementation tempted to patch a short leaf chunk directly, instead of allocating a fresh one, breaks it. Verified concretely: build v1 = buildRope("Dear team, the report is attached."), then v2 = ropeConcat(v1, buildRope(" -- Alex")) — a natural "draft, then draft-plus- signature" version pair sharing v1's entire tree. Patching a single character into v2 at index 4 via direct leaf mutation (rather than split-then-new-leaf-then-concat) changes v1 too: it silently becomes "DearX team, the report is attached.", even though nothing in the code ever named v1 in that edit. The version someone thought they'd kept untouched was never actually independent.

Where ropes show up

• Large-document text editor buffers. The whole reason ropes exist: editing the middle of a multi-megabyte file has to stay fast regardless of where the cursor is, and a flat string or plain array forces an O(n) shift on every keystroke. Rust's ropey crate (used by the Helix and Xi text editors) and the original SGI Cord C library both exist specifically for this.
• Building up huge strings from many small pieces without quadratic blowup. Repeatedly doing s = s + chunk on a flat immutable string is the classic O(n²) anti-pattern for exactly this task — each + copies everything accumulated so far. A rope's O(1) concat turns the same loop into O(n) total work, one allocation per chunk instead of one copy of everything-so-far per chunk.
• Any version-history or undo/redo stack over large text. Because split, concat, insert, and delete are all non-destructive by construction (see the third pitfall above), every prior version of the text is already a valid, cheaply-kept-around rope with no extra copying beyond the handful of nodes each edit actually created — the same path-copying payoff Persistent Union-Find and Persistent Segment Tree get from the identical technique over different data.

Complexity

Time: on a rope of depth d holding n characters in chunks of at most LEAF_SIZE, index and split are both O(d) — one root-to-leaf walk, and a balanced tree keeps d = O(log(n / LEAF_SIZE)) (measured above: depth 9 for n = 1,000 against a log₂(1000/4) ≈ 7.97 bound). concat is O(1) unconditionally — it never looks inside either subtree, just wraps them. insert and delete are each one or two splits plus one or two concats, so they inherit split's O(d) bound. toString is O(n), visiting every leaf once — unavoidable, since materializing the text has to touch every character exactly once no matter how it's stored. None of the O(d) = O(log n) bounds above hold without periodic rebalancing (see the second pitfall): a pathological edit sequence can push d as high as O(n), at which point every operation degrades to the same cost a flat string or linked list would give directly. Space: a freshly built rope uses O(n / LEAF_SIZE) leaves plus roughly as many internal nodes, O(n) total — but because every operation is persistent (third pitfall above), keeping k successive versions of a rope alive costs the original O(n) plus only O(d) new nodes per edit, not O(n) per version the way keeping k full string copies would.

This site's guide, Choosing a Search Tree, sets this entry aside from the seven it actually compares: it isn't about a set of keys at all — it holds one mutable-feeling string, and answers index, split, or join queries on that text, a question none of the seven comparison entries even attempt.