## of book chapters

[In *Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities,*
Trends in Mathematics, Birkhäuser Verlag, Basel, 3-15, 2000]
### András Antos and Luc Devroye

Abstract
A rawa tree is a binary search tree for an ordinary **ra**ndom **wa**lk
*0,S*_{1} ,S_{2},S_{3},...,
where *S*_{n}=\sum_{i=1}^{n} X_{i}
and the *X*_{i} 's are i.i.d. distributed as *X*.
We study the height *H*_{n} of the rawa tree,
and show that if *X* is absolutely continuous with bounded symmetric density,
if *X* has finite variance,
and if the density of *X* is bounded away from zero near the origin,
then *H*_{n} / \sqrt*{2n}* tends to the Erdõs-Kac-Rényi distribution.

*Keywords and phrases*.
Random binary search tree, probabilistic analysis, random walk, Catalan constant, limit distributions.

*CR Categories*: 3.74, 5.25, 5.5.

Back to the publications

© András Antos

Updated: Feb 7, 2021