Page 234 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 234
Unit 11: Leftist Heaps and Binomial Queues
The number of nodes in a binomial tree of order k is a function of k: Notes
Theorem-11.3
k
The binomial tree of order k, B , contains 2 nodes.
k
extbfProof (By induction). Let n be the number of nodes in B , a binomial tree of order k.
k k
Base Case: By defi nition, B consists a single node. Therefore n = 1 = 2 .
0
0 0
k
Inductive Hypothesis: Assume that n = 2 for k = 0, 1, 2, ..., l, for some l ≥ 0. Consider the binomial
k
tree of order l + 1:
B = {R, B , B , B , ..., B }.
l + 1 0 1 2 l
Therefore the number of nodes in B is given by
l+1
l
n = 1 + ∑ n i
l+1
i= 0
l
= 1 + ∑ 2 i
i= 0
2 l+ 1 – 1
= 1 +
2– 1
= 2 l+1
Therefore, by induction on l, n = 2 for all k ≥ 0.
k
k
It follows from Theorem 11.3 that binomial trees only come in sizes that are a power of two. i.e.,
n ∈ {1, 2, 4, 8, 16, ...}. Furthermore, for a given power of two, there is exactly one shape of
k
binomial tree.
Theorem-11.4
The height of B , the binomial tree of order k, is k.
k
extbfProof (By induction). Let h be the height of B , a binomial tree of order k.
k k
Base Case: By defi nition, B consists a single node. Therefore h = 0.
0 0
Inductive Hypothesis: Assume that h = k for k = 0, 1, 2, ..., l, for some l ≥ 0. Consider the binomial
k
tree of order l + 1:
B = {R, B , B , B , ..., B }.
l+1 0 1 2 l
Therefore the height B is given by
l+1
h = 1maxh+
l+1 0 il i
≤≤
= 1maxi+
≤≤
0 il
= l + 1.
Therefore, by induction on l, h = k for all k ≥ 0.
k
Theorem 11.4 tells us that the height of a binomial tree of order k is k and tells us that the number
of nodes is n = 2 . Therefore, the height of B is exactly O(log n).
k
k k
Figure 11.5 shows that there are two ways to think about the construction of binomial trees, i.e.,
binomial B consists of a root node to which the k binomial trees B , B , ..., B are attached as
1
k–1
k
0
shown in Figure 11.5 (a).
LOVELY PROFESSIONAL UNIVERSITY 229