Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

getHeight, adjustHeight, and getBalanceFactor Methods

The getHeight method is implemented as an accessor that simply returns the value of the height field. Clearly the running time of this method is constant.

The purpose of adjustHeight is to recompute the height of a node and to update the height field. This method 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 method determines the height of a node by adding one to the height of the highest subtree. Since the running time of the getHeight method is constant, so too is the running time of adjustHeight.

The getBalanceFactor method simply returns the difference between the heights of the left and right subtrees of a given AVL tree. By Definition gif, the empty node is AVL balanced. Therefore, the getBalanceFactor method returns zero for an empty tree. Again, since the running time of the getHeight method is constant, the running time of getBalanceFactor is also constant.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.