Geodesic
A repertoire for additive functionals of uniformly distributed m-ary search trees
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_249_a18,
     author = {fill, james Allen and Kapur, Nevin},
     title = {A repertoire for additive functionals of uniformly distributed m-ary search trees},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3370},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3370/}
}
TY  - JOUR
AU  - fill, james Allen
AU  - Kapur, Nevin
TI  - A repertoire for additive functionals of uniformly distributed m-ary search trees
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3370/
DO  - 10.46298/dmtcs.3370
LA  - en
ID  - DMTCS_2005_special_249_a18
ER  - 
%0 Journal Article
%A fill, james Allen
%A Kapur, Nevin
%T A repertoire for additive functionals of uniformly distributed m-ary search trees
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3370/
%R 10.46298/dmtcs.3370
%G en
%F DMTCS_2005_special_249_a18
fill, james Allen; Kapur, Nevin. A repertoire for additive functionals of uniformly distributed m-ary search trees. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3370. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3370/

Cité par Sources :