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

James Allen Fill, Nevin Kapur

Published 2005-02-20, updated 2005-04-25Version 2

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^\alpha$ with $\alpha \geq 0$ ($\alpha=0$ and $\alpha=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) $\mathbf{1}_{n=m-1}$, which corresponds to the number of leaves.