Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
Having already implemented a binary search tree class, BST,
we can make use of much of the existing code to implement an AVL tree class.
Program 
gives the declaration of the AVLTree class
which is derived from the class BST.
The AVLTree class inherits most of its
functionality from the binary tree class.
In particular,
it uses the inherited Insert and Withdraw functions!
In addition, the inherited Balance,
AttachKey and DetachKey member functions are overridden
and a number of new member functions are declared.
Program: AVLTree Class Definition
Program indicates that
the Height member function is redefined for the AVLTree class.
This turns out to be necessary because we need to be able to
determine quickly, i.e., in O(1) time,
that the AVL balance condition is satisfied at a given node in the tree.
In general, the running time required to compute the height of a
tree containing n nodes is O(n).
Therefore, to determine whether the AVL balance
condition is satisfied at a given node,
it is necessary to traverse completely the subtrees of the given node.
But this cannot be done in constant time.
To make it possible to verify the AVL balance condition in constant time, the member variable height has been added. Thus, every node in an AVLTree keeps track of its own height. In this way it is possible for the Height member function to run in constant time--all it needs to do is to return the value of the height member variable. And this makes it possible to test whether the AVL balanced condition satisfied at a given node in constant time.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.