Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T01:45:40.121Z Has data issue: false hasContentIssue false
  • English
  • Français

On a random search tree: asymptotic enumeration of vertices by distance from leaves

Part of: Graph theory Combinatorics Extremal combinatorics Combinatorial probability Lattices

Published online by Cambridge University Press:  08 September 2017

Miklós Bóna  and
Boris Pittel
Miklós Bóna*
Affiliation:
University of Florida
Boris Pittel*
Affiliation:
The Ohio State University
*
* Postal address: Department of Mathematics, University of Florida, 358 Little Hall, Gainesville, FL 32611-8105, USA. Email address: bona@ufl.edu
** Postal address: Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, OH 43210-1175, USA. Email address: bgp@math.ohio-state.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A random binary search tree grown from the uniformly random permutation of [n] is studied. We analyze the exact and asymptotic counts of vertices by rank, the distance from the set of leaves. The asymptotic fraction c k of vertices of a fixed rank k ≥ 0 is shown to decay exponentially with k. We prove that the ranks of the uniformly random, fixed size sample of vertices are asymptotically independent, each having the distribution {c k }. Notoriously hard to compute, the exact fractions c k have been determined for k ≤ 3 only. We present a shortcut enabling us to compute c 4 and c 5 as well; both are ratios of enormous integers, the denominator of c 5 being 274 digits long. Prompted by the data, we prove that, in sharp contrast, the largest prime divisor of the denominator of c k is at most 2k+1 + 1. We conjecture that, in fact, the prime divisors of every denominator for k > 1 form a single interval, from 2 to the largest prime not exceeding 2k+1 + 1.

Keywords

Search treerootleavesrankenumerationasymptoticdistributionnumerical data

MSC classification

Primary: 05A05: Permutations, words, matrices
Secondary: 05A15: Exact enumeration problems, generating functions 05A16: Asymptotic enumeration 05C05: Trees 06B05: Structure theory 05C80: Random graphs 05D40: Probabilistic methods 60C05: Combinatorial probability

Information

Type
Research Article
Information
Advances in Applied Probability , Volume 49 , Issue 3 , September 2017 , pp. 850 - 876
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Prob. 1, 228–266. Google Scholar
[2] Bóna, M. (2014). k-protected vertices in binary search trees. Adv. Appl. Math. 53, 1–11. CrossRefGoogle Scholar
[3] Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach. 33, 489–498. Google Scholar
[4] Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Structures Algorithms 2, 303–315. Google Scholar
[5] Devroye, L. and Janson, S. (2014). Protected nodes and fringe subtrees in some random trees. Electron. Commun. Prob. 19, 6. Google Scholar
[6] Drmota, M. (2009). Random Trees: An Interplay Between Combinatorics and Probability. Springer, Vienna. Google Scholar
[7] Du, R. R. X. and Prodinger, H. (2012). Notes on protected nodes in digital search trees. Appl. Math. Lett. 25, 1025–1028. Google Scholar
[8] Flajolet, P. and Sedgewick, R. (2009). Analytic Combinatorics. Cambridge University Press, Cambridge, UK. Google Scholar
[9] Fuchs, M., Lee, C.-K. and Yu, G.-R. (2016). On 2-protected nodes in random digital trees. Theoret. Comput. Sci. 622, 111–122. Google Scholar
[10] Holmgren, C. and Janson, S. (2015). Asymptotic distribution of two-protected nodes in ternary search trees. Electron J. Prob. 20, 9. Google Scholar
[11] Kesten, H. and Pittel, B. (1996). A local limit theorem for the number of nodes, the height, and the number of final leaves in a critical branching process tree. Random Structures Algorithms 8, 243–299. Google Scholar
[12] Kolchin, V. F. (1978). Moment of degeneration of a branching process and height of a random tree. Math. Notes Acad. Sci. USSR 24, 954–961. Google Scholar
[13] Mahmoud, H. and Pittel, B. (1984). On the most probable shape of a search tree grown from a random permutation. SIAM J. Algebraic Discrete Meth. 5, 69–81. Google Scholar
[14] Mahmoud, H. M. and Ward, M. D. (2012). Asymptotic distribution of two-protected nodes in random binary search trees. Appl. Math. Lett. 25, 2218–2222. Google Scholar
[15] Mahmoud, H. M. and Ward, M. D. (2015). Asymptotic properties of protected notes in random recursive trees. J. Appl. Prob. 52, 290–297. Google Scholar
[16] Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, Berlin. Google Scholar
[17] Pittel, B. (1984). On growing random binary trees. J. Math. Anal. Appl. 103, 461–480. Google Scholar
[18] Pittel, B. (1994). Note on the heights of random recursive trees and random m-ary search trees. Random Structures Algorithms 5, 337–347. Google Scholar