Search Trees/OOP

Object oriented programming concepts as applied to search trees.

Also see: Trees/OOP

Notes

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

Pseudo-Concrete Implementations

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.

I call this a pseudo-concrete implementation because it is, in fact, a concrete implementation, but one that is missing features and is therefore less efficient than it could be.