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

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


Publisher files allowed on an open archive




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


Files downloads