Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T16:37:47.217Z Has data issue: false hasContentIssue false
  • English
  • Français

Random Records and Cuttings in Binary Search Trees

Published online by Cambridge University Press:  05 March 2010

CECILIA HOLMGREN
CECILIA HOLMGREN*
Affiliation:
Uppsala Universitet, Matematiska Institutionen, Box 480 751 06 Uppsala, Sweden (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 3 , May 2010 , pp. 391 - 424
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Chauvin, B., Drmota, M. and Jabbour Hattab, J. (2001) The profile of binary search trees. Ann. Applied Probab. 11 1042–1062.CrossRefGoogle Scholar
[2]Devroye, L. (1986) A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 489–498.Google Scholar
[3]Devroye, L. (1998) Branching processes and their applications in the analysis of tree structures and tree algorithms. In Probabilistic Methods for Algorithmic Discrete Mathematics, Vol. 16 (Habib, et al. , eds), Springer, Berlin, pp. 249–314.Google Scholar
[4]Devroye, L. (2005) Applications of Stein's method in the analysis of random binary search trees. In Stein's Method and Applications (Chen, and Barbour, , eds), Vol. 5 of Inst. for Math. Sci. Lect. Notes Ser., World Scientific, Singapore, pp. 47–297.Google Scholar
[5]Drmota, M., Iksanov, A., Moehle, M. and Roesler, U. (2009) A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Struct. Alg. 34 319–336.CrossRefGoogle Scholar
[6]Fill, J. A. and Janson, S. (2002) Quicksort asymptotics. J. Algorithms 44 4–28.CrossRefGoogle Scholar
[7]Feller, W. (1971) An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn, Wiley, New York.Google Scholar
[8]Gut, A. (2005) Probability: A Graduate Course, Springer, New York.Google Scholar
[9]Holmgren, C. (2008) Random records and cuttings in split trees: Extended abstract. Discrete Math. Theor. Comput. Sci. (DMTCS Proceedings) AI, 269–282.Google Scholar
[10]Holmgren, C. (2009) A weakly 1-stable limiting distribution for the number of random records and cuttings in split trees. Submitted.Google Scholar
[11]Iksanov, A. and Moehle, M. (2007) A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Prob. 12 28–35.Google Scholar
[12]Janson, S. (2004) Random records and cuttings in complete binary trees. In Mathematics and Computer Science III, Birkhäuser, Basel, pp. 241–253.CrossRefGoogle Scholar
[13]Janson, S. (2006) Random cuttings and records in deterministic and random trees. Random Struct. Alg. 29 139–179.CrossRefGoogle Scholar
[14]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley, New York.CrossRefGoogle Scholar
[15]Kallenberg, O. (2002) Foundations of Modern Probability, 2nd edn, Springer.Google Scholar
[16]Knessl, C. and Szpankowski, W. (1999) Quicksort algorithm again revisited. Discrete Math. Theor. Comput. Sci. no. 2 43–64.Google Scholar
[17]Knuth, D. E. (1997) The Art of Computer Programming I: Fundamental Algorithms, 3rd edn, Addison-Wesley.Google Scholar
[18]Knuth, D. E. (2002) The Art of Computer Programming III: Sorting and Searching, Addison-Wesley.Google Scholar
[19]Meir, A. and Moon, J. W. (1970) Cutting down random trees. J. Australian Math. Soc. 11 313–324.Google Scholar