Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Implementing Search Trees

Since search trees are designed to support efficient searching, it is only appropriate that they extend the SearchableContainer class. Recall from Section  that the searchable container class includes the operations __contains__, find, insert, and withdraw.

  
Figure: Object class hierarchy

Program  defines the SearchTree class. The abstract SearchTree class extends the abstract Tree class introduced in Program  as well as the and the abstract SearchableContainer class defined in Program .

  
Program: Abstract SearchTree class min and max properties.

In addition, two properties are defined--min and max. The min property uses the getMin method to return the object contained in the search tree having the smallest key. Similarly, the max uses the getMax method to 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 © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.