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
   229   230   231   232   233   234   235   236   237   238   239