Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-27T07:25:50.624Z Has data issue: false hasContentIssue false
  • English
  • Français

An almost sure result for path lengths in binary search trees

Part of: Theory of computing Limit theorems Combinatorial probability Theory of data

Published online by Cambridge University Press:  22 February 2016

F. M. Dekking  and
L. E. Meester
F. M. Dekking*
Affiliation:
Thomas Stieltjes Institute for Mathematics and Delft University of Technology
L. E. Meester*
Affiliation:
Thomas Stieltjes Institute for Mathematics and Delft University of Technology
*
∗ Postal address: Department of ITS, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands.
∗ Postal address: Department of ITS, Delft University of Technology, Mekelweg 4, 2628 CD Delft, The Netherlands.
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper studies path lengths in random binary search trees under the random permutation model. It is known that the total path length, when properly normalized, converges almost surely to a nondegenerate random variable Z. The limit distribution is commonly referred to as the ‘quicksort distribution’. For the class 𝒜m of finite binary trees with at most m nodes we partition the external nodes of the binary search tree according to the largest tree that each external node belongs to. Thus, the external path length is divided into parts, each part associated with a tree in 𝒜m. We show that the vector of these path lengths, after normalization, converges almost surely to a constant vector times Z.

Keywords

Binary search treerandom permutation modelpath lengthalmost sure convergencequicksort distribution

MSC classification

Primary: 68P05: Data structures 60C05: Combinatorial probability
Secondary: 60F15: Strong theorems 68Q25: Analysis of algorithms and problem complexity
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 35 , Issue 2 , June 2003 , pp. 363 - 376
Copyright
Copyright © Applied Probability Trust 2003 

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., Flannery, B. and Palacios, J. L. (1988). Two applications of urn processes: the fringe analysis of search trees and the simulation of quasi-stationary distributions of Markov chains. Prob. Eng. Inf. Sci. 2, 293–307.Google Scholar
[2] Dekking, F. M., De Graaf, S. and Meester, L. E. (2000). On the node structure of binary search trees. In Mathematics and Computer Science (Versailles, 2000), eds Gardy, D. and Mokkadem, A., Birkhäuser, Basel, pp. 31–40.Google Scholar
[3] Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach. 33, 489–498.Google Scholar
[4] Fill, J. A. (1996). On the distribution of binary search trees under the random permutation model. Random Structures Algorithms 8, 1–25.Google Scholar
[5] Flajolet, P., Gourdon, X. and Martínez, C. (1997). Patterns in random binary search trees. Random Structures Algorithms 11, 223–244.Google Scholar
[6] Knuth, D. E. (1973). The Art of Computer Programming, Vol. 3, Sorting and Searching. Addison-Wesley, Reading, MA.Google Scholar
[7] Mahmoud, H. M. (1992). Evolution of Random Search Trees. John Wiley, New York.Google Scholar
[8] Mahmoud, H. M. (1998). On rotations in fringe-balanced binary trees. Inf. Process. Lett. 65, 41–46.Google Scholar
[9] Pittel, B. (1985). Asymptotical growth of a class of random trees. Ann. Prob. 13, 414–427.Google Scholar
[10] Poblete, P. V. and Munro, J. I. (1985). The analysis of a fringe heuristic for binary search trees. J. Algorithms 6, 336–350.Google Scholar
[11] Régnier, M., (1989). A limiting distribution for quicksort. RAIRO Inf. Théorique Appl. 23, 335–343.Google Scholar
[12] Rösler, U., (1991). A limit theorem for ‘quicksort’. RAIRO Inf. Théorique Appl. 25, 85–100.CrossRefGoogle Scholar
[13] Smythe, R. T. (1996). Central limit theorems for urn models. Stoch. Process. Appl. 65, 115–137.Google Scholar