Random binary trees: from the average case analysis to the asymptotics of distributions (Q2457886)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random binary trees: from the average case analysis to the asymptotics of distributions |
scientific article |
Statements
Random binary trees: from the average case analysis to the asymptotics of distributions (English)
0 references
23 October 2007
0 references
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.
0 references
search algorithm
0 references
Poisson approximation
0 references
martingales
0 references
internal path length
0 references
binary search tree
0 references