One-sided variations on interval trees. (English) Zbl 1043.05036

Summary: 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.


05C05 Trees
60F05 Central limit and other weak theorems
34C60 Qualitative investigation and simulation of ordinary differential equation models
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI


[1] Devroye, L. (1986). A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 , 489–498. · Zbl 0741.05062
[2] Feller, W. (1971). Theory of Probability and Its Applications , Vol. 2, 2nd edn. John Wiley, New York. · Zbl 0219.60003
[3] 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. · Zbl 0870.60018
[4] Harary, F. and Palmer, E. M. (1973). Graphical Enumeration. Academic Press, New York. · Zbl 0266.05108
[5] Magnus, W., Oberhettinger, F. and Soni, R. (1966). Formulas and Theorems for the Special Functions of Mathematical Physics . Springer, New York. · Zbl 0143.08502
[6] Mahmoud, H. (1992). Evolution of Random Search Trees . John Wiley, New York. · Zbl 0762.68033
[7] Mahmoud, H. (2003). One-sided variations on binary search trees. To appear in Ann. Inst. Statist. Math. · Zbl 1099.68601
[8] Neininger, R. and Rüschendorf, L. (2003). On the contraction method with degenerate limit equation. Unpublished manuscript. · Zbl 1060.60005
[9] Prodinger, H. (1993). How to select a loser. Discrete Math. 120 , 149–159. · Zbl 0795.90103
[10] Rényi, A. (1958). On a one-dimensional random space-filling problem. Pub. Math. Inst. Hungar. Acad. Sci. 3 , 109–127. · Zbl 0105.11903
[11] Riordan, J. (1968). Combinatorial Identities . John Wiley, New York. · Zbl 0194.00502
[12] Rösler, U. (1991). A limit theorem for ‘quicksort’. RAIRO Inf. Théor. Appl. 25 , 85–100. · Zbl 0718.68026
[13] Sibuya, M. and Itoh, Y. (1987). Random sequential bisection and its associated binary tree. Ann. Inst. Statist. Math. 39 , 69–84. · Zbl 0622.60020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.