• 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 alea occurs.
    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.