How to split a rope tree?

Question

I came across a rope tree as an alternative data structure for a string.

http://en.wikipedia.org/wiki/Rope_(data_structure)

To concat is easy, but I am stuck on the split operation. The wikipedia article states:

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 the right child of G. Go to the parent G and subtract the weight of K from the weight of G. Travel up the tree and remove any right links, subtracting the weight of K from these nodes (only node D, 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.

Locating the character and recombining the orphans is no problem. But I don't understand the "Travel up the tree and remove any right links, subtracting the weight of K from these nodes". The example stops at D, but if you follow these instructions verbatim you would continue onto B and remove D as well. What is the correct stopping requirement in this algorithm? And how do you avoid nodes with only one (left or right) child?

A pseudo-code algorithm explaining this part would help tremendously.

Answer 1

The wikipedia article is not very explicit. If the current node is X and its parent is Y you would only travel up if X is the left child of Y. Visually you're going up and to the right as far as you can.