|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
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 
,
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.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.