if the tree is balanced. As most rope operations require balanced trees, the tree may need to be re-balanced after concatenation. Split Definition: Split (i, S): split the string S into two new strings S1 and S2, and . Time complexity: There are two cases that must be dealt with: The split point is at the end of a string (i.e. after the last character of a leaf node) 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. public Pair<RopeLike, RopeLike> split(int index) { if (index < weight) { val split = left.split(index); return Pair.of(rebalance(split.fst), rebalance(new RopeLikeTree(split.snd, right))); } else if (index > weight) { val split = right.split(index - weight); return Pair.of(rebalance(new RopeLikeTree(left, split.fst)), rebalance(split.snd)); } else { return Pair.of(left, right); } } Delete Definition: Delete(i, j): delete the substring , from s to form a new string . Time complexity: . 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. @Override public RopeLike delete(int start, int length) { val lhs = split(start); val rhs = split(start + length); return rebalance(new RopeLikeTree(lhs.fst, rhs.snd)); } Report Definition: Report(i, j): output the string . Time complexity: To report the string , find the node u that contains