Search Trees/OOP

Notes

Object oriented programming concepts as applied to search trees:

The Goodrich book shows several really nice examples of how we can apply object oriented thinking to this type of data structure.

The first was in Section 11.1, introducing binary search trees. The TreeMap class introduced in that section implemented a binary search tree, albeit with no balancing. The class is a concrete implementation (it inherited from LinkedBinaryTree, itself a concrete implementation of the binary tree class and the abstract tree class) but it is also a class that is intended to be extended. Like an abstract class, it implements certain methods and leaves others "blank" with the intention that the class be extended to new implementations that define those methods. However, this is done in a clever way, such that the TreeMap class stands on its own, or can be extended into new and more efficient types of tree maps.