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  that the searchable container interface includes the member functions Find, IsMember, Insert, and Withdraw.

  
Figure: Object Class Hierarchy

Program  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 ).

  
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.

• Binary Search Trees
• Inserting Items in a Binary Search Tree
• Removing Items from a Binary Search Tree

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