For the binomial tree Bk,
1. there are 2k nodes,
2. the height of the tree is k,
3. there are exactly nodes at depth i for i = 0, 1, ..., k, and
4. the root has degree k, which is greater than that of any other node; moreover if i the children of the root are numbered from left to right by k - 1, k - 2, ..., 0, child i is the root of a sub tree Bi.
Proof:
The proof is by induction on k. For each property, the basis is the binomial tree B0. Verifying that each property holds for B0 is trivial. For the inductive step, we assume that the lemma holds for Bk-1.
1. Binomial tree Bk consists of two copies of Bk-1, and so Bk has 2k-1 + 2k-1 = 2k nodes.
2. Because of the way in which the two copies of Bk-1 are linked to form Bk, the
maximum depth of a node in Bk is one greater than the maximum depth in Bk-1. By the
inductive hypothesis, this maximum depth is (k - 1) + 1 = k.
3. The name comes from the shape: a binomial tree of order 
has 
nodes at depth 
.These are the binomial coefficients.see http://en.wikipedia.org/wiki/Binomial_coefficient?temp-new-window-replacement=true
4. The only node with greater degree in Bk than in Bk-1 is the root, which has one more
child than in Bk-1. Since the root of Bk-1 has degree k - 1, the root of Bk has degree k.
Now, by the inductive hypothesis, and as Figure 19.2(c) shows, from left to right, the
children of the root of Bk-1 are roots of Bk-2, Bk-3, ..., B0. When Bk-1 is linked to Bk-1,
therefore, the children of the resulting root are roots of Bk-1, Bk-2, ..., B0.
The maximum degree in an n-node binomial tree is lg n and n-node binomial heap H consists of at most [lg n]+1 binomial trees.
Now we are defining the Binomial Heaps.
- Definition definition.php?temp-new-window-replacement=true
- Construction construction-of-binomial-heap.php?temp-new-window-replacement=true
- Representation representation-of-binomial-heaps.php?temp-new-window-replacement=true
- Operations operations-on-binomial-heap.php?temp-new-window-replacement=true
continue definition.php
