Rope (data structure)

Definition: Insert(i, S’): insert the string S’ beginning at position i in the string s, to form a new string C₁, …, C_i, S', C_{i + 1}, …, C_m.

Time complexity: ${\displaystyle O(\log N)}$.

This operation can be done by a Split() and two Concat() operations. The cost is the sum of the three.

Figure 2.1: Example of index lookup on a rope.

Definition: Index(i): return the character at position i

Time complexity: ${\displaystyle O(\log N)}$

To retrieve the i-th character, we begin a recursive search from the root node:

function index(RopeNode node, integer i)
  if node.weight <= i and exists(node.right) then
    return index(node.right, i - node.weight)
  end
  
  if exists(node.left) then
    return index(node.left, i)
  end
  
  return node.string[i]
end

For example, to find the character at i=10 in Figure 2.1 shown on the right, start at the root node (A), find that 22 is greater than 10 and there is a left child, so go to the left child (B). 9 is less than 10, so subtract 9 from 10 (leaving i=1) and go to the right child (D). Then because 6 is greater than 1 and there's a left child, go to the left child (G). 2 is greater than 1 and there's a left child, so go to the left child again (J). Finally 2 is greater than 1 but there is no left child, so the character at index 1 of the short string "na", is the answer.

Figure 2.2: Concatenating two child ropes into a single rope.

Definition: Concat(S1, S2): concatenate two ropes, S₁ and S₂, into a single rope.

Time complexity: ${\displaystyle O(1)}$ (or ${\displaystyle O(\log N)}$ time to compute the root weight)

A concatenation can be performed simply by creating a new root node with left = S1 and right = S2, which is constant time. The weight of the parent node is set to the length of the left child S₁, which would take ${\displaystyle O(\log N)}$ time, if the tree is balanced.

As most rope operations require balanced trees, the tree may need to be re-balanced after concatenation.

Figure 2.3: Splitting a rope in half.

Definition: Split (i, S): split the string S into two new strings S₁ and S₂, S₁ = C₁, …, C_i and S₂ = C_{i + 1}, …, C_m.

Time complexity: ${\displaystyle O(\log N)}$

There are two cases that must be dealt with:

1. The split point is at the end of a string (i.e. after the last character of a leaf node)
2. The split point is in the middle of a string.

The second case reduces to the first by splitting the string at the split point to create two new leaf nodes, then creating a new node that is the parent of the two component strings.

For example, to split the 22-character rope pictured in Figure 2.3 into two equal component ropes of length 11, query the 12th character to locate the node K at the bottom level. Remove the link between K and G. Go to the parent of G and subtract the weight of K from the weight of D. Travel up the tree and remove any right links to subtrees covering characters past position 11, subtracting the weight of K from their parent nodes (only node D and A, in this case). Finally, build up the newly orphaned nodes K and H by concatenating them together and creating a new parent P with weight equal to the length of the left node K.

As most rope operations require balanced trees, the tree may need to be re-balanced after splitting.

Definition: Delete(i, j): delete the substring C_i, …, C_{i + j − 1}, from s to form a new string C₁, …, C_{i − 1}, C_{i + j}, …, C_m.

Time complexity: ${\displaystyle O(\log N)}$.

This operation can be done by two Split() and one Concat() operation. First, split the rope in three, divided by i-th and i+j-th character respectively, which extracts the string to delete in a separate node. Then concatenate the other two nodes.

Definition: Report(i, j): output the string C_i, …, C_{i + j − 1}.

Time complexity: ${\displaystyle O(j+\log N)}$

To report the string C_i, …, C_{i + j − 1}, find the node u that contains C_i and weight(u) >= j, and then traverse T starting at node u. Output C_i, …, C_{i + j − 1} by doing an in-order traversal of T starting at node u.