Split Trees – A Unifying Model for Many Important Random Trees of Logarithmic Height: A Brief Survey
Pages 20 - 57
Abstract
Split trees were introduced by Devroye [28] as a novel approach for unifying many important random trees of logarithmic height. They are interesting not least because of their usefulness as models of sorting algorithms in computer science; for instance the well-known Quicksort algorithm (introduced by Hoare [35, 36]) can be depicted as a binary search tree (which is one example of a split tree). A split tree of cardinality n is constructed by distributing n balls (which often represent data items) to a subset of nodes of an infinite tree. In [39], renewal theory was introduced by the author as a novel approach for studying split trees. This approach has proved to be highly useful for investigating such trees and has lead (often in combination with other methods) to several general results valid for all split trees. In this brief survey, we will present split trees, give an introduction to renewal theory in relation to split trees and describe some of the characteristics of split trees including results on the depths for the balls and nodes in the tree, the height (maximal depth) of the tree and the size of the tree in terms of the number of nodes; see [11, 17, 18, 28, 39]. Furthermore, we will briefly describe some of our later results for this large class of random trees, e.g. on the total path length [19], number of cuttings [12, 21, 38] and number of inversions (and more general permutations) [2, 20] as well as on the size of the giant and other components after bond percolation [11, 13].
References
[1]
Addario-Berry L, Broutin N, and Holmgren C Cutting down trees with a Markov chainsaw Ann. Appl. Probab. 2014 24 2297-2339
[2]
Albert M, Holmgren C, Johansson T, and Skerman F Embedding small digraphs and permutations in binary trees and split trees Algorithmica 2020 82 589-615
[3]
Asmussen S Applied Probability and Queues 1987 Chichester Wiley
[4]
Barabási A-L and Albert R Emergence of scaling in random networks Science 1999 286 5439 509-512
[5]
Baur E Percolation on random recursive trees Random. Struct. Alg. 2016 48 655-680
[6]
Bertoin J Almost giant clusters for percolation on large trees with logarithmic heights J. Appl. Probab. 2013 50 3 603-611
[7]
Bertoin J On the non-Gaussian fluctuations of the giant cluster for percolation on random recursive trees Electron. J. Probab. 2014 19 24 1-15
[8]
Bertoin J Sizes of the largest clusters for supercritical percolation on random recursive trees Random Struct. Algorithms 2014 44 1 29-44
[9]
Bertoin, J., Uribe Bravo, G.: Supercritical percolation on large scale-free random trees. Ann. Appl. Probab. 25(1), 81–103 (2015)
[10]
Berzunza G Yule processes with rare mutation and their applications to percolation on -ary trees Electron. J. Probab. 2015 20 43 1-23
[11]
Berzunza, G., Cai, X.S., Holmgren, C.: The asymptotic non-normality of the giant cluster for percolation on random split trees. https://arxiv.org/abs/1902.08109 (2019)
[12]
Berzunza G, Cai XS, and Holmgren C The -cut model in deterministic and random trees Electron. J. Combin. 2021 28 1 1-30
[13]
Berzunza, G., Holmgren, C.: The asymptotic distribution of cluster sizes for supercritical percolation on random split trees. https://arxiv.org/abs/2003.12018 (2020)
[14]
Bollobás, B., Riordan, O.: Percolation. Cambridge University Press, Cambridge (2006)
[15]
Bollobás B and Riordan O Asymptotic normality of the size of the giant component in a random hypergraph Random Struct. Algorithms 2012 41 4 441-450
[16]
Broadbent, S., Hammersley, J.: Percolation processes I. Crystals and mazes. Math. Proc. Cambridge Philos. Soc. 53(3), 629–641 (1957)
[17]
Broutin N and Devroye L Large deviations for the weighted height of an extended class of trees Algorithmica 2006 46 3–4 271-297
[18]
Broutin N, Devroye L, and McLeish E Weighted height of random trees Acta Inform. 2008 45 4 237-277
[19]
Broutin N and Holmgren C The total path length of split trees Ann. Appl. Probab. 2012 22 5 1745-1777
[20]
Cai XS, Holmgren C, Janson S, Johansson T, and Skerman F Inversions in split trees and conditional Galton-Watson trees Comb. Probab. Comput. 2019 28 3 335-364
[21]
Cai XS, Devroye L, Holmgren C, and Skerman F -cut on paths and some trees Electron. J. Probab. 2019 24 53 1-22
[22]
Cai XS and Holmgren C Cutting resilient networks - complete binary trees Electron. J. Combin. 2019 26 4 1-28
[23]
Dagon, D., Gu, G., Lee, C.P., Lee, W.: A taxonomy of botnet structures. In: Twenty-Third Annual Computer Security Applications Conference (ACSAC 2007), pp. 325–333 (2007)
[24]
Devroye L A note on the height of binary search trees J. Assoc. Comput. Mach. 1986 33 489-498
[25]
Devroye L Applications of the theory of records in the study of random trees Acta Inform. 1988 26 123-130
[26]
Devroye L On the height of random -ary search trees Random Struct. Algorithms 1990 1 2 191-203
[27]
Devroye L Habib M, McDiarmid C, Ramirez-Alfonsin J, and Reed B Branching processes and their applications in the analysis of tree structures and tree algorithms Probabilistic Methods for Algorithmic Discrete Mathematics 1998 Berlin Springer 249-314
[28]
Devroye L Universal limit laws for depth in random trees SIAM J. Comput. 1998 28 409-432
[29]
Drmota M Random Trees 2009 Vienna Springer
[30]
Drmota M, Iksanov A, Moehle M, and Roesler U A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree Random Struct. Alg. 2009 34 319-336
[31]
Feller, W.: An Introduction to Probability Theory and Its Applications. Volume II, 2nd edn. Wiley, New York (1971)
[32]
Friedkin E Trie memory Commun. ACM 1960 3 490-500
[33]
Goldschmidt C and Martin J Random recursive trees and the Bolthausen-Sznitman coalescent Electron. J. Probab. 2005 10 718-745
[34]
Grimmett G Percolation 1999 2 Heidelberg Springer
[35]
Hoare CAR Partition (Algorithm 63), Ouicksort (Algorithm 64), and Find (Algorithm 65) Comm. ACM 1961 4 321-322
[36]
Hoare CAR Ouicksort Comput. J. 1962 5 10-15
[37]
Holmgren C Random records and cuttings in binary search trees Comb. Probab. Comput. 2010 19 391-424
[38]
Holmgren C A weakly 1-stable distribution for the number of random records and cuttings in split trees Adv. in Appl. Probab. 2011 43 151-177
[39]
Holmgren C Novel characteristics of split trees by use of renewal theory Electron. J. Probab. 2012 17 1-27
[40]
Jacquet, P., Régnier, M.: Normal limiting distribution for the size and the external path length of tries. Technical report 827, INRIA-Rocquencourt (1988)
[41]
Janson, S.: Random records and cuttings in complete binary trees. In: Mathematics and Computer Science III Birkhäuser, Basel, pp. 241–253 (2004)
[42]
Janson S Random cuttings and records in deterministic and random trees Random Struct. Alg. 2006 29 139-179
[43]
Janson S Random recursive trees and preferential attachment trees are random split trees Comb. Probab. Comput. 2019 28 1 81-99
[44]
Kallenberg O Foundations of Modern Probability 2002 2 New York Springer
[45]
Knuth, D.E.: The Art of Computer Programming. Vol. 3: Sorting and Searching, 2nd edn. Addison-Wesley, Reading (1998)
[46]
Meir A and Moon JW Cutting down random trees J. Australian Math. Soc. 1970 11 313-324
[47]
Neininger R and Rüschendorf L On the internal pathlength of -dimensional quad trees Random Struct. Alg. 1999 15 1 25-41
[48]
Roesler U A limit theorem for “Quicksort” RAIRO Inform. Théor. Appl. 1991 25 85-100
[49]
Roesler U On the analysis of stochastic divide and conquer algorithms Algorithmica 2001 29 1–2 238-261
[50]
Schweinsberg J Dynamics of the evolving Bolthausen-Sznitman coalecent Electron. J. Probab. 2012 17 91 1-50
[51]
Seierstad TG On the normality of giant components Random Struct. Algorithms 2013 43 4 452-485
[52]
Stepanov, V.E.: Phase transitions in random graphs. Teor. Verojatnost. i Primenen. 15, 200–216 (1970)
Recommendations
Embedding Small Digraphs and Permutations in Binary Trees and Split Trees
AbstractWe investigate the number of permutations that occur in random labellings of trees. This is a generalisation of the number of subpermutations occurring in a random permutation. It also generalises some recent results on the number of inversions in ...
The height of a random binary search tree
Let Hn be the height of a random binary search tree on n nodes. We show that there exist constants α = 4.311… and β = 1.953… such that E(Hn) = αln n − βln ln n + O(1), We also show that Var(Hn) = O(1).
On the Variance of the Height of Random Binary Search Trees
Let $H_n$ be the height of a random binary search tree on $n$ nodes. We show that there exists a constant $\alpha = 4.31107\ldots$ such that ${\rm P} \{ |H_n - \alpha \log n | > \beta \log \log n \} \to 0$, where $\beta>15 \alpha / \ln 2 = 93.2933\...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2021
552 pages
ISBN:978-3-030-76656-6
DOI:10.1007/978-3-030-76657-3
- Editors:
- Joakim Lindblad,
- Filip Malmberg,
- Nataša Sladoje
© Springer Nature Switzerland AG 2021.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 24 May 2021
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 08 Mar 2025