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.