Geodesic
Random Records and Cuttings in Split Trees: Extended Abstract
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008).

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

We study the number of records in random split trees on $n$ randomly labelled vertices. Equivalently the number of random cuttings required to eliminate an arbitrary random split tree can be studied. After normalization the distributions are shown to be asymptotically $1$-stable. This work is a generalization of our earlier results for the random binary search tree which is one specific case of split trees. Other important examples of split trees include $m$-ary search trees, quadtrees, median of $(2k+1)$-trees, simplex trees, tries and digital search trees. 
@article{DMTCS_2008_special_254_a16,
     author = {Holmgren, Cecilia},
     title = {Random {Records} and {Cuttings} in {Split} {Trees:} {Extended} {Abstract}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science},
     year = {2008},
     doi = {10.46298/dmtcs.3570},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3570/}
}
TY  - JOUR
AU  - Holmgren, Cecilia
TI  - Random Records and Cuttings in Split Trees: Extended Abstract
JO  - Discrete mathematics & theoretical computer science
PY  - 2008
VL  - DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3570/
DO  - 10.46298/dmtcs.3570
LA  - en
ID  - DMTCS_2008_special_254_a16
ER  - 
%0 Journal Article
%A Holmgren, Cecilia
%T Random Records and Cuttings in Split Trees: Extended Abstract
%J Discrete mathematics & theoretical computer science
%D 2008
%V DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3570/
%R 10.46298/dmtcs.3570
%G en
%F DMTCS_2008_special_254_a16
Holmgren, Cecilia. Random Records and Cuttings in Split Trees: Extended Abstract. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science (2008). doi : 10.46298/dmtcs.3570. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3570/

Cité par Sources :