Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T22:35:17.485Z Has data issue: false hasContentIssue false
  • English
  • Français

Subtree Sizes in Recursive Trees and Binary Search Trees: Berry–Esseen Bounds and Poisson Approximations

Published online by Cambridge University Press:  01 September 2008

MICHAEL FUCHS
MICHAEL FUCHS*
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 300, Taiwan (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We study the number of subtrees on the fringe of random recursive trees and random binary search trees whose limit law is known to be either normal or Poisson or degenerate depending on the size of the subtree. We introduce a new approach to this problem which helps us to further clarify this phenomenon. More precisely, we derive optimal Berry–Esseen bounds and local limit theorems for the normal range and prove a Poisson approximation result as the subtree size tends to infinity.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 5 , September 2008 , pp. 661 - 680
Copyright
Copyright © Cambridge University Press 2008

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]Aldous, D. J. (1991) Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 228–266.CrossRefGoogle Scholar
[2]Bai, Z.-D., Hwang, H.-K. and Tsai, T.-H. (2003) Berry–Esseen bounds for the number of maxima in planar regions. Electron. J. Probab. 8 #9.CrossRefGoogle Scholar
[3]Baron, G., Drmota, M. and Mutafchiev, L. (1996) Predecessors in random mappings. Combin. Probab. Comput. 5 317–335.CrossRefGoogle Scholar
[4]Blum, M. G. B. and François, O. (2005) Minimal clade size and external branch length under the neutral coalescent. Adv. Appl. Probab. 37 647–662.CrossRefGoogle Scholar
[5]Chang, H. and Fuchs, M. (2008) Limit theorems for patterns in phylogenetic trees. Manuscript.Google Scholar
[6]Chern, H.-H., Fuchs, M. and Hwang, H.-K. (2007) Phase changes in random point quadtrees. ACM Trans. Alg. 3 #12.Google Scholar
[7]Devroye, L. (1991) Limit laws for local counters in random binary search trees. Random Struct. Alg. 2 303–315.CrossRefGoogle Scholar
[8]Drmota, M. and Hwang, H.-K. (2005) Profiles of random trees: Correlation and width of random recursive trees and binary search trees. Adv. Appl. Probab. 37 321–341.CrossRefGoogle Scholar
[9]Drmota, M., Janson, S. and Neininger, R. (2008) A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 288–333.CrossRefGoogle Scholar
[10]Feng, Q., Mahmoud, H. and Panholzer, A. (2008) Phase changes in subtree varieties in random recursive trees and binary search trees. SIAM J. Discrete Math. 22 160–184.CrossRefGoogle Scholar
[11]Feng, Q., Mahmoud, H. and Su, C. (2007) On the variety of subtrees in a random recursive tree. Technical report, The George Washington University, Washington, DC.Google Scholar
[12]Feng, Q., Miao, B. and Su, C. (2006) On the subtrees of binary search trees. Chinese J. Appl. Probab. Statist. 22 304–310.Google Scholar
[13]Flajolet, P., Gourdon, X. and Martinez, C. (1997) Patterns in random binary search trees. Random Struct. Alg. 11 223–244.3.0.CO;2-2>CrossRefGoogle Scholar
[14]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.CrossRefGoogle Scholar
[15]Hwang, H.-K. (2003) Second phase changes in random m-ary search trees and generalized Quicksort: Convergence rates. Ann. Probab. 31 609–629.CrossRefGoogle Scholar
[16]Hwang, H.-K. (2007) Profiles of random trees: Plane-oriented recursive trees. Random Struct. Alg. 30 380–413.CrossRefGoogle Scholar
[17]Hwang, H.-K., Nicodème, P., Park, G. and Szpankowski, W. (2008) Profiles of tries. Submitted.Google Scholar
[18]Rosenberg, N. A. (2006) The mean and variance of the numbers of r-pronged nodes and r-caterpillars in Yule-generated genealogical trees. Ann. Combin. 10 129–146.CrossRefGoogle Scholar