A functional limit theorem for the profile of search trees

• 成果类型: Article
• 署名作者: Drmota, Michael; Janson, Svante; Neininger, Ralph
• 署名单位: Technische Universitat Wien; Uppsala University; Goethe University Frankfurt
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/07-AAP457
• 发表日期: 2008
• 页码: 288-333
• 关键词: independent random-variables; random recursive trees; distributions; algorithms; height; width; sums

摘要

We study the profile X-n,X-k of random search trees including binary search trees and m-ary search trees. Our main result is a functional limit theorem of the normalized profile X-n,X-k/EXn,k for k = [alpha logn] in a certain range of alpha. A central feature of the proof is the use of the contraction method to prove convergence in distribution of certain random analytic functions in a complex domain. This is based on a general theorem concerning the contraction method for random variables in an infinite-dimensional Hilbert space. As part of the proof, we show that the Zolotarev metric is complete for a Hilbert space.