Binomial trees
What is a binomial tree? It is a recursively defined tree, as follows:
The first binomial tree has just one node. Its height is equal to 0. A binomial tree of height 1 is formed from two binomial trees, each of height 0. A binomial tree of height 2 is formed from two binomial trees, each of height 1.
The tree is defined in terms of itself, recursively. For example, the following figure shows two binomial trees of rank 2. When the right tree is pulled up, the left tree becomes its left child. The resulting tree is of rank 3 with 23 = 8 nodes.
The structure is formed by similar smaller structures:
The definition of binomial trees could also be stated as follows: a binomial tree with rank k is composed of subtrees with rank (k-1). Here is a pictorial way of stating this:
This forms an important basis for the merging operation, as we will soon see.
You can also look at a binomial tree as a list of binary trees. This is illustrated in the following figure:
The figure...
