A repertoire for additive functionals of uniformly distributed m-ary search trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

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

Résumé

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.
Fichier principal
Vignette du fichier
dmAD0110.pdf (146.29 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184042 , version 1 (12-08-2015)

Identifiants

Citer

James Allen Fill, Nevin Kapur. A repertoire for additive functionals of uniformly distributed m-ary search trees. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.105-114, ⟨10.46298/dmtcs.3370⟩. ⟨hal-01184042⟩

Collections

INSMI TDS-MACS
48 Consultations
424 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More