if all npermutations of keys occur with equal probabilitywhat is the expected height of the constructed balanced tree what is the probability that an insertion requires rebalancingmathematical analysis of this complicated algorithm is still an open problem empirical tests support the conjecture that the expected height of the balanced tree thus generated is log( )+cwhere is small constant ( this means that in practice the avl-balanced tree behaves as well as the perfectly balanced treealthough it is much simpler to maintain empirical evidence also suggests thaton the averagerebalancing is necessary once for approximately every two insertions here single and double rotations are equally probable the example of fig has evidently been carefully chosen to demonstrate as many rotations as possible in minimum number of insertions the complexity of the balancing operations suggests that balanced trees should be used only if information retrievals are considerably more frequent than insertions this is particularly true because the nodes of such search trees are usually implemented as densely packed records in order to economize storage the speed of access and of updating the balance factors -each requiring two bits only -is therefore often decisive factor to the efficiency of the rebalancing operation empirical evaluations show that balanced trees lose much of their appeal if tight record packing is mandatory it is indeed difficult to beat the straightforwardsimple tree insertion algorithm balanced tree deletion our experience with tree deletion suggests that in the case of balanced trees deletion will also be more complicated than insertion this is indeed truealthough the rebalancing operation remains essentially the same as for insertion in particularrebalancing consists again of either single or double rotations of nodes the basis for balanced tree deletion is the ordinary tree deletion algorithm the easy cases are terminal nodes and nodes with only single descendant if the node to be deleted has two subtreeswe will again replace it by the rightmost node of its left subtree as in the case of insertiona boolean variable parameter is added with the meaning "the height of the subtree has been reducedrebalancing has to be considered only when is true is made true upon finding and deleting nodeor if rebalancing itself reduces the height of subtree we now introduce the two (symmetricbalancing operations in the form of proceduresbecause they have to be invoked from more than one point in the deletion algorithm note that balancel is applied when the leftbalancer after the right branch had been reduced in height the operation of the procedure is illustrated in fig given the balanced tree ( )successive deletion of the nodes with keys and results in the trees ( (hdeletion of key is simple in itselfbecause it represents terminal node howeverit results in an unbalanced node its rebalancing operation invoves an ll single rotation rebalancing becomes again necessary after the deletion of node this time the right subtree of the root ( is rebalanced by an rr single rotation deletion of node although in itself straightforward since it has only single descendantcalls for complicated rl double rotation the fourth casean lr double rotationis finally invoked after the removal of node which at first was replaced by the rightmost element of its left subtreei by the node with key