rebalance(RopeLike r) { if (!isBalanced(r)) { val leaves = Ropes.collectLeaves(r); return merge(leaves, 0, leaves.size()); } return r; } static RopeLike merge(List<RopeLike> leaves) { return merge(leaves, 0, leaves.size()); } static RopeLike merge(List<RopeLike> leaves, int start, int end) { int range = end - start; if (range == 1) { return leaves.get(start); } if (range == 2) { return new RopeLikeTree(leaves.get(start), leaves.get(start + 1)); } int mid = start + (range / 2); return new RopeLikeTree(merge(leaves, start, mid), merge(leaves, mid, end)); } Insert Definition: Insert(i, S’): insert the string S’ beginning at position i in the string s, to form a new string {{math|C1, ..., Ci, S''', Ci + 1, ..., Cm}}. Time complexity: . This operation can be done by a Split() and two Concat() operations. The cost is the sum of the three. public Rope insert(int idx, CharSequence sequence) { if (idx == 0) { return prepend(sequence); } if (idx == length()) { return append(sequence); } val lhs = base.split(idx); return new Rope(Ropes.concat(lhs.fst.append(sequence), lhs.snd)); } Index Definition: Index(i): return the character at position i Time complexity: To retrieve the i-th character, we begin a recursive search from the root node: @Override public int indexOf(char ch, int startIndex) { if (startIndex > left.weight()) { return right.indexOf(ch, startIndex - left.weight()); } return left.indexOf(ch, startIndex); } For example, to find the character at 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 ) 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" (ie "n") is the answer. (1-based index) Concat Definition: Concat(S1, S2): concatenate two ropes, S1 and S2, into a single rope. Time complexity: (or time to compute the root weight) A concatenation can be performed simply by creating a new root node with and , which is constant time. The weight of the parent node is set to the length of the left child S1, which would take time,