|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
If binomial trees only come in sizes that are powers of two, how do we implement a container which holds an arbitrary number number of items n using binomial trees? The answer is related to the binary representation of the number n. Every non-negative integer n can be expressed in binary form as
where 
is the 
binary digit
or bit in the representation of n.
For example, n=27 is expressed as the binary number
because 27=16+8+2+1.
To make a container which holds exactly n items
we use a collection of binomial trees.
A collection of trees is called a forest .
The forest contains binomial tree 
if the bit
in the binary representation of n is a one.
That is, the forest 
which contains exactly n items is given by
where 
is determined from Equation 
.
For example, the forest which contains 27 items is
The analogy between and the binary representation of n
carries over to the merge operation.
Suppose we have two forests,
say and 
.
Since contains n items and contains m items,
the combination of the two contains n+m items.
Therefore, the resulting forest is 
.
For example, consider n=27 and m=10.
In this case, we need to merge 
with
.
Recall that two binomial trees of order k can be combined
to obtain a binomial tree of order k+1.
For example, 
.
But this is just like adding binary digits!
In binary notation, the sum 27+10 is calculated like this:
| 1 | 1 | 0 | 1 | 1 | ||
| + | 1 | 0 | 1 | 0 | ||
|
| 1 | 0 | 0 | 1 | 0 | 1 |
and 
is done in the same way:
 |  |  |  |  | | ||
| + | | | | |  | ||
|
|  | | |  | | |  |
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
