# Random Records and Cuttings in Split Trees: Extended Abstract

Abstract : 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.
Keywords :
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.269-282, 2008, DMTCS Proceedings
Domaine :

Littérature citée [16 références]

https://hal.inria.fr/hal-01194685
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:51:08
Dernière modification le : mercredi 10 mai 2017 - 17:41:10
Document(s) archivé(s) le : mardi 8 décembre 2015 - 13:01:24

### Fichier

dmAI0117.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01194685, version 1

### Citation

Cecilia Holmgren. Random Records and Cuttings in Split Trees: Extended Abstract. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.269-282, 2008, DMTCS Proceedings. 〈hal-01194685〉

### Métriques

Consultations de la notice

## 146

Téléchargements de fichiers