×

On the internal path length of \(d\)-dimensional quad trees. (English) Zbl 0927.68030

Summary: 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.

MSC:

68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] ?Probability distributions on cladograms,? Random discrete structures, The IMA Volumes in Mathematics and Its Applications, Vol. 76, pp. 1-18, and (Editors), Springer-Verlag, New York, 1996.
[2] Devroye, J ACM 33 pp 489– (1986) · Zbl 0741.05062 · doi:10.1145/5925.5930
[3] Devroye, Acta Inform 24 pp 277– (1987) · Zbl 0643.60065 · doi:10.1007/BF00265991
[4] Devroye, SIAM J Comput 28 pp 409– (1999) · Zbl 0915.68089 · doi:10.1137/S0097539795283954
[5] Devroye, SIAM J Comput 19 pp 821– (1990) · Zbl 0711.68032 · doi:10.1137/0219057
[6] Dobrow, Combinatorics
[7] Finkel, Acta Inform 4 pp 1– (1974) · Zbl 0278.68030 · doi:10.1007/BF00288933
[8] Flajolet, Algorithmica 10 pp 473– (1993) · Zbl 0783.68056 · doi:10.1007/BF01891833
[9] Flajolet, Random Struct Alg 7 pp 117– (1995) · Zbl 0834.68013 · doi:10.1002/rsa.3240070203
[10] Flajolet, Discrete Computat Geom 12 pp 151– (1994) · doi:10.1007/BF02574372
[11] Mahmoud, Acta Inform 23 pp 111– (1986) · Zbl 0567.68038 · doi:10.1007/BF00268078
[12] Evolution of random search trees, John Wiley, New York, 1992. · Zbl 0762.68033
[13] Rachev, Theory Probab Appl 29 pp 647– (1984) · Zbl 0581.60010 · doi:10.1137/1129093
[14] Rachev, Adv Appl Probab 27 pp 770– (1995) · doi:10.1017/S0001867800027142
[15] Régnier, RAIRO, Theoret Inform Appl 23 pp 335– (1989) · Zbl 0677.68072 · doi:10.1051/ita/1989230303351
[16] Rösler, RAIRO, Theoret Inform Appl 25 pp 85– (1991) · Zbl 0718.68026 · doi:10.1051/ita/1991250100851
[17] Rösler, Stoch Proc Appl 42 pp 195– (1992) · Zbl 0761.60015 · doi:10.1016/0304-4149(92)90035-O
[18] On the analysis of stochastic divide and conquer algorithms, preprint, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.