Cecilia Holmgren
-
Random Records and Cuttings in Split Trees: Extended Abstract
dmtcs:3570 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2008,
DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
-
https://doi.org/10.46298/dmtcs.3570
Random Records and Cuttings in Split Trees: Extended Abstract
Authors: Cecilia Holmgren 1
NULL
Cecilia Holmgren
1 Department of Mathematics [Uppsala]
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.
Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: Random Trees,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
2 Documents citing this article
Source : OpenCitations
Addario-Berry, Louigi; Broutin, Nicolas; Holmgren, Cecilia, 2014, Cutting Down Trees With A Markov Chainsaw, The Annals Of Applied Probability, 24, 6, 10.1214/13-aap978.
Dhersin, Jean-StĂŠphane; MĂśhle, Martin, 2013, On The External Branches Of Coalescents With Multiple Collisions, Electronic Journal Of Probability, 18, none, 10.1214/ejp.v18-2286.