Page 233 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes has a very special shape called a binomial tree. Binomial trees are general trees. i.e., the maximum
degree of a node is not fi xed.
The remarkable characteristic of binomial queues is that the merge operation is similar in structure
to binary addition, i.e., the collection of binomial trees that make up the binomial queue is like
the set of bits that make up the binary representation of a non-negative integer. Furthermore, the
merging of two binomial queues is done by adding the binomial trees that make up that queue in
the same way that the bits are combined when adding two binary numbers.

Binomial Trees

A binomial tree is a general tree with a very special shape:

Definition (Binomial Tree)

The binomial tree of order k ≥ 0 with root R is the tree B defined as follows
k
1. If k = 0, B = B = {R} i.e., the binomial tree of order zero consists of a single node, R.
k 0
2. If k > 0, B = {R, B , B , ..., B } i.e., the binomial tree of order k>0 comprises the root R, and
k 0 1 k–1
k binomial subtrees, B , B , ..., B .
0 1 k–1
Figure 11.4 shows the fi rst five binomial trees, B – B . It follows directly from the root of B , the

4
k
0
binomial tree of order k, has degree k. Since k may arbitrarily large, so too can the degree of the
root. Furthermore, the root of a binomial tree has the largest fanout of any of the nodes in that
tree.
Figure 11.4: Binomial Trees B , B , ..., B
0 1 4
B 0 B 1 B 2 B 3

B
4

228 LOVELY PROFESSIONAL UNIVERSITY