×

On a random search tree: asymptotic enumeration of vertices by distance from leaves. (English) Zbl 1428.05005

Adv. Appl. Probab. 49, No. 3, 850-876 (2017); corrigendum ibid. 54, No. 2, 337-339 (2022).
Summary: 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 ck of vertices of a fixed rank \(k\geq 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\leq 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 \(2^{k+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 \(2^{k+1} + 1\).

MSC:

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
05A16 Asymptotic enumeration
05C05 Trees
06B05 Structure theory of lattices
05C80 Random graphs (graph-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
60C05 Combinatorial probability

References:

[1] Aldous, D. (1991). Asymptotic fringe distributions for general families of random trees. Ann. Appl. Prob.1, 228-266. · Zbl 0733.60016
[2] Bóna, M. (2014). k-protected vertices in binary search trees. Adv. Appl. Math.53, 1-11. · Zbl 1281.05004
[3] Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach.33, 489-498. · Zbl 0741.05062
[4] Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Structures Algorithms2, 303-315. · Zbl 0728.60027
[5] Devroye, L. and Janson, S. (2014). Protected nodes and fringe subtrees in some random trees. Electron. Commun. Prob.19, 6. · Zbl 1355.60015
[6] Drmota, M. (2009). Random Trees: An Interplay Between Combinatorics and Probability. Springer, Vienna. · Zbl 1170.05022
[7] Du, R. R. X. and Prodinger, H. (2012). Notes on protected nodes in digital search trees. Appl. Math. Lett.25, 1025-1028. · Zbl 1244.05055
[8] Flajolet, P. and Sedgewick, R. (2009). Analytic Combinatorics. Cambridge University Press, Cambridge, UK. · Zbl 1165.05001
[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. · Zbl 1336.68047
[10] Holmgren, C. and Janson, S. (2015). Asymptotic distribution of two-protected nodes in ternary search trees. Electron J. Prob.20, 9. · Zbl 1327.60032
[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 Algorithms8, 243-299. · Zbl 0856.60030
[12] Kolchin, V. F. (1978). Moment of degeneration of a branching process and height of a random tree. Math. Notes Acad. Sci. USSR24, 954-961. · Zbl 0415.60079
[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. · Zbl 0529.05002
[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. · Zbl 1251.05033
[15] Mahmoud, H. M. and Ward, M. D. (2015). Asymptotic properties of protected notes in random recursive trees. J. Appl. Prob.52, 290-297. · Zbl 1397.60021
[16] Pitman, J. (2006). Combinatorial Stochastic Processes (Lecture Notes Math. 1875). Springer, Berlin. · Zbl 1103.60004
[17] Pittel, B. (1984). On growing random binary trees. J. Math. Anal. Appl.103, 461-480. · Zbl 0593.60014
[18] Pittel, B. (1994). Note on the heights of random recursive trees and random m-ary search trees. Random Structures Algorithms5, 337-347. · Zbl 0790.05077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.