A repertoire for additive functionals of uniformly distributed m-ary search trees
Abstract
Description
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 $α\geq 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) $\mathbf{1}_{n=m-1}$, which corresponds to the number of leaves.
26 pages; v2 expands on the introduction by comparing the results with other probability models
26 pages; v2 expands on the introduction by comparing the results with other probability models