↩ back to Node-Linked Trees

Rope Rebalancing

Rope's own Pitfalls section measured a real problem and named its fix without building it: appending one character at a time — the exact pattern a naive "type a letter, splice it on" text editor would produce if it never rebuilt anything — degrades a 1,000-character rope from depth 9 (its properly built shape) to depth 1,000, a fully right-leaning chain, with every operation now paying the full O(n) cost a rope exists to avoid, and nothing about the API signals it happened. That page named the real fix without building it: "real rope implementations... 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." This page is that algorithm, from the original Boehm/Atkinson/Plass 1995 "Ropes: An Alternative to Strings" paper.

The core idea: instead of requiring a rope to be perfectly balanced (which would need real rotation logic, the way an AVL tree keeps every subtree within one level of its sibling), allow it to be looser — as deep as a Fibonacci-based bound permits — in exchange for a rebalancing procedure that's just one linear pass over the leaves, no rotations at all. The tradeoff is measured directly below: this page's rebalance produces trees averaging about 1.27× as deep as the tightest possible bound, not the perfectly-balanced 1.0×, but still strictly O(log n) and built in O(m) time for m leaves, with no per-node bookkeeping required between rebalances.

Try it

Degenerate build reproduces the parent page's own pathological pattern: it splices the text field's contents onto the rope one character at a time via plain concat, no balancing at all, up to 20 characters so the resulting staircase stays on-screen. Rebalance runs the algorithm below on whatever tree currently exists and re-renders it. Nodes outlined in the accent color are ones rebalancing actually created — watch how many of them there are relative to the tree's total size. The stats line shows the exact Fibonacci minimum length the current depth requires, so "balanced: no" always comes with the number that explains it.

The Fibonacci bound

Define the Fibonacci numbers the usual way: F[0] = 0, F[1] = 1, F[i] = F[i-1] + F[i-2]. The classic definition of "balanced" (Boehm/Atkinson/Plass) counts a leaf as depth 0; this site's own ropeDepth (used throughout Rope's own page) counts a leaf as depth 1 instead, so the formula below shifts by one to match: a rope of depth d (this site's convention) is balanced if its length is at least F[d+1] - 1. That threshold grows fast — F[11]-1 = 88 at depth 10, F[16]-1 = 986 at depth 15, F[21]-1 = 10945 at depth 20 — which is exactly what makes it useful as a trigger: a tree that's gotten pathologically deep for its length fails the check almost immediately, while a tree built and edited normally almost never does. Checked directly: 200 freshly-built ropes at random lengths from 1 to 3,000 characters all satisfy the bound (200/200), and 200 deliberately degenerate ropes (built one character at a time, the parent page's own pattern) all fail it (200/200) — the check reliably tells the two shapes apart.

The rebalance algorithm

Rebalancing a subtree happens in two passes, both O(m) for m leaves, no rotations:

• Collect. Walk the tree in order (identical shape to toString, but pushing leaf references onto an array instead of concatenating text) to get every leaf, left to right, in a flat list.
• Carry-merge. Maintain an array of "slots," one per Fibonacci bucket. Feed the leaves into it one at a time: for each new leaf, walk up from slot 0, and as long as a slot is occupied, concatenate its contents onto the left of the leaf being carried and empty that slot — exactly a binary counter's carry propagation, except merging ropes instead of adding bits. The carry stops at the first empty slot, which absorbs the (possibly now-merged) result. This is the same array-indexed "merge anything sharing a bucket" trick this site's own Fibonacci Heap page uses in its own consolidate() step, just keyed by accumulated length instead of node degree.

Once every leaf has been fed in, the slots hold a handful of subtrees — at most one per Fibonacci bucket, so O(log n) of them — with lower-indexed slots holding more recently processed (rightward) content and higher-indexed slots holding content accumulated earlier (leftward). The final tree is their concatenation from the highest occupied index down to the lowest, each one attached to the left of everything assembled so far, which is what puts every character back in its original order. The direction of every one of those concatenations is load-bearing — see the first pitfall below.

Reference implementation

Reuses Rope's own makeLeaf, makeInternal, ropeConcat, and ropeDepth unchanged. Everything here is new:

// F[0] = 0, F[1] = 1, F[i] = F[i-1] + F[i-2]
const FIB = [0, 1];
while (FIB.length < 100) FIB.push(FIB[FIB.length - 1] + FIB[FIB.length - 2]);

// this site's ropeDepth() counts a leaf as depth 1, not the textbook's depth 0 —
// shift by one to match the classic length >= F[depth+2] (0-indexed) bound.
function minLengthForDepth(d) {
  return FIB[d + 1] - 1;
}

function isBalanced(node) {
  if (node === null) return true;
  return node.length >= minLengthForDepth(ropeDepth(node));
}

function collectLeaves(node, out) {
  if (node === null) return;
  if (node.leaf !== null) { out.push(node); return; }
  collectLeaves(node.left, out);
  collectLeaves(node.right, out);
}

function rebalance(node) {
  if (node === null || node.leaf !== null) return node;
  const leaves = [];
  collectLeaves(node, leaves);

  const slots = [];
  for (const leaf of leaves) {
    let tmp = leaf;
    let i = 0;
    while (slots[i] != null) {
      tmp = ropeConcat(slots[i], tmp); // earlier (leftward) content goes on the left
      slots[i] = null;
      i++;
    }
    slots[i] = tmp;
  }

  let result = null;
  for (let i = slots.length - 1; i >= 0; i--) {
    if (slots[i] != null) result = ropeConcat(result, slots[i]);
  }
  return result;
}

Verified against a plain-string oracle two ways: 2,000 random strings (1-60 characters) built pathologically, one character at a time, then rebalanced — 0/2,000 mismatches against the original string. Separately, 2,000 random strings put through 5-24 interleaved insert/delete operations each with a rebalance call fired after roughly 30% of them (so the tree is repeatedly mid-restructure when the next edit lands, not just rebalanced once at the end) — 0/2,000 mismatches, ~29,000 operations total. Depth reduction measured directly across ten sizes from 50 to 10,000 characters, comparing the pathological (one-char-at-a-time) depth, the post-rebalance depth, and the tight theoretical bound logφ(n / LEAF_SIZE): rebalanced depth ran from 8 (n=50) to 18 (n=10,000) against a pathological depth exactly equal to n every time, averaging 1.27× the tight bound (range 1.11×-1.52× across the ten sizes) — consistently close, never degenerate, never perfectly tight either, the expected shape for a bound this loose.

Pitfalls

Getting the merge direction backward corrupts the text, silently and completely, every time. The carry step above concatenates an occupied slot's contents onto the left of the leaf being carried (ropeConcat(slots[i], tmp)), because the slot holds earlier (more leftward) content than the leaf currently being fed in. Swapping that one call to ropeConcat(tmp, slots[i]) looks like a harmless argument-order slip, but it reverses the relative order of every merged chunk. Checked directly: rebalancing 500 random pathological ropes (5-45 characters) with the swapped version corrupts the text in 500/500 trials (100%) — never crashes, never a partial match, always a fully wrong string, since ropeConcat itself doesn't know or care what order its arguments arrive in. Concrete example: "the quick brown fox" rebalances to " nworb kciuq ehtofx" — not reversed, not scrambled randomly, but every Fibonacci-bucket-sized chunk correctly reconstructed internally and then stitched back together in the wrong order, exactly the failure mode "it still looks kind of like the input" bugs are most dangerous for.

Rebalancing after every single edit instead of only when isBalanced fails throws away the near-total structural sharing the parent page measured. Rope's own page built a 2,000-character rope (1,023 nodes total) and showed a single targeted insert creates only a handful of new nodes, reusing everything else unchanged. Reproduced here with the identical setup: a plain insert with no rebalancing creates 3 new nodes out of 1,023. The same insert followed by an unconditional rebalance — a reasonable-looking "just always call it to be safe" habit — creates 513 new nodes instead, effectively rebuilding half the tree for a one-character edit. This isn't a correctness bug: rebalance never mutates existing nodes, so older rope versions kept around stay perfectly valid either way, unlike the persistence-breaking pitfall on the parent page. It's a pure performance own-goal — the entire reason isBalanced exists as a cheap (O(depth), reading only cached .length fields, no tree walk) gate is to pay the O(m) rebalance cost only when the tree has actually gotten bad enough to need it.

Complexity

Time: rebalance is O(m) for a subtree with m leaves — one pass to collect them, one pass to carry-merge them, both linear, no rotations. isBalanced is O(d) (really O(1) plus one ropeDepth walk, itself O(d), since every node already caches its own length). Depth after rebalancing is O(log_φn), measured above at 1.11×-1.52× (1.27× average) the tight bound across sizes from 50 to 10,000 characters — worse than a perfectly balanced tree's O(log₂n) by a constant factor (φ ≈ 1.618 < 2, so the Fibonacci bound tolerates more depth for the same length), in exchange for needing no rotation logic at all.

How often the trigger fires depends entirely on the edit pattern. Under the worst continuous adversarial case — always prepending a single character at position 0, the pattern most likely to keep pushing one side of the tree deeper — a freshly balanced 1,000-character rope's isBalanced check fails again after just 7 more prepends; a just-rebalanced tree (already under some prior degeneracy) fails after 4. That's not a long amortized runway, and it isn't supposed to be one: the Fibonacci bound caps how bad depth can ever get, not how rarely you're forced to pay for a rebalance under sustained targeted pressure. Under a more realistic pattern — 500 inserts of 1-3 random characters at uniformly random positions — the check fires noticeably less often but still regularly: 121/500 times at n=500 (24.2%), 97/500 at n=1,000 (19.4%), 80/500 at n=2,000 (16.0%), each rebalance only ever costing O(m) for whatever the tree's current leaf count is. Space: O(m) new nodes per rebalance, same bound as an insert or delete on the parent page — never more than the number of leaves being reassembled.