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.
Publié le : 2008-02-15
Classification:
Functional limit theorem,
search trees,
profile of trees,
random trees,
analysis of algorithms,
60F17,
68Q25,
68P10,
60C05
@article{1199890024,
author = {Drmota, Michael and Janson, Svante and Neininger, Ralph},
title = {A functional limit theorem for the profile of search trees},
journal = {Ann. Appl. Probab.},
volume = {18},
number = {1},
year = {2008},
pages = { 288-333},
language = {en},
url = {http://dml.mathdoc.fr/item/1199890024}
}
Drmota, Michael; Janson, Svante; Neininger, Ralph. A functional limit theorem for the profile of search trees. Ann. Appl. Probab., Tome 18 (2008) no. 1, pp. 288-333. http://gdmltest.u-ga.fr/item/1199890024/