×

zbMATH — the first resource for mathematics

Search trees: metric aspects and strong limit theorems. (English) Zbl 1294.60009
Summary: We consider random binary trees that appear as the output of certain standard algorithms for sorting and searching if the input is random. We introduce the subtree size metric on search trees and show that the resulting metric spaces converge with probability 1. This is then used to obtain almost sure convergence for various tree functionals, together with representations of the respective limit random variables as functions of the limit tree.

MSC:
60B99 Probability theory on algebraic and topological structures
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
68Q25 Analysis of algorithms and problem complexity
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] Biggins, J. D. (1977). Chernoff’s theorem in the branching random walk. J. Appl. Probab. 14 630-636. · Zbl 0373.60090
[2] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[3] Blackwell, D. and Kendall, D. (1964). The Martin boundary of Pólya’s urn scheme, and an application to stochastic population growth. J. Appl. Probab. 1 284-296. · Zbl 0129.10702
[4] Burago, D., Burago, Y. and Ivanov, S. (2001). A Course in Metric Geometry. Graduate Studies in Mathematics 33 . Amer. Math. Soc., Providence, RI. · Zbl 0981.51016
[5] Chauvin, B., Drmota, M. and Jabbour-Hattab, J. (2001). The profile of binary search trees. Ann. Appl. Probab. 11 1042-1062. · Zbl 1012.60038
[6] Chauvin, B., Klein, T., Marckert, J. F. and Rouault, A. (2005). Martingales and profile of binary search trees. Electron. J. Probab. 10 420-435 (electronic). · Zbl 1109.60059
[7] Chauvin, B. and Rouault, A. (2004). Connecting Yule processes, bisection and binary search tree via martingales. J. Iran. Stat. Soc. ( JIRSS ) 3 89-116. · Zbl 06657082
[8] Dennert, F. (2009). Zufällige binäre Bäume: Algorithmen, Asymptotik und Statistik. Ph.D. thesis, Leibniz Univ. Hannover. · Zbl 1243.05001
[9] Dennert, F. and Grübel, R. (2010). On the subtree size profile of binary search trees. Combin. Probab. Comput. 19 561-578. · Zbl 1198.05135
[10] Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 489-498. · Zbl 0741.05062
[11] Devroye, L. (1998). Branching processes and their applications in the analysis of tree structures and tree algorithms. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin. 16 249-314. Springer, Berlin. · Zbl 0924.60077
[12] Doob, J. L. (1959). Discrete potential theory and boundaries. J. Math. Mech. 8 433-458; erratum 993. · Zbl 0101.11503
[13] Drmota, M. (2009). Random Trees : An Interplay Between Combinatorics and Probability . Springer, Vienna. · Zbl 1170.05022
[14] Drmota, M., Janson, S. and Neininger, R. (2008). A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 288-333. · Zbl 1143.68019
[15] Evans, S. N. (2008). Probability and Real Trees. Lecture Notes in Math. 1920 . Springer, Berlin.
[16] Evans, S. N., Grübel, R. and Wakolbinger, A. (2012). Trickle-down processes and their boundaries. Electron. J. Probab. 17 1-58. · Zbl 1246.60100
[17] Fuchs, M. (2008). Subtree sizes in recursive trees and binary search trees: Berry-Esseen bounds and Poisson approximations. Combin. Probab. Comput. 17 661-680. · Zbl 1159.05305
[18] Fuchs, M., Hwang, H.-K. and Neininger, R. (2006). Profiles of random trees: Limit theorems for random recursive trees and binary search trees. Algorithmica 46 367-407. · Zbl 1106.68083
[19] Grübel, R. (2009). On the silhouette of binary search trees. Ann. Appl. Probab. 19 1781-1802. · Zbl 1203.60040
[20] Jabbour-Hattab, J. (2001). Martingales and large deviations for binary search trees. Random Structures Algorithms 19 112-127. · Zbl 0983.60034
[21] Kallenberg, O. (1997). Foundations of Modern Probability . Springer, New York. · Zbl 0892.60001
[22] Kaĭmanovich, V. A. and Vershik, A. M. (1983). Random walks on discrete groups: Boundary and entropy. Ann. Probab. 11 457-490. · Zbl 0641.60009
[23] Knuth, D. E. (1973). The Art of Computer Programming. Vol. 3: Sorting and Searching . Addison-Wesley, Reading, MA. · Zbl 0302.68010
[24] Mahmoud, H. M. (1992). Evolution of Random Search Trees . Wiley, New York. · Zbl 0762.68033
[25] Neininger, R. (2002). The Wiener index of random trees. Combin. Probab. Comput. 11 587-597. · Zbl 1013.05029
[26] Neveu, J. (1975). Discrete-Parameter Martingales , Revised ed. North-Holland, Amsterdam. · Zbl 0345.60026
[27] Régnier, M. (1989). A limiting distribution for quicksort. RAIRO Inform. Théor. Appl. 23 335-343. · Zbl 0677.68072
[28] Rösler, U. (1991). A limit theorem for “Quicksort.” RAIRO Inform. Théor. Appl. 25 85-100. · Zbl 0718.68026
[29] Woess, W. (2000). Random Walks on Infinite Graphs and Groups. Cambridge Tracts in Mathematics 138 . Cambridge Univ. Press, Cambridge. · Zbl 0951.60002
[30] Woess, W. (2009). Denumerable Markov Chains : Generating Functions , Boundary Theory , Random Walks on Trees . EMS, Zürich. · Zbl 1219.60001
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.