DMTCS Proceedings, 2005 International Conference on Analysis of Algorithms

Font Size:  Small  Medium  Large

A repertoire for additive functionals of uniformly distributed m-ary search trees

James Allen Fill, Nevin Kapur


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) 1n=m-1, which corresponds to the number of leaves.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional