ab fig tree deletion analysis of tree search and insertion it is natural reaction to be suspicious of the algorithm of tree search and insertion at least one should retain some skepticism until having been given few more details about its behaviour what worries many programmers at first is the peculiar fact that generally we do not know how the tree will growwe have no idea about the shape that it will assume we can only guess that it will most probably not be the perfectly balanced tree since the average number of comparisons needed to locate key in perfectly balanced tree with nodes is approximately log( )the number of comparisons in tree generated by this algorithm will be greater but how much greaterfirst of allit is easy to find the worst case assume that all keys arrive in already strictly ascending (or descendingorder then each key is appended immediately to the right (leftof its predecessorand the resulting tree becomes completely degeneratei it turns out to be linear list the average search effort is then / comparisons this worst case evidently leads to very poor performance of the search algorithmand it seems to fully justify our skepticism the remaining question isof coursehow likely this case will be more preciselywe should like to know the length an of the search path averaged over all keys and averaged over all ntrees that are generated from the npermutations of the original distinct keys this problem of algorithmic analysis turns out to be fairly straightforwardand it is presented here as typical example of analyzing an algorithm as well as for the practical importance of its result given are distinct keys with values assume that they arrive in random order the probability of the first key -which notably becomes the root node -having the value is / its left subtree will eventually contain - nodesand its right subtree - nodes (see fig let the average path length in the left subtree be denoted by ai- and the one in the right subtree is an-iagain assuming that all possible permutations of the remaining - keys are equally likely the average path length in tree with nodes is the sum of the products of each node' level and its probability of access if all nodes are assumed to be searched with equal likelihoodthen an (si < <npin where pi is the path length of node