|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Since binomial trees are simply general trees with a special shape,
we can make use of the GeneralTree class
presented in Section 
to implement the BinomialTree class.
(See Figure ).
Program introduces the BinomialQueue class
and the nested class BinomialTree.
The BinomialQueue class extends
the abstract MergeablePriorityQueue class
defined in Program .
The BinomialTree class extends the GeneralTree class
introduced in Program .
No new instance attributes 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 instance attribute. 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: BinomialQueue.BinomialTree class __init__ method.
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.