James Allen Fill ; Nevin Kapur
-
A repertoire for additive functionals of uniformly distributed m-ary search trees
dmtcs:3370 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
-
https://doi.org/10.46298/dmtcs.3370
A repertoire for additive functionals of uniformly distributed m-ary search treesConference paper
Authors: james Allen fill ; Nevin Kapur 1
NULL##NULL
james Allen fill;Nevin Kapur
1 Department of Computer Science
Using recent results on singularity analysis for Hadamard products of generating functions, we obtain the limiting distributions for additive functionals on m-ary search trees on n keys with toll sequence (i) n^α with α ≥ 0 (α =0 and α =1 correspond roughly to the space requirement and total path length, respectively); (ii) ln \binom{n} {m-1}, which corresponds to the so-called shape functional; and (iii) 1_{n=m-1}, which corresponds to the number of leaves.
Probability and Algorithms; Funder: National Science Foundation; Code: 0406104
CAREER: Computation Methods; Funder: National Science Foundation; Code: 0049092
Studies in Perfect Simulation and Combinatorial Probability; Funder: National Science Foundation; Code: 0104167
Bibliographic References
1 Document citing this article
Jean-François Delmas;Jean-Stéphane Dhersin;Marion Sciauveau, 2018, Cost functionals for large (uniform and simply generated) random trees, Electronic Journal of Probability, 23, none, 10.1214/18-ejp213, https://doi.org/10.1214/18-ejp213.