Random binary trees: from the average case analysis to the asymptotics of distributions (Q2457886)

The author gives a survey of various probabilistic methods which have been developed in the last 10--20 years for the analysis of algorithms. For random binary search trees \(T_n\) which correspond to a particular storage algorithm for storing \(n\) random data \(x_1, \ldots, x_n\), the dynamic structure as martingale is derived. This leads to a limit theorem for the internal-path length. The recursive structure of the tree allows to identify the limit by the contraction method. From a different view point then Poisson approximation estimates are applied to analyse the number of recursions needed by the FIND-algorithm to search the \(l\)-th order statistic. The argument uses a representation of the number of records in terms of binomial random variables. Finally a technic of special (accompanying) constructions is illustrated by the example of the number of comparison steps of the FIND-algorithm. The paper gives a vivid impression of the development of this active area of research.