Sur la concentration de la hauteur des arbres binaires de recherche

La hauteur d'un arbre binaire de recherche de $n$ sommets est \'egale \`a la taille de pile utilis\'ee en triant $n$ \'el\'ements par la version la plus simple de Quicksort. La valeur moyenne de cette hauteur est connue ($4.31107...\log (n) + O(\log \log n)$). Quant \`a sa variance, on n'a qu'une borne sup\'erieure en $O({\log \log n}^2)$. On a conjectur\'e qu'elle est en fait $O(1)$. Apr\`es un aper\c{c}u historique de ce probl\`eme, je pr\'esenterai des r\'esultats qui rendent cette conjecture plus plausible, \`a savoir des bornes de $O(1)$ sur la diff\'erence absolue entre la hauteur et sa moyenne.