HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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 : Random Trees
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

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

Identifiers

Collections

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⟩

Share

Metrics

Record views

59

Files downloads

443