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

AdjustHeight Method, Height and BalanceFactor Properties

The Height property provides a get accessor that 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 field 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 Height accessor is constant, so too is the running time of AdjustHeight.

The BalanceFactor property provides a get accessor that 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 BalanceFactor is zero for an empty tree. Again, since the running time of the Height accessor is constant, the running time of BalanceFactor is also constant.


next up previous contents index

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