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 AbstractArticle
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]
Bibliographic References
3 Documents citing this article
Louigi Addario-Berry;Nicolas Broutin;Cecilia Holmgren, 2014, Cutting down trees with a Markov chainsaw, The Annals of applied probability/The annals of applied probability, 24, 6, 10.1214/13-aap978, https://doi.org/10.1214/13-aap978.