Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Heap-Ordered Binomial Trees

Since binomial trees are simply general trees with a special shape, we can make use of the GeneralTree class presented in Section gif to implement the BinomialTree class. (See Figure gif).

Program gif introduces the BinomialQueue class and the inner class BinomialTree. The BinomialTree class extends the GeneralTree class introduced in Program gif.

No new fields a declared in the BinomialTree class. Remember that the implementation of the GeneralTree class uses a linked list to contain the pointers to the subtrees, since the degree of a node in a general tree may be arbitrarily large. Also, the GeneralTree class already keeps track of the degree of a node in its degree field. Since the degree of the root node of a binomial tree of order k is k, it is not necessary to keep track of the order explicitly. The degree variable serves this purpose nicely.

Program: BinomialTree class.

next up previous contents index

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