Premium
On the internal path length of d ‐dimensional quad trees
Author(s) -
Neininger Ralph,
Rüschendorf Ludger
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199908)15:1<25::aid-rsa2>3.0.co;2-r
Subject(s) - mathematics , path (computing) , path length , normalization (sociology) , tree (set theory) , limiting , combinatorics , mathematical analysis , computer science , anthropology , mechanical engineering , computer network , sociology , engineering , programming language
It is proved that the internal path length of a d ‐dimensional quad tree after normalization converges in distribution. The limiting distribution is characterized as a fixed point of a random affine operator. We obtain convergence of all moments and of the Laplace transforms. The moments of the limiting distribution can be evaluated from the recursion and lead to first order asymptotics for the moments of the internal path lengths. The analysis is based on the contraction method. In the final part of the paper we state similar results for general split tree models if the expectation of the path length has a similar expansion as in the case of quad trees. This applies in particular to the m ‐ary search trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 5: 25–41, 1999