Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-27T09:36:41.405Z Has data issue: false hasContentIssue false
  • English
  • Français

EXTREMAL WEIGHTED PATH LENGTHS IN RANDOM BINARY SEARCH TREES

Published online by Cambridge University Press:  15 December 2006

Rafik Aguech ,
Nabil Lasmar  and
Hosam Mahmoud
Rafik Aguech
Affiliation:
Département de Mathématiques, Faculté des Sciences de Monastir, 5019 Monastir, Tunisia, E-mail: [email protected]
Nabil Lasmar
Affiliation:
Département de mathématiques, Institut préparatoire aux études d'ingénieurs de Tunis, IPEIT, Tunis, Tunisia, E-mail: [email protected]
Hosam Mahmoud
Affiliation:
Department of Statistics, The George Washington University, Washington, DC 20052, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider weighted path lengths to the extremal leaves in a random binary search tree. When linearly scaled, the weighted path length to the minimal label has Dickman's infinitely divisible distribution as a limit. By contrast, the weighted path length to the maximal label needs to be centered and scaled to converge to a standard normal variate in distribution. The exercise shows that path lengths associated with different ranks exhibit different behaviors depending on the rank. However, the majority of the ranks have a weighted path length with average behavior similar to that of the weighted path to the maximal node.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 21 , Issue 1 , January 2007 , pp. 133 - 141
Copyright
© 2007 Cambridge University Press

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

REFERENCES

Billingsley, P. (1995). Probability and measure. New York: Wiley.
Devroye, L. (1986). A note on the height of binary search trees. Journal of the ACM 33: 489–498.Google Scholar
Devroye, L. (1987). Branching processes in the analysis of the height of trees. Acta Informatica 24: 277–298.Google Scholar
Devroye, L. (1988). Applications of the theory of records in the study of random trees. Acta Informatica 26: 123–130.Google Scholar
Devroye, L. & Neininger, R. (2004). Distances and finger search in random binary search trees. SIAM Journal on Computing 33: 647–658.Google Scholar
Drmota, M. (2001). An analytic approach to the height of binary search trees. Algorithmica 29: 89–119.Google Scholar
Drmota, M. (2002). The variance of the height of binary search trees. Theoretical Computer Science 270: 913–919.Google Scholar
Hwang, H. & Tsai, T. (2002). Quickselect and Dickman function. Combinatorics, Probability and Computing 11: 353–371.Google Scholar
Kemp, R. (1984). Fundamentals of the average case analysis of particular algorithms. Wiley-Teubner Series in Computer Science. New York: Wiley.
Knuth, D. (1998). The art of computer programming. Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley.
Mahmoud, H. (1992). Evolution of random search trees. New York: Wiley.
Mahmoud, H. (2000). Sorting: A distribution theory. New York: Wiley.CrossRef
Mahmoud, H., Modarres, R., & Smythe, R. (1995). Analysis of Quickselect: An algorithm for order statistics. RAIRO: Theoretical Informatics and Its Applications 29: 255–276.Google Scholar
Mahmoud, H. & Pittel, B. (1984). On the most probable shape of a search tree grown from a random permutation. SIAM Journal on Algebraic and Discrete Methods 5: 69–81.Google Scholar
Pittel, B. (1984). On growing random binary trees. Journal of Mathematical Analysis and Its Applications 103: 461–480.Google Scholar
Reed, B. (2003). The height of a random binary search tree. Journal of the Association for Computing Machinery 50: 306–332.Google Scholar
Robson, J. (1979). The height of binary search trees. The Australian Computer Journal 11: 151–153.Google Scholar