Hostname: page-component-7bb8b95d7b-l4ctd Total loading time: 0 Render date: 2024-09-12T10:46:39.508Z Has data issue: false hasContentIssue false
  • English
  • Français

One-sided variations on interval trees

Part of: Graph theory Limit theorems

Published online by Cambridge University Press:  14 July 2016

Yoshiaki Itoh  and
Hosam M. Mahmoud
Yoshiaki Itoh*
Affiliation:
Institute of Statistical Mathematics, Tokyo
Hosam M. Mahmoud*
Affiliation:
George Washington University
*
∗Postal address: Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minatoku, Tokyo 106-8569, Japan. Email address: [email protected]
∗∗Postal address: Department of Statistics, George Washington University, Washington, DC 20052, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

The binary interval tree is a random structure that underlies interval division and parking problems. Five incomplete one-sided variants of binary interval trees are considered, providing additional flavors and variations on the main applications. The size of each variant is studied, and a Gaussian tendency is proved in each case via an analytic approach. Differential equations on half scale and delayed differential equations arise and can be solved asymptotically by local expansions and Tauberian theorems. Unlike the binary case, in an incomplete interval tree the size determines most other parameters of interest, such as the height or the internal path length.

Keywords

Random graphtreelimit distributionhalf-scale differential equationdelayed differential equationTauberian theorem

MSC classification

Primary: 05C05: Trees 60F05: Central limit and other weak theorems
Type
Research Papers
Information
Journal of Applied Probability , Volume 40 , Issue 3 , September 2003 , pp. 654 - 670
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

Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach. 33, 489–498.CrossRefGoogle Scholar
Feller, W. (1971). Theory of Probability and Its Applications, Vol. 2, 2nd edn. John Wiley, New York.Google Scholar
Fill, J., Mahmoud, H., and Szpankowski, W. (1996). On the distribution for the duration of a randomized leader election algorithm. Ann. Appl. Prob. 6, 1260–1283.Google Scholar
Harary, F., and Palmer, E. M. (1973). Graphical Enumeration. Academic Press, New York.Google Scholar
Magnus, W., Oberhettinger, F., and Soni, R. (1966). Formulas and Theorems for the Special Functions of Mathematical Physics. Springer, New York.Google Scholar
Mahmoud, H. (1992). Evolution of Random Search Trees. John Wiley, New York.Google Scholar
Mahmoud, H. (2003). One-sided variations on binary search trees. To appear in Ann. Inst. Statist. Math.CrossRefGoogle Scholar
Neininger, R. and Rüschendorf, L. (2003). On the contraction method with degenerate limit equation. Unpublished manuscript.Google Scholar
Prodinger, H. (1993). How to select a loser. Discrete Math. 120, 149–159.Google Scholar
Rényi, A. (1958). On a one-dimensional random space-filling problem. Pub. Math. Inst. Hungar. Acad. Sci. 3, 109–127.Google Scholar
Riordan, J. (1968). Combinatorial Identities. John Wiley, New York.Google Scholar
Rösler, U. (1991). A limit theorem for ‘quicksort’. RAIRO Inf. Théor. Appl. 25, 85–100.Google Scholar
Sibuya, M., and Itoh, Y. (1987). Random sequential bisection and its associated binary tree. Ann. Inst. Statist. Math. 39, 69–84.Google Scholar