Skedbooks
←
Design Analysis of Algorithm

Binomial Heaps

Binomial trees

The binomial tree Bk is an ordered tree defined recursively. As shown in Figure 19.2(a), the binomial tree B0 consists of a single node. The binomial tree Bk consists of two binomial trees Bk-1 that are linked together: the root of one is the leftmost child of the root of the other. Figure 19.2(b) shows the binomial trees B0 through B4.

Figure 19.2: (a) The recursive definition of the binomial tree Bk. Triangles represent rooted subtrees. (b) The binomial trees B0 through B4. Node depths in B4 are shown. (c) Another way of looking at the binomial tree Bk.

Some properties of binomial trees are given by the following lemma.

Lemma 19.1: (Properties of binomial trees)

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 subtree 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. Let D(k, i) be the number of nodes at depth i of binomial tree Bk. Since Bk is composed of two copies of Bk-1 linked together, a node at depth i in Bk-1 appears in Bk once at depth i and once at depth i 1. In other words, the number of nodes at depth i in Bk is the number of nodes at depth i in Bk-1 plus the number of nodes at depth i - 1 in Bk-1. Thus,

  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