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.