Adding Binomial Trees

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Adding Binomial Trees

Recall that we can combine two binomial trees of the same order, say k, into a single binomial tree of order k+1. Each of the two trees to be combined is heap-ordered. Since the smallest key is at the root of a heap-ordered tree, we know that the root of the result must be the smaller root of the two trees which are to be combined. Therefore, to combine the two trees, we simply attach the tree with the larger root under the root of the tree with the smaller root. For example, Figure illustrates how two heap-ordered binomial trees of order two are combined into a single heap-ordered tree of order three.

Figure: Adding binomial trees.

The Add method defined in Program provides the means to combine two binomial trees of the same order. The Add method takes a BinomialTree and attaches the specified tree to this node. This is only permissible when both trees have the same order.

program26830
Program: BinomialTree class Add method.

In order to ensure that the resulting binomial tree is heap ordered, the roots of the trees are compared. If necessary, the contents of the nodes are exchanged using SwapContentsWith (lines 13-14) before the subtree is attached (line 15). Assuming SwapContentsWith and AttachSubtree both run in constant time, the worst-case running time of the Add method is . That is, exactly one comparison and a constant amount of additional work is needed to combine two binomial trees.