HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# 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 :
Document type :
Conference papers
Domain :

Cited literature [16 references]

https://hal.inria.fr/hal-01194685
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, September 7, 2015 - 12:51:08 PM
Last modification on : Wednesday, May 10, 2017 - 5:41:10 PM
Long-term archiving on: : Tuesday, December 8, 2015 - 1:01:24 PM

### File

dmAI0117.pdf
Publisher files allowed on an open archive

### Citation

Cecilia Holmgren. Random Records and Cuttings in Split Trees: Extended Abstract. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. pp.269-282, ⟨10.46298/dmtcs.3570⟩. ⟨hal-01194685⟩

Record views