Brigitte Chauvin, University of Versailles
"Binary Search Trees"
We present first the binary search trees which model one of the most
famous sorting algorithm of computer science; we precise next where the
We analyze their height and path length, important cost parameters for
the computer scientist. The asymptotic analysis is done on one hand by
analytic combinatorics and generating functions and on the other hand
by a probabilistic approach using martingales.
The asymptotic analysis leads to a fixed point equation in
distribution, the latter being studied by a contraction method.
We precise the relationship of the model with branching processes
which allows results of large deviation for the height.