Implementation

Program  declares the class MWayTree. An MWayTree is derived from the class SearchTree which is in turn derived from Tree and SearchableContainer. The four member variables, m, numberOfKeys, key, and subtree, correspond to the components of a node shown in Figure .

  
Program: MWayTree Class Definition

The first member variable, m, is a constant. It is used to record the degree of the node which cannot change after the node is created. (I.e., ). The second member variable, numberOfKeys, keeps track of the number of keys contained in the node. Recall, a node which has n subtrees contains n-1 keys. Therefore, . We have chosen to keep track of the number of keys of a node rather than the number of subtrees because it simplifies the coding of the algorithms by eliminating some of the special cases which arise if we keep track of n explicitly.

The third member variable, key, is an array of pointers to Object class instances. It is used to contain pointers to the keys contained in the node. The fourth and final member variable, subtree, is an array of pointers to the MWayTree instances which are the subtrees of the given node.

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