Data Structures and Algorithms with Object-Oriented Design Patterns in Python
next up previous index

Binomial Trees

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

Definition (Binomial Tree)  The binomial tree of order tex2html_wrap_inline60883 with root R is the tree tex2html_wrap_inline65955 defined as follows
  1. If k=0, tex2html_wrap_inline65959. That is, the binomial tree of order zero consists of a single node, R.
  2. If k>0, tex2html_wrap_inline65965. That is, the binomial tree of order k>0 comprises the root R, and k binomial subtrees, tex2html_wrap_inline65973, tex2html_wrap_inline65975, ..., tex2html_wrap_inline65977.

Figure gif shows the first five binomial trees, tex2html_wrap_inline65973- tex2html_wrap_inline65981. It follows directly from Definition gif that the root of tex2html_wrap_inline65955, the 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.

   figure26023
Figure: Binomial trees tex2html_wrap_inline65973, tex2html_wrap_inline65975, ..., tex2html_wrap_inline65981.

The number of nodes in a binomial tree of order k is a function of k:

Theorem  The binomial tree of order k, tex2html_wrap_inline65955, contains tex2html_wrap_inline58271 nodes.

extbfProof (By induction). Let tex2html_wrap_inline66017 be the number of nodes in tex2html_wrap_inline65955, a binomial tree of order k.

Base Case By definition, tex2html_wrap_inline65973 consists a single node. Therefore tex2html_wrap_inline66025.

Inductive Hypothesis Assume that tex2html_wrap_inline66027 for tex2html_wrap_inline66029, for some tex2html_wrap_inline66031. Consider the binomial tree of order l+1:

displaymath65943

Therefore the number of nodes in tex2html_wrap_inline66035 is given by

eqnarray26303

Therefore, by induction on l, tex2html_wrap_inline66027 for all tex2html_wrap_inline60883.

It follows from Theorem gif that binomial trees only come in sizes that are a power of two. That is, tex2html_wrap_inline66043. Furthermore, for a given power of two, there is exactly one shape of binomial tree.

Theorem  The height of tex2html_wrap_inline65955, the binomial tree of order k, is k.

extbfProof (By induction). Let tex2html_wrap_inline66051 be the height of tex2html_wrap_inline65955, a binomial tree of order k.

Base Case By definition, tex2html_wrap_inline65973 consists a single node. Therefore tex2html_wrap_inline66059.

Inductive Hypothesis Assume that tex2html_wrap_inline66061 for tex2html_wrap_inline66029, for some tex2html_wrap_inline66031. Consider the binomial tree of order l+1:

displaymath65943

Therefore the height tex2html_wrap_inline66035 is given by

eqnarray26325

Therefore, by induction on l, tex2html_wrap_inline66061 for all tex2html_wrap_inline60883.

Theorem gif tells us that the height of a binomial tree of order k is k and Theorem gif tells us that the number of nodes is tex2html_wrap_inline66027. Therefore, the height of tex2html_wrap_inline65955 is exactly tex2html_wrap_inline59347.

Figure gif shows that there are two ways to think about the construction of binomial trees. The first way follows directly from the Definition gif. That is, binomial tex2html_wrap_inline65955 consists of a root node to which the k binomial trees tex2html_wrap_inline65973, tex2html_wrap_inline65975, ..., tex2html_wrap_inline65977 are attached as shown in Figure gif (a).

   figure26336
Figure: Two views of binomial tree tex2html_wrap_inline65981.

Alternatively, we can think of tex2html_wrap_inline65955 as being comprised of two binomial trees of order k-1. For example, Figure gif (b) shows that tex2html_wrap_inline65981 is made up of two instances of tex2html_wrap_inline66117. In general, suppose we have two trees of order k-1, say tex2html_wrap_inline66121 and tex2html_wrap_inline66123, where tex2html_wrap_inline66125. Then we can construct a binomial tree of order k by combining the trees to get

displaymath65945

Why do we call tex2html_wrap_inline65955 a binomial tree? It is because the number of nodes at a given depth in the tree is determined by the binomial coefficient. And the binomial coefficient derives its name from the binomial theorem. And the binomial theorem tells us how to compute the tex2html_wrap_inline57913 power of a binomial . And a binomial is an expression which consists of two terms, such as x+y. That is why it is called a binomial tree!

Theorem (Binomial Theorem)  The tex2html_wrap_inline57913 power of the binomial x+y for tex2html_wrap_inline58503 is given by

displaymath65946

where tex2html_wrap_inline66141 is called the binomial coefficient  .

extbfProof The proof of the binomial theorem is left as an exercise for the reader (Exercise gif).gif

The following theorem gives the expression for the number of nodes at a given depth in a binomial tree:

Theorem  The number of nodes at level l in tex2html_wrap_inline65955, the binomial tree of order k, where tex2html_wrap_inline66149, is given by the binomial coefficient tex2html_wrap_inline66151.

extbfProof (By induction). Let tex2html_wrap_inline66153 be the number of nodes at level l in tex2html_wrap_inline65955, a binomial tree of order k.

Base Case Since tex2html_wrap_inline65973 contains a single node, there is only one level in the tree, l=0, and exactly one node at that level. Therefore, tex2html_wrap_inline66165.

Inductive Hypothesis Assume that tex2html_wrap_inline66167 for tex2html_wrap_inline66169, for some tex2html_wrap_inline63063. The binomial tree of order h+1 is composed of two binomial trees of height h, one attached under the root of the other. Hence, the number of nodes at level l in tex2html_wrap_inline66179 is equal to the number of nodes at level l in tex2html_wrap_inline66183 plus the number of nodes at level l-1 in tex2html_wrap_inline66183:

eqnarray26566

Therefore by induction on h, tex2html_wrap_inline66167.

next up previous index

Bruno Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.