\(k\)-protected vertices in binary search trees. (English) Zbl 1281.05004
Summary: We show that for every \(k\), the probability that a randomly selected vertex of a random binary search tree on \(n\) nodes is at distance \(k-1\) from the closest leaf converges to a rational constant \(c_k\) as \(n\) goes to infinity.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 05A16 | Asymptotic enumeration |
| 05C30 | Enumeration in graph theory |
| 05C05 | Trees |
| 05C12 | Distance in graphs |
| 68P05 | Data structures |
References:
| [1] | Bóna, M., A Walk Through Combinatorics (2011), World Scientific: World Scientific Singapore · Zbl 1236.05001 |
| [2] | Cheon, G.-S.; Shapiro, L. W., Protected points in ordered trees, Appl. Math. Lett., 21, 516-520 (2008) · Zbl 1138.05308 |
| [3] | Devroye, L., Limit laws for local counters in random binary search trees, Random Structures Algorithms, 2, 3, 303-315 (1991) · Zbl 0728.60027 |
| [4] | Devroye, L.; Janson, S., Protected nodes and fringe subtrees in some random trees · Zbl 1355.60015 |
| [5] | Du, R. R.; Prodinger, H., Notes on protected nodes in digital search trees, Appl. Math. Lett., 25, 1025-1028 (2012) · Zbl 1244.05055 |
| [6] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1165.05001 |
| [7] | Mahmoud, H. M., The expected distribution of degrees in random binary search trees, Comp. J., 29, 36-37 (1986) · Zbl 0587.68057 |
| [8] | Mahmoud, H. M.; Ward, M. D., Asymptotic distribution of two-protected nodes in random binary search trees, Appl. Math. Lett., 25, 2218-2222 (2012) · Zbl 1251.05033 |
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.
