A functional limit theorem for the profile of search trees
2008 (English)In: The Annals of Applied Probability, ISSN 1050-5164, Vol. 18, no 1, 288-233 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2008. Vol. 18, no 1, 288-233 p.
functional limit theorem, search trees, profile of trees, random trees, analysis of algorithms
IdentifiersURN: urn:nbn:se:uu:diva-106265DOI: 10.1214/07-AAP457ISI: 000252750300012OAI: oai:DiVA.org:uu-106265DiVA: diva2:224358