4.12.2.1 General Trees |

A compression is the repeated application of a right rotation, called in this context a “compression transformation”, once for each black node, like so:

So far, all of the compressions we've performed have involved all 2**k - 1 nodes composing the “main vine.” This works out well for an initial vine of exactly 2**n - 1 nodes. In this case, a total of n - 1 compressions are required, where for successive compressions k = n, n - 1, ..., 2.

For trees that do not have exactly one fewer than a power of two nodes, we need to begin with a compression that does not involve all of the nodes in the vine. Suppose that our vine has m nodes, where 2**n - 1 < m < 2**(n+1) - 1 for some value of n. Then, by applying the compression transformation shown above m - (2**n - 1) times, we reduce the length of the main vine to exactly 2**n - 1 nodes. After that, we can treat the problem in the same way as the former case. The result is a balanced tree with n full levels of nodes, and a bottom level containing m - (2**n - 1) nodes and (2**(n + 1) - 1) - m vacancies.

An example is indicated. Suppose that the vine contains *m* == 9 nodes
numbered from 1 to 9. Then *n* == 3 since we have 2**3 - 1 = 7 < 9 < 15 = 2**4 - 1, and
we must perform the compression transformation shown above 9 - (2**3 - 1) = 2 times initially, reducing the
main vine's length to 7 nodes. Afterward, we treat the problem the same
way as for a tree that started off with only 7 nodes, performing one
compression with *k* == 3 and one with *k* == 2. The entire sequence,
omitting the initial vine, looks like this:

Now we have a general technique that can be applied to a vine of any
size.