A functional limit theorem for the profile of search trees

Abstract

We study the profile $X_{n,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,k}/\mathbb{E}{X}_{n,k}$ for $k=\lfloor \alpha \log n\rfloor$ 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.

Published in at http://dx.doi.org/10.1214/07-AAP457 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Width and mode of the profile for some random trees of logarithmic height

Cited by in corpus (9)

• Polya urns via the contraction method
• On a functional contraction method
• Heavy tailed solutions of multivariate smoothing transforms
• Long and short paths in uniform random recursive dags
• A limit process for partial match queries in random quadtrees and $2$-d trees
• A functional limit theorem for the profile of $b$-ary trees
• Mass distribution exponents for growing trees
• Search trees: Metric aspects and strong limit theorems
• The degree profile of Pólya trees