A functional limit theorem for the profile of search trees

Abstract

We study the profile Xn,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=⌊αlogn⌋ in a certain range of α. 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.