The profile of binary search trees
成果类型：
Article
署名作者：
Chauvin, B; Drmota, M; Jabbour-Hattab, J
署名单位：
Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); Technische Universitat Wien
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
发表日期：
2001
页码：
1042-1062
关键词：
摘要：
We characterize the limiting behavior of the number or nodes in level k of binary search trees T-n in the central region 1.2 log n less than or equal to k less than or equal to 2.8 log n. Especially we show that the width V, (the maximal number of internal nodes at the same level) satisfies (V) over bar (n) similar to (n/ root4pi log n) as n --> infinity a.s.