Section 1 - Inheritance and Generics

5B.1.1 Inheriting AVL from BST

We have done the hard work in designing and implementing our AVL trees. The truth is, if I just let you copy all the code from your BST template file (FHsearch_tree.h) and then replace the insert()/delete() and the definition of the basic node type, you'd be done. So why are we talking about inheritance.

Programmers don't like copying and pasting code if we are going to just use the copy exactly "as is". It gives us a bad feeling, and for good reason. Once we open that door, we have the same code in two places. Ultimately, we'll find a bug or want to adjust something in one file but forget or be too lazy to fix it in the other file. The next thing we know, we've got two different, unsynchronized and incompatible versions of the same function or class in two files. I suppose the truth is, we've all done this in the past, and know the pain it can cause.

Besides this, you have all spent an entire quarter honing your skills in inheritance, in CS 2B (CIS 15B), so you are naturally looking for an opportunity to use them. Here is your chance.

Let's peek a review of the FHsearch_tree prototype. What data and members can we use, unaltered, in our new FHavlTree?

// ------------------- FHsearch_tree Prototype ----------------------
template <class Comparable>
class FHsearch_tree
{
protected:
   int mSize;
   FHs_treeNode<Comparable> *mRoot;

public:
   FHsearch_tree() { mSize = 0; mRoot = NULL; }
   FHsearch_tree(const FHsearch_tree &rhs) 
      { mRoot = NULL; mSize = 0; *this = rhs; }
   ~FHsearch_tree() { clear(); }

   const Comparable &findMin() const;
   const Comparable &findMax() const;
   const Comparable &find(const Comparable &x) const;

   bool empty() const { return (mSize == 0); }
   int size() const { return mSize; }
   void clear() { makeEmpty(mRoot); }
   const FHsearch_tree & operator=(const FHsearch_tree &rhs);

   bool insert(const Comparable &x);
   bool remove(const Comparable &x);
   bool contains(const Comparable &x) const { return find(mRoot, x) != NULL; }

   template <class Processor>
   void traverse(Processor func) const { traverse(mRoot, func); }
   int showHeight() const { return findHeight(mRoot); }

protected:
   FHs_treeNode<Comparable> *clone( FHs_treeNode<Comparable> *root) const;
   FHs_treeNode<Comparable> *findMin(FHs_treeNode<Comparable> *root) const;
   FHs_treeNode<Comparable> *findMax(FHs_treeNode<Comparable> *root) const;
   FHs_treeNode<Comparable> *find(FHs_treeNode<Comparable> *root,
      const Comparable &x) const;
   bool insert(FHs_treeNode<Comparable> * &root,
      const Comparable &x);
   bool remove(FHs_treeNode<Comparable> * &root, const Comparable &x);
   void makeEmpty(FHs_treeNode<Comparable> * &subtreeToDelete);
   template <class Processor>
   void traverse(FHs_treeNode<Comparable> *treeNode,
      Processor func, int level = 0) const;
   int findHeight(FHs_treeNode<Comparable> *treeNode, int height = 0) const;
   
public:
   // for exception throwing
   class EmptyTreeException {};
   class NotFoundException {};
};

The data mRoot, and mSize? Absolutely. the three find() methods? Yes. empty(), size() and clear()? We're sure to have a need for them. Even traverse() can be used just as much in an AVL tree as in a binary search tree. And the exception classes are going to come in handy, too. There are other methods, but I'll stop here. All of these things have nothing to do with AVL-ness. The bottom line is, an AVL tree IS A binary search tree -- plus a little more. That's what inheritance means.

There are a few methods tucked in there that we never discussed, but they are part of your include package. Two of them, findHeight() and showHeight() are used for analytical purposes to compare this the original FHsearch_tree structure size with the new FHavlTree.

We derive two new classes from our two BST types. The first is the node type. The second is the tree type. Here is the class declaration header in each case:

// ---------------------- AvlNode --------------------------
template <class Comparable>
class AvlNode : public FHs_treeNode<Comparable>
{
   ...
}

// -------------------- FHavlTree Prototype ----------------------
template <class Comparable>
class FHavlTree : public FHsearch_tree<Comparable>
{
   ...
}

We are defining two new class templates, and using the type variable, Comparable, to specialize the base class. After that, we pretty much use the same notation we have always used. Our job now is to add methods and data to the derived class (template, but I'll probably use the word class alone in much of what follows), but do so in a way that does not duplicate anything unnecessarily. We let the base class do what it did and not touch that code.

For example, we will not define or even mention member functions like clear(), makeEmpty() or traverse(), since they will carry over, unchanged. There is no need to write them. This will be true of most of the methods in the base FHsearch_tree.

5B.1.2 The AVL Node Class

The node class is very easy, so we may as well show it all now. First, I will reveal something that's been in your FHsearch_tree.h file that I had not advertized -- two virtual methods in FHs_treeNode class:

 // -------------------- FHs_treeNode Prototype -----------------------
template <class Comparable>
class FHs_treeNode
{
public:
   // members and constructor you already know about are omitted, then ...
   
   // for use only with AVL Trees
   virtual int getHeight() const { return 0; }
   virtual bool setHeight(int height) { return true; }
}; 

These two methods make it possible for FHs_treeNode pointers to be used in many of our AVL tree methods. When they point to actual AVL nodes, they will correctly access the true methods that will get and set the height data. This is what virtual means, after all.

Here is the full node class, named this time without the "FH", in agreement with the text: AvlNode.

// ---------------------- AvlNode --------------------------
template <class Comparable>
class AvlNode : public FHs_treeNode<Comparable>
{
public: 
   AvlNode( const Comparable & d, AvlNode *lftChild, AvlNode *rtChild, int ht = 0 )
      : FHs_treeNode<Comparable>(d, lftChild, rtChild), height(ht)
   { }

   int height;

   int getHeight() const { return height; }
   bool setHeight(int height);
};

template <class Comparable>
bool AvlNode<Comparable>::setHeight(int height) 
{
   if (height < -1) 
      return false;
   this->height = height;
   return true;
}

It has exactly one member: height. But don't forget, it inherits the lftChild and rtChild members from the base class. The constructor chains, simply, to the base class constructor, and the accessor and mutator override the virtual base versions. It is straightforward.

5B.1.3 The AVL Tree Class

Which leaves us with the question: what methods will we actually have to add or change in our subclass template FHavlTree?

• The easy answers: We'll need our overriding insert() and remove(). We'll need all the private rotation methods. We already designed and implemented them, so this will be a piece of cake going forward.
• The trickier answers: We'll need to provide our own copy constructor, default constructor, assignment operator and private clone() method. This four-method package is only needed if we want to be able to assign one FHavlTree to another, which, of course, we should allow. The base class versions of these four functions are of no use to us -- and we can't really even chain to them easily -- because the height information was not incorporated in those methods. These few methods are really not central to the maneuvers we are studying -- tree balancing and rotations -- so I'll provide the code without much commentary. You can study those items as you wish, especially if you are weak on inheritance concepts as they are impacted by deep memory, the crux of the problem that these four methods overcome.

Here, then, is the full class prototype, which I will call FHavlTree. Note that there are relatively few public methods, a state of affairs made possible because we are deriving this class from FHsearch_tree.

template <class Comparable>
class FHavlTree : public FHsearch_tree<Comparable>
{
public:
   // we need our own copy constructor and op= because of height info
   FHavlTree(const FHavlTree &rhs) 
      { this->mRoot = NULL; this->mSize = 0; *this = rhs; }

   // need a default because above hides it.  Simply chain to base class
   FHavlTree() : FHsearch_tree<Comparable>() { }

   const FHavlTree & operator=(const FHavlTree &rhs);

   // override base class insert/remove
   bool insert(const Comparable &x);
   bool remove(const Comparable &x);

   // a fun and informative touch
   int showHeight() const { return heightOf(this->mRoot); }

protected:
   // static because the node whose height we want might be null
   static int heightOf(FHs_treeNode<Comparable> *t)
      { return t == NULL? -1 : t->getHeight(); }
   AvlNode<Comparable> *clone( FHs_treeNode<Comparable> *root) const;

   bool insert( const Comparable & x, FHs_treeNode<Comparable> * & root );
   bool remove( const Comparable & x, FHs_treeNode<Comparable> * & root );
   void rotateWithLeftChild( FHs_treeNode<Comparable> * & k2 );
   void doubleWithLeftChild( FHs_treeNode<Comparable> * & k3 );
   void rotateWithRightChild( FHs_treeNode<Comparable> * & k2 );
   void doubleWithRightChild( FHs_treeNode<Comparable> * & k3 );
   int static max(int a, int b) { return (a < b)? b : a ; }
};

On the next page I will show the definitions, many of which you have already seen.