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.

Here's what it looks like in action:

class TreeMap(LinkedBinaryTree,MapBase):

    ...

    def __getitem__(self,k): 
        """Return value associated with key K."""
        if self.is_empty():
            raise KeyError("Key Error: "+repr(k))
        else:
            p = self._subtree_search(self.root(), k)
            self._rebalance_access(p) # hook for balanced subtree calsses
            if k!= p.key():
                raise KeyError("Key Error: " + repr(k))
            return p.value()

    def __iter__(self):
        """Generate an iteration of all keys in the map in order."""
        p = self.first()
        while p is not None:
            yield p.key()
            p = self.after(p)

    def __reverse__(self):
        """Generate a reverse iteration of all keys in the map in order."""
        p = self.last()
        while p is not None:
            yield p.key()
            p = self.before(p)

Note the following line:

self._rebalance_access(p) # hook for balanced subtree calsses

This calls a private method to rebalance the tree. However, because this class is an unbalanced search tree, this method is an empty method that does nothing to rebalance the tree. Thus, the class is intended to be extended by search trees that provide a similar interface, but that provide their own implementation of rebalancing nodes.