Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-09T06:53:40.856Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Subtree Size Profile of Binary Search trees

Published online by Cambridge University Press:  22 January 2010

FLORIAN DENNERT  and
RUDOLF GRÜBEL
FLORIAN DENNERT
Affiliation:
Institut für Mathematische Stochastik, Leibniz Universität Hannover, Postfach 6009, D-30060 Hannover, Germany (e-mail: dennert@stochastik.uni-hannover.de, rgrubel@stochastik.uni-hannover.de)
RUDOLF GRÜBEL
Affiliation:
Institut für Mathematische Stochastik, Leibniz Universität Hannover, Postfach 6009, D-30060 Hannover, Germany (e-mail: dennert@stochastik.uni-hannover.de, rgrubel@stochastik.uni-hannover.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 4 , July 2010 , pp. 561 - 578
Copyright
Copyright © Cambridge University Press 2010

References

[1]Billingsley, P. (1968) Convergence of Probability Measures, Wiley, New York.Google Scholar
[2]Chauvin, B., Drmota, M. and Jabbour-Hattab, J. (2001) The profile of binary search trees. Ann. Appl. Probab. 11 1042–1062.CrossRefGoogle Scholar
[3]Dennert, F. (2009) Zufällige binäre Bäume: Algorithmen, Asymptotik und Statistik. Dissertation, Leibniz Universität Hannover.Google Scholar
[4]Devroye, L. (1991) Limit laws for local counters in random binary search trees. Random Struct. Alg. 2 303–315.CrossRefGoogle Scholar
[5]Drmota, M., Janson, S. and Neininger, R. (2008) A functional limit theorem for the profile of search trees. Ann. Appl. Probab. 18 288–333.Google Scholar
[6]Evans, S., Grübel, R. and Wakolbinger, A. (2009) Boundary theory for randomly growing binary trees. In preparation.Google Scholar
[7]Feng, Q., Mahmoud, H. M. and Panholzer, A. (2008) Phase changes in subtree varieties in random recursive and binary search trees. SIAM J. Discrete Math. 22 160–184.Google Scholar
[8]Fuchs, M. (2008) Subtree sizes in recursive trees and binary search trees: Berry–Esseen bounds and Poisson approximations. Combin. Probab. Comput. 17 661–680.CrossRefGoogle Scholar
[9]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
[10]Mahmoud, H. M. (1992) Evolution of Random Search Trees, Wiley, New York.Google Scholar
[11]Neininger, R. and Rüschendorf, L. (2004) A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab. 14 378–418.CrossRefGoogle Scholar
[12]Sedgewick, R. and Flajolet, P. (1996) An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading.Google Scholar