Height, AdjustHeight and BalanceFactor Member Functions

Data Structures and Algorithms with Object-Oriented Design Patterns in C++

`Height`, `AdjustHeight` and `BalanceFactor` Member Functions

The Height member function is implemented as an AVLTree member variable accessor that simply returns the value of the height member variable. Clearly the running time of this function is constant.

The purpose of AdjustHeight is to recompute the height of a node and to update the height member variable. This routine must be called whenever the height of one of the subtrees changes in order to ensure the height variable is always up to date. The AdjustHeight routine determines the height of a node by adding one to the height of the highest subtree. Since the running time of the Height function is constant, so too is the running time of AdjustHeight.

The BalanceFactor member function simply returns the difference between the heights of the left and right subtrees of a given AVL tree. By Definition , the empty node is AVL balanced. Therefore, the BalanceFactor routines zero for an empty tree. Again, since the running time of the Height function is constant, the running time of BalanceFactor is also constant.