Distribution of distances in random binary search trees

• 成果类型: Article
• 署名作者: Mahmoud, HM; Neininger, R
• 署名单位: George Washington University; McGill University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2003
• 页码: 253-276
• 关键词: contraction method; THEOREM

摘要

We investigate random distances in a random binary search tree. Two types of random distance are considered: the depth of a node randomly selected from the tree, and distance between randomly selected pairs of nodes. By a combination of classical methods and modern contraction techniques we arrive at a Gaussian limit law for normed random distances between pairs. The exact forms of the mean and variance of this latter distance are first derived by classical methods to determine the scaling properties, then used for norming, and the normed random variable is then shown by the contraction method to have a normal limit arising as the fixed-point solution of a distributional equation. We identify the rate of convergence in the limit law to be of the order Theta(1/root1nn) in the Zolotarev metric xi(3). In the analysis we need the rate of convergence in the central limit law for the depth of a node, as well. This limit law was derived before by various techniques. We establish the rate Theta (1 /root1nn) in xi(3).