---

1.3 Balancing a rope

As in the previous section we denote by d the depth of the rope. Ropes additionally have a length denoted by ℓ, and it is the sum of lengths of the string labels of the leaves. We say that a rope is balanced if ℓ ≥ Fib(d) where Fib(·) is the Fibonacci sequence.

Our goal is to explain why the definition is appropriate (with a caveat; see below), and then to explain the algorithm itself.

First we wish to explain the above definition captures ropes that dense with branches as balanced: Generally, a rope of depth d can have as many as 2^d + 1 leaves, and if we disallow empty strings for labels, it follows that in that extremal case ℓ > 2^d, as each leaf must have a string of length at least 1. Since¹ Fib(d) ≈ φ^d ≈ (1.6)^d is less than 2^d, it follows that the balancing property automatically holds. This completes our first observation, namely that ropes whose structure is almost filled are considered balanced. This is a good property because we would not want to spend time attempting to rebalance such a tree.

On the other hand, let us now consider ropes with a sparse tree structure, for which we would want the balancing property not to hold: those are the ropes whose depth is approximately the same as the number of internal nodes, and so they are structurally long and narrow. We would not want these ropes to satisfy the balancing criterion, and yet, if one of the leaf strings is longer than Fib(d), then certainly it will be called a balanced rope, regardless of its long and narrow tree structure! This can happen to any rope: as long as one of its leaves has a string that is long enough, it will be considered balanced. Long strings break the balance property, and so we should set a maximum threshold for how large a string label can be. If we do that, then indeed sparse trees will be considered unbalanced. The threshold parameter should be small relative to the average text file; for example a value like 1024 should work.

We have not yet clarified on the significance of the arithmetic function itself. Why was the Fibonacci sequence chosen over any other sequence? The answer lies in the heart of the balancing algorithm, which is presented next.

• The balancing algorithm