Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Implementing Search Trees

Since search trees are designed to support efficient searching, it is only appropriate that they implement the SearchableContainer interface. Recall from Section  that the searchable container interface includes the operations Find, IsMember, Insert, and Withdraw.

  
Figure: Object class hierarchy

Program  defines the SearchTree interface. The SearchTree interface extends the Tree interface defined in Program  and the SearchableContainer interface defined in Program .

  
Program: SearchTree interface.

In addition, two properties are defined--Min and Max. The Min property provides a get accessor that returns the object contained in the search tree having the smallest key. Similarly, the Max provides a get accessor that returns 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 © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.