Rope (data structure) - Wikipedia

data-structuresropebinary-treestring-processingtext-editing

Abstraction: Binary-tree structure for O(log n) string mutation operations

Key points:

A rope is a binary tree where leaf nodes hold fixed-length string segments; internal nodes store the total weight (length) of their left subtree
Concatenation is O(1) amortized (create new root); Index/Insert/Remove/Split are O(log n) — vs O(n) for array-based strings
Enables persistent (nondestructive) behavior via copy-on-write; supports multi-level undo in text editors
Rebalancing uses Fibonacci sequence bounds: a balanced rope of depth d requires weight >= Fibonacci(d+2)
Trade-offs: greater constant-factor space overhead for parent nodes; increased code complexity; preferred when data is large and frequently modified
Widely implemented: Ropey (Rust), absl::Cord (C++), SGI STL rope, and ports for Java, JavaScript, OCaml, Python, Nim, etc.

Connections: Data Structures · String Processing