by substituting the above value of in formula we obtainfor > - + * - ( > - ( > - ( by taking logarithms of both sides of formula we obtain log( ( ) from which we get log( ( ) ( which implies that an avl tree storing entries has height at most logn by proposition and the analysis of binary search trees given in section the operation getitem in map implemented with an avl treeruns in time (log )where is the number of items in the map of coursewe still have to show how to maintain the height-balance property after an insertion or deletion update operations given binary search tree we say that position is balanced if the absolute value of the difference between the heights of its children is at most and we say that it is unbalanced otherwise thusthe height-balance property characterizing avl trees is equivalent to saying that every position is balanced the insertion and deletion operations for avl trees begin similarly to the corresponding operations for (standardbinary search treesbut with post-processing for each operation to restore the balance of any portions of the tree that are adversely affected by the change insertion suppose that tree satisfies the height-balance propertyand hence is an avl treeprior to the insertion of new item an insertion of new item in binary search treeas described in section results in new node at leaf position this action may violate the height-balance property (seefor examplefigure )yet the only positions that may become unbalanced are ancestors of pbecause those are the only positions whose subtrees have changed thereforelet us describe how to restructure to fix any unbalance that may have occurred