Section 2 - Completion of the Avl Tree Implementation
5B.2.1 The Supporting Methods
The static private (protected) utility int max(int, int) speaks for itself. We saw this used during our insert() and remove() algorithms when we had to re-compute the height of a given node. One takes the higher of the two subtrees (ergo, max()) and adds one.
The static method heightOf() is at first a little curious. Why do we need this in the tree class? Can't we just call the node class's getHeight(), or better, since height is public, just access the height using the notation a_node->height, directly? Well, not quite. The problem arises when we are asking about the height of a null pointer. There is no node pointed-to, yet we still want a number, in that case, -1. So we have to make this a static member outside the node class. heightOf() is only used by our class template, not by the client so we make it private (which word I will use informally to mean protected, as it is in our class; remember, we want to prepare for the possibility of deriving from this class, just as we did with FHsearch_tree, and protected allows this).
showHeight() is the public version of heightOf(). It gives the total height of the entire tree, and is callable by the client. I don't want to call it getHeight() since it is not an accessor, and calling it height(), as in the text, results in a method with the same name as a member. This has been done in the past with size and size(), but then we had no choice because we wanted to be compatible with STL methods. Here, however, there is no STL counterpart to a tree class, so we can walk the walk.
5B.2.2 The Use of Base Class Node Pointers
In all but one case, when a method takes a node pointer parameter, we declare it to be of the base class (FHs_treeNode *), not of the derived class (AvlNode *). We must do this and we can do this.
Why "must"? Because these are often going to be recursive functions which start by passing in the root node pointer mRoot. This node is declared in the base class to be an FHs_treeNode* and we can't change that. We certainly cannot add a second root node of type AvlNode to our FHavlTree class - that would be madness. So we will be declaring all the pointer parameters to be base pointers, FHs_treeNode*s, but those pointers can and will be pointing to derived class, AvlNode, objects. This is standard procedure for pointers and should not be a big shock.
Why "can"? If we had not supplied virtual, then overriding, mutator/accessors in our node classes would create trouble. The base class pointers cannot be used to literally access the private height member of the derived class. It was that concern that prompted me to provide virtual methods getHeight() and setHeight() in the base node class. Since there was no height member in the base class, these base class variants cannot not return anything useful, so they just return 0 and true, respectively. They are dummy methods (written, perhaps by a dummy). The benefit of this is that we now have base class pointers which can be used to call getHeight() and setHeight(), and those two methods can be trusted to do the right thing because of their being virtual.
This was not the only solution. I could have added a height member to the base node class. If I had done so I would have set the value universally at 0 and not bothered to include overhead to maintain the height member in the basic search-tree template. That would have created an extra memory location for each node in the tree, and is not as elegant as using virtual functions. But, it was certainly a valid alternative approach.
But wait a second. Before we nod our heads in agreement, we have to be certain that when a base node pointer is used, it really does point to a derived node. When, exactly, does this theoretical node breathe its first breath, and how do we know it was born as an AvlNode and not an FHs_treeNode? Well, when do we create nodes in an FHavlTree? Not in the default constructor - there are no nodes there. Aha. In the insert() method of the derived class, FHavlTree::insert(). In a moment, you'll see that method (for the second time), and you can verify that every node created therein is, indeed, an AvlNode.
5B.2.3 The insert()/remove() and Rotation Methods
The explanations given in the sections above allow us to review the code that was presented in the earlier sections, but now with complete understanding. I won't show everything. Here is one rotate method and an insert() method, that you have seen before, but now you can read every detail in light of the full information about the virtual functions and base class nodes.
Here is a single right rotation:
template <class Comparable>
void FHavlTree<Comparable>::rotateWithRightChild( FHs_treeNode<Comparable> * & k2 )
{
FHs_treeNode<Comparable> *k1 = k2->rtChild;
k2->rtChild = k1->lftChild;
k1->lftChild = k2;
k2->setHeight( max( heightOf(k2->lftChild), heightOf(k2->rtChild) ) + 1 );
k1->setHeight( max( heightOf(k1->rtChild), k2->getHeight() ) + 1 );
k2 = k1;
}
Now for the insert():
// private utilities for member methods
template <class Comparable>
bool FHavlTree<Comparable>::insert( const Comparable & x, FHs_treeNode<Comparable> * & root )
{
if( root == NULL )
root = new AvlNode<Comparable>(x, NULL, NULL); // found a place to hang new node
else if( x < root->data )
{
if ( !insert(x, root->lftChild) )
return false;
if(heightOf(root->lftChild) - heightOf(root->rtChild) == 2)
if( x < root->lftChild->data )
rotateWithLeftChild(root);
else
doubleWithLeftChild(root);
}
else if(root->data < x)
{
if ( !insert(x, root->rtChild) )
return false;
if(heightOf(root->rtChild) - heightOf(root->lftChild) == 2)
if(root->rtChild->data < x)
rotateWithRightChild(root);
else
doubleWithRightChild(root);
}
else
return false;
// successfully inserted at this or lower level; adjust height
root->setHeight( max(heightOf(root->lftChild), heightOf(root->rtChild)) + 1);
return true;
}
Look, closely, for the birth of the new node. Is it a derived class node, AvlNode, as promised?
5B.2.4 The Quartet of Deep Copy Methods
As promised, I will show you the four deep-copy methods -- the copy constructor, assignment operator, clone() method, and default constructor -- of the new derived class. (Why do we need another default constructor, anyway?!).
They work very much like their base-class progenitors, but they, of course, pay tribute to the height member of the derived node class.
// ---------------------- FHavlTree Prototype --------------------------
template <class Comparable>
class FHavlTree : public FHsearch_tree<Comparable>
{
...
// written in-line in the prototype
FHavlTree(const FHavlTree &rhs)
{ this->mRoot = NULL; this->mSize = 0; *this = rhs; }
FHavlTree() : FHsearch_tree<Comparable>() { }
...
}
template <class Comparable>
const FHavlTree<Comparable> &FHavlTree<Comparable>::operator=
(const FHavlTree &rhs)
{
if (&rhs != this)
{
this->clear();
this->mRoot = clone(rhs.mRoot);
this->mSize = rhs.size();
}
return *this;
}
template <class Comparable>
AvlNode<Comparable> *FHavlTree<Comparable>::clone(
FHs_treeNode<Comparable> *root) const
{
AvlNode<Comparable> *newNode;
if (root == NULL)
return NULL;
newNode = new AvlNode<Comparable>(
root->data,
clone(root->lftChild), clone(root->rtChild), root->getHeight());
return newNode;
}
5B.2.5 The Public insert()/remove()
The only detail left undone is the presentation of the publicly exposed insert() and remove() methods. They set up a call to the private, recursive, methods, by using the mRoot as the initial node parameter, and adjusting the new mSize of the tree, as appropriate.
template <class Comparable>
bool FHavlTree<Comparable>::insert( const Comparable &x )
{
if (insert(x, this->mRoot))
{
this->mSize++;
return true;
}
return false;
}
template <class Comparable>
bool FHavlTree<Comparable>::remove( const Comparable &x )
{
if (remove(x, this->mRoot))
{
this->mSize--;
return true;
}
return false;
}
5B.2.6 Taking It Out For a Spin
Now for a simple test client. This is not exhaustive, but it confirms that insertion and deletion do seem to work, the heights are as expected, and the deep copy mechanism is correct:
// CS_2C AVL Tree Client
#include <iostream>
#include <string>
#include <stack>
#include "FHavlTree.h"
using namespace std;
#include "EBookEntry.h"
template <typename Object>
class PrintObject
{
public:
void operator()(Object obj)
{
cout << obj << " ";
}
};
int main()
{
int k;
FHavlTree<int> searchTree;
//FHsearch_tree<int> searchTree;
PrintObject<int> intPrinter;
searchTree.traverse(intPrinter);
cout << "initial size: " << searchTree.size() << endl;
searchTree.insert(50);
searchTree.insert(20);
searchTree.insert(30);
searchTree.insert(70);
searchTree.insert(10);
searchTree.insert(60);
cout << "tree 1 new size: " << searchTree.size()
<< " new height: " << searchTree.showHeight() << endl;
cout << "traversal: \n";
searchTree.traverse(intPrinter);
cout << endl;
FHavlTree<int> searchTree2 = searchTree;
cout << "\ntree 2 - size: " << searchTree2.size()
<< " new height: " << searchTree2.showHeight() << endl;
cout << "\n\nAttempting 100 removals: \n";
for (k = 100; k > 0; k--)
if (searchTree.remove(k))
cout << "removed " << k << endl;
cout << "\nsearchTree now:\n";
searchTree.traverse(intPrinter);
cout << "tree 1 - new size: " << searchTree.size()
<< " new height: " << searchTree.showHeight() << endl;
searchTree2.insert(500);
searchTree2.insert(200);
searchTree2.insert(300);
searchTree2.insert(700);
searchTree2.insert(100);
searchTree2.insert(600);
cout << "\nsearchTree2 after deletes:\n";
searchTree2.traverse(intPrinter);
cout << endl;
cout << "\ntree 2 - size: " << searchTree2.size()
<< " new height: " << searchTree2.showHeight() << endl;
return 0;
}
/* --------- output -----------
initial size: 0
tree 1 new size: 6 new height: 2
traversal:
10 20 30 50 60 70
tree 2 - size: 6 new height: 2
Attempting 100 removals:
removed 70
removed 60
removed 50
removed 30
removed 20
removed 10
searchTree now:
tree 1 - new size: 0 new height: -1
searchTree2 after deletes:
10 20 30 50 60 70 100 200 300 500 600 700
tree 2 - size: 12 new height: 4
Press any key to continue . . .
----------------------------- */