Article contents
An almost sure result for path lengths in binary search trees
Published online by Cambridge University Press: 22 February 2016
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
MSC classification
- Type
- General Applied Probability
- Information
- Copyright
- Copyright © Applied Probability Trust 2003
References
- 1
- Cited by