3 ms·

Can someone explain intuitively what this is?

• samatman 13y ago
  It is a tree, where the leaves are substrings, and the nodes are the sum of the lengths of all the leaves under the node. Thus, the root node has a value equal to the length of the string; it has two child nodes, with values equal to the lengths of the first and second 'half' of the string, and so on.
• inportb 13y ago
  A rope stores a long string as a collection (binary tree) of shorter strings. Strings are stored contiguously in memory, so mutation (insertion, deletion, catenation, etc) often involves much copying of data, which could be problematic with long strings. Ropes avoid this problem, but have some additional code complexity and resource overhead associated with data fragmentation.