Ci and , and then traverse T starting at node u. Output by doing an in-order traversal of T starting at node u. Comparison with monolithic arrays Advantages: Ropes enable much faster insertion and deletion of text than monolithic string arrays, on which operations have time complexity O(n). Ropes don't require O(n) extra memory when operated upon (arrays need that for copying operations). Ropes don't require large contiguous memory spaces. If only nondestructive versions of operations are used, rope is a persistent data structure. For the text editing program example, this leads to an easy support for multiple undo levels. Disadvantages: Greater overall space use when not being operated on, mainly to store parent nodes. There is a trade-off between how much of the total memory is such overhead and how long pieces of data are being processed as strings. The strings in example figures above are unrealistically short for modern architectures. The overhead is always O(n), but the constant can be made arbitrarily small. Increase in time to manage the extra storage Increased complexity of source code; greater risk of bugs This table compares the algorithmic traits of string and rope implementations, not their raw speed''. Array-based strings have smaller overhead, so (for example) concatenation and split operations are faster on small datasets. However, when array-based strings are used for longer strings, time complexity and memory use for inserting and deleting characters becomes unacceptably large. In contrast, a rope data structure has stable performance regardless of data size. Further, the space complexity for ropes and arrays are both O(n). In summary, ropes are preferable when the data is large and modified often. See also The Cedar programming environment, which used ropes "almost since its inception" The Model T enfilade, a similar data structure from the early 1970s. Gap buffer, a data structure commonly used in text editors that allows efficient insertion and deletion operations clustered near the same location Piece table, another data structure commonly used in text editors References External links "absl::Cord" implementation of ropes within The Abseil library "C cords" implementation of ropes within the Boehm Garbage Collector library SGI C++ specification for ropes (supported by STLPort and libstdc++) Ropes for C# ropes for Common Lisp Ropes for Java String-Like Ropes for Java Ropes for JavaScript Ropes for Limbo ropes for Nim Ropes for OCaml pyropes for Python Ropes for Smalltalk SwiftRope for Swift "Ropey" for Rust