Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-26T02:02:34.893Z Has data issue: false hasContentIssue false
  • English
  • Français

Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model

Published online by Cambridge University Press:  12 September 2008

Robert P. Dobrow  and
James Allen Fill
Robert P. Dobrow
Affiliation:
Division of Mathematics and Computer Science, Truman State University, Kirksville, MO 63501, USA (e-mail: [email protected])
James Allen Fill
Affiliation:
Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, MD 21218-2692, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Multiway trees, also known as m–ary search trees, are data structures generalising binary search trees. A common probability model for analysing the behaviour of these structures is the random permutation model. The probability mass function Q on the set of m–ary search trees under the random permutation model is the distribution induced by sequentially inserting the records of a uniformly random permutation into an initially empty m–ary search tree. We study some basic properties of the functional Q, which serves as a measure of the ‘shape’ of the tree. In particular, we determine exact and asymptotic expressions for the maximum and minimum values of Q and identify and count the trees achieving those values.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 5 , Issue 4 , December 1996 , pp. 351 - 371
Copyright
Copyright © Cambridge University Press 1996

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]Knuth, D. (1973) The Artof Computer Programming, Vol. 1: Fundamental Algorithms, 2nd ed.Addison-Wesley, Reading, MA.Google Scholar
[2]Knuth, D. (1973). The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed.Addison-Wesley, Reading, MA.Google Scholar
[3]Mahmoud, H. (1992) Evolution of Random Search Trees. Wiley, New York.Google Scholar
[4]Muntz, R. and Uzgalis, R. (1971) Dynamic storage allocation for binary search trees in a two-level memory. Proceedings of Princeton Conference on Information Sciences and Systems, Vol. 4, 345–349.Google Scholar
[5]Bayer, R. and McCreight, E. (1972) Organization and maintenance of large ordered indexes. Ada Inform. 1 173–189.Google Scholar
[6]Mahmoud, H. and Pittel, B. (1989) Analysis of the space of search trees under the random insertion algorithm. J. Alg. 10 52–75.CrossRefGoogle Scholar
[7]Devroye, L. (1990) On the height of random m–ary search trees. Rand. Struct. Alg. 1 191–203.CrossRefGoogle Scholar
[8]Pittel, B. (1994) Note on the heights of random recursive trees and random w–ary search trees. Rand. Struct. Alg. 5 337–347.Google Scholar
[9]Fill, J. A. and Dobrow, R. P. (1995) The number of w–ary search trees on n keys. Technical Report #543, Department of Mathematical Sciences, The Johns Hopkins University. Combinatorics, Probability & Computing (to appear.)Google Scholar
[10]Fill, J. A. (1996) On the distribution for binary search trees under the random permutation model. Rand. Struct. Alg. 8 1–25.3.0.CO;2-1>CrossRefGoogle Scholar