www.delorie.com/gnu/docs/avl/libavl_73.html

search

	Buy GNU books!

GNU libavl 2.0.1

5.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 \ASCII\{2^n - 1, 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 \ASCII\ - 1, 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 \ASCII\{2^n - 1, 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 \ASCII\{m - (2^n - 1), m - (2**n - 1)} nodes and \ASCII\ - 1) - m, (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 \ASCII\{2^3 - 1 \equiv 7 < 9 < 15 \equiv 2^4 - 1, 2**3 - 1 = 7 < 9 < 15 = 2**4 - 1}, and we must perform the compression transformation shown above \ASCII\{9 - (2^3 - 1) \equiv 2, 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.