equal probability expect an average improvement in the search path length of at most emphasis is to be put on the word averagefor the improvement may of course be very much greater in the unhappy case in which the generated tree had completely degenerated into listwhichhoweveris very unlikely to occur in this connection it is noteworthy that the expected average path length of the random tree grows also strictly logarithmically with the number of its nodeseven though the worst case path length grows linearly the figure of imposes limit on the amount of additional effort that may be spent profitably on any kind of reorganization of the tree' structure upon insertion of keys naturallythe ratio between the frequencies of access (retrievalof nodes (informationand of insertion (updatesignificantly influences the payoff limits of any such undertaking the higher this ratiothe higher is the payoff of reorganization procedure the figure is low enough that in most applications improvements of the straight tree insertion algorithm do not pay off unless the number of nodes and the access vs insertion ratio are large balanced trees from the preceding discussion it is clear that an insertion procedure that always restores the treesstructure to perfect balance has hardly any chance of being profitablebecause the restoration of perfect balance after random insertion is fairly intricate operation possible improvements lie in the formulation of less strict definitions of balance such imperfect balance criteria should lead to simpler tree reorganization procedures at the cost of only slight deterioration of average search performance one such definition of balance has been postulated by adelson-velskii and landis [ - the balance criterion is the followinga tree is balanced if and only if for every node the heights of its two subtrees differ by at most trees satisfying this condition are often called avl-trees (after their inventorswe shall simply call them balanced trees because this balance criterion appears most suitable one (note that all perfectly balanced trees are also avl-balanced the definition is not only simplebut it also leads to manageable rebalancing procedure and an average search path length practically identical to that of the perfectly balanced tree the following operations can be performed on balanced trees in (log nunits of timeeven in the worst case locate node with given key insert node with given key delete the node with given key these statements are direct consequences of theorem proved by adelson-velskii and landiswhich guarantees that balanced tree will never be more than higher than its perfectly balanced counterpartno matter how many nodes there are if we denote the height of balanced tree with nodes by hb( )then log( + hb( *log( + the optimum is of course reached if the tree is perfectly balanced for - but which is the structure of the worst avl-balanced treein order to find the maximum height of all balanced trees with nodeslet us consider fixed height and try to construct the balanced tree with the minimum number of nodes this strategy is recommended becauseas in the case of the minimal heightthe value can be attained only for certain specific values of let this tree of height be denoted by clearlyt is the empty treeand is the tree with single node in order to construct the tree for we will provide the root with two subtrees which again have minimal number of nodes hencethe subtrees are also evidentlyone subtree must have height - and the other is then allowed to have height of one lessi - figure shows the trees with height and since their composition principle very