zbMATH — the first resource for mathematics

Random records and cuttings in binary search trees. (English) Zbl 1215.05162
Summary: We study the number of random records in a binary search tree with $$n$$ vertices (or equivalently, the number of cuttings required to eliminate the tree). We show that a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. The asymptotic distribution of the (normalized) number of records or cuts is found to be weakly 1-stable.

MSC:
 05C80 Random graphs (graph-theoretic aspects) 05C05 Trees 60F99 Limit theorems in probability theory
Full Text:
References:
 [1] Knuth, The Art of Computer Programming III: Sorting and Searching (2002) [2] DOI: 10.1214/aoap/1015345394 · Zbl 1012.60038 [3] Knessl, Discrete Math. Theor. Comput. Sci. no. 2 pp 43– (1999) [4] Kallenberg, Foundations of Modern Probability (2002) [5] Holmgren, Discrete Math. Theor. Comput. Sci. AI pp 269– (2008) [6] DOI: 10.1017/S1446788700006698 · Zbl 0196.27602 [7] Janson, Random Graphs (2000) [8] Gut, Probability: A Graduate Course (2005) · Zbl 1076.60001 [9] DOI: 10.1002/rsa.20086 · Zbl 1120.05083 [10] Feller, An Introduction to Probability Theory and Its Applications (1971) · Zbl 0219.60003 [11] Janson, Mathematics and Computer Science III pp 241– (2004) [12] DOI: 10.1016/S0196-6774(02)00216-X · Zbl 1011.68028 [13] Iksanov, Electron. Commun. Prob. 12 pp 28– (2007) · Zbl 1133.60012 [14] DOI: 10.1002/rsa.20233 · Zbl 1187.05068 [15] Devroye, Stein’s Method and Applications pp 47– (2005) [16] Devroye, Probabilistic Methods for Algorithmic Discrete Mathematics pp 249– (1998) [17] Devroye, J. Assoc. Comput. Mach. 33 pp 489– (1986) · Zbl 0741.05062 [18] Knuth, The Art of Computer Programming I: Fundamental Algorithms (1997) · Zbl 0895.68055
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.