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

2005/02/28 by James Allen Fill, Nevin Kapur
Mathematics · #math.PR #math.CO #msc:68W40 #msc:60F05 #msc:60C05

paper · pdf

published as Discrete Mathematics and Theoretical Computer Science Proceedings AD (2005) 105-114 · 26 pages; v2 expands on the introduction by comparing the results with other probability models

arxiv created 2005/04/25 · arxiv updated 2009/12/01

Abstract

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 \binomnm-1, which corresponds to the so-called shape functional; and (iii) 1_n=m-1, which corresponds to the number of leaves.

Related

• Additive functionals on random search trees
• Limiting distributions for additive functionals on Catalan trees
• Transfer Theorems and Asymptotic Distributional Results for m-ary Search Trees
• The space requirement of m-ary search trees: distributional asymptotics for m >= 27
• Additive functionals of d-ary increasing trees