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

Implementing Search Trees

Since search trees are designed to support efficient searching, it is only appropriate that they be implemented as classes derived from the SearchableContainer abstract base class. Recall from Section gif that the searchable container interface includes the member functions Find, IsMember, Insert, and Withdraw.

   figure19290
Figure: Object Class Hierarchy

Program gif declares the SearchTree abstract base class. The SearchTree is derived from the classes Tree and SearchableContainer. The Tree class encapsulates those interface elements which are common to trees and search trees. The common member functions include Key, Subtree, IsEmpty, IsLeaf, Height, and Degree, as well as all of the various traversal routines (see Section gif).

   program19310
Program: SearchTree Class Definition

In addition, two more member functions are defined--FindMin and FindMax. These functions are accessors. The function FindMin returns a reference to the object contained in the search tree having the smallest key. Similarly, the function FindMax returns a reference to the contained object having the largest key.




next up previous contents index

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