Protected nodes and fringe subtrees in some random trees

Luc Devroye (McGill University)
Svante Janson (Uppsala University)

Abstract


We study protected nodes in various classes of random rooted trees by putting them in the general context of fringe subtrees introduced by Aldous (1991). Several types of random trees are considered: simply generated trees (or conditioned Galton-Watson trees), which includes several cases treated separately by other authors, binary search trees and random recursive trees. This gives unified and simple proofs of several earlier results, as well as new results.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-10

Publication Date: February 5, 2014

DOI: 10.1214/ECP.v19-3048

References

  • Aldous, David. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228--266. MR1102319
  • Aldous, David. The continuum random tree. II. An overview. Stochastic analysis (Durham, 1990), 23--70, London Math. Soc. Lecture Note Ser., 167, Cambridge Univ. Press, Cambridge, 1991. MR1166406
  • Bennies, Jörgen; Kersting, Götz. A random walk approach to Galton-Watson trees. J. Theoret. Probab. 13 (2000), no. 3, 777--803. MR1785529
  • Bóna, Miklós. $k$-Protected vertices in binary search trees. Adv. in Appl. Math. 53 (2014), 1--11. MR3149690
  • Cheon, Gi-Sang; Shapiro, Louis W. Protected points in ordered trees. Appl. Math. Lett. 21 (2008), no. 5, 516--520. MR2402845
  • Devroye, Luc. Branching processes and their applications in the analysis of tree structures and tree algorithms. Probabilistic methods for algorithmic discrete mathematics, 249--314, Algorithms Combin., 16, Springer, Berlin, 1998. MR1678582
  • Devroye, Luc. Limit laws for sums of functions of subtrees of random binary search trees. SIAM J. Comput. 32 (2002/03), no. 1, 152--171. MR1954858
  • Devroye, Luc; Fawzi, Omar; Fraiman, Nicolas. Depth properties of scaled attachment random recursive trees. Random Structures Algorithms 41 (2012), no. 1, 66--98. MR2943427
  • Drmota, Michael. Random trees. An interplay between combinatorics and probability. SpringerWienNewYork, Vienna, 2009. xviii+458 pp. ISBN: 978-3-211-75355-2 MR2484382
  • Du, Rosena R. X.; Prodinger, Helmut. Notes on protected nodes in digital search trees. Appl. Math. Lett. 25 (2012), no. 6, 1025--1028. MR2902374
  • Gaither, Jeffrey; Homma, Yushi; Sellke, Mark; Ward, Mark Daniel. On the number of 2-protected nodes in tries and suffix trees. 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), 381--397, Discrete Math. Theor. Comput. Sci. Proc., AQ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012. MR2957345
  • Jeffrey Gaither and Mark Daniel Ward, The variance of the number of 2-protected nodes in a trie. phProceedings, Tenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2013 (New Orleans 2013), SIAM, Philadephia, PA, 2013, 43--51.
  • Cecilia Holmgren and Svante Janson, Limit laws for functions of fringe trees for binary search trees and recursive trees. In preparation.
  • Janson, Svante. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv. 9 (2012), 103--252. MR2908619
  • Kennedy, Douglas P. The Galton-Watson process conditioned on the total progeny. J. Appl. Probability 12 (1975), no. 4, 800--806. MR0386042
  • Mahmoud, Hosam M.; Ward, Mark Daniel. Asymptotic distribution of two-protected nodes in random binary search trees. Appl. Math. Lett. 25 (2012), no. 12, 2218--2222. MR2967819
  • Hosam H. Mahmoud and Mark Daniel Ward, Asymptotic properties of protected nodes in random recursive trees. Preprint, 2013.
  • Mansour, Toufik. Protected points in $k$-ary trees. Appl. Math. Lett. 24 (2011), no. 4, 478--480. MR2749730
  • Smythe, Robert T.; Mahmoud, Hosam M. A survey of recursive trees. (Ukrainian) ; translated from Teor. Ĭmovīr. Mat. Stat. No. 51 (1994), 1--29 Theory Probab. Math. Statist. No. 51 (1995), 1--27 (1996) MR1445048
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.