We characterize the limiting behavior of the number of nodes in
level $k$ of binary search trees $T_n$ in the central region $1.2 \log n \leq
2.8 \log n$. Especially we show that the width $\bar{V}_n$ (the maximal number
of internal nodes at the same level) satisfies $\bar{V}_n \sim
(n/\sqrt{4\pi\log n})$ as $n \to \infty$ a.s.
Publié le : 2001-11-14
Classification:
Repartition of nodes for binary search trees,
martingales,
asymptotic series expansion,
complex analysis,
60F17,
60Q25,
05C05
@article{1015345394,
author = {Chauvin, Brigitte and Drmota, Michael and Jabbour-Hattab, Jean},
title = {The Profile of Binary Search Trees},
journal = {Ann. Appl. Probab.},
volume = {11},
number = {2},
year = {2001},
pages = { 1042-1062},
language = {en},
url = {http://dml.mathdoc.fr/item/1015345394}
}
Chauvin, Brigitte; Drmota, Michael; Jabbour-Hattab, Jean. The Profile of Binary Search Trees. Ann. Appl. Probab., Tome 11 (2001) no. 2, pp. 1042-1062. http://gdmltest.u-ga.fr/item/1015345394/