The Profile of Binary Search Trees

Authors
Chauvin, Brigitte Drmota, Michael Jabbour-Hattab Jean
Citation
Chauvin, Brigitte et al., The Profile of Binary Search Trees, Annals of applied probability , 11(4), 2001, pp. 1042-1062
Journal title
Annals of applied probability → ACNP
ISSN journal
10505164
Volume
11
Issue
4
Year of publication
2001
Pages
1042 - 1062
Database
ACNP
SICI code
Abstract
We characterize the limiting behavior of the number of nodes in level k of binary search trees Tn in the central region 1.2logn.2.8logn. Especially we show that the width .Vn (the maximal number of internal nodes at the same level) satisfies .Vn.(n/.4.logn) as n.. a.s.