One-sided variations on binary search trees. (English) Zbl 1099.68601

Summary: We investigate incomplete one-sided variants of binary search trees. The (normed) size of each variant is studied, and convergence to a Gaussian law is proved in each case by asymptotically solving recurrences. These variations are also discussed within the scope of the contraction method with degenerate limit equations. In an incomplete tree the size determines most other parameters of interest, such as the height and the internal path length.


68P05 Data structures
05C05 Trees
60C05 Combinatorial probability
Full Text: DOI


[1] Arora, S. and Dent, W. (1969). Randomized binary search technique,Communications of the ACM,12, 77–80. · Zbl 0167.45901
[2] Chassaing, P. and Marchand, R. (2002). Cutting a random tree (and UNION-FIND algorithms) (manuscript).
[3] Devroye, L. (1988). Applications of the theory of records in the study of random trees,Acta Inform.,16, 123–130. · Zbl 0656.68065
[4] Drmota, M. (2002). The random bisection problem and the distribution of the height of binary search trees (manuscript). · Zbl 0988.68059
[5] Fill, J., Mahmoud, H. and Szpankowski, W. (1996). On the distribution for the duration of a randomized leader election algorithm,Ann. Appl. Probab.,6, 1260–1283. · Zbl 0870.60018
[6] Itoh, Y. and Mahmoud, H. (2003). One-sided variations on interval trees,J. Appl. Probab.,40, 1–17. · Zbl 1043.05036
[7] Kemp, R. (1984).Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner, Stuttgart. · Zbl 0638.68026
[8] Knuth, D. (1998).The Art of Computer Programming, Vol. III: Searching and Sorting, Addison-Wesley, Reading Massachusetts. · Zbl 0895.65001
[9] Mahmoud, H. (1992).Evolution of Random Search Trees, Wiley, New York. · Zbl 0762.68033
[10] Mahmound, H. (2000).Sorting: A Distribution Theory, Wiley, New York.
[11] Mahmound, H. and Neininger, R. (2003). Distribution of distances in random binary search trees,Ann. Appl. Probab.,13, 253–276. · Zbl 1033.60007
[12] Martínez, C., Panholzer, A. and Prodinger, H. (1998). Descendants and ascendants in random search trees,Electronic Journal of Combinatorics,5, R20; 29 pages+Appendix (10 pages). · Zbl 0892.05004
[13] Meir, A. and Moon, J. (1970). Cutting down random trees,J Austral. Math. Soc.,11, 313–324. · Zbl 0196.27602
[14] Neininger, R. (2002). On a multivariate contraction method for random recursive structures with applications to Quicksort,Random Structures Algorithms,19, 498–524. · Zbl 0990.68054
[15] Neininger, R. and Rüschendorf, L. (2002). On the contraction method with degenerate limit equation (manuscript). · Zbl 1060.60005
[16] Prodinger, H. (1993). How to select a loser,Discrete Math.,120, 149–159. · Zbl 0795.90103
[17] Rachev, S. and Rüschendorf, L. (1995). Probability metrics and recursive algorithms,Adv. in Appl. Probab.,27, 770–799. · Zbl 0829.60094
[18] Rösler, U. (1991). A limit theorem for ”Quicksort”,RAIRO Inform. Théor. Appl.,25, 85–100. · Zbl 0718.68026
[19] Rösler, U. (2001). On the analysis of stochastic divide and conquer algorithms,Algorithmica,29, 238–261. · Zbl 0967.68168
[20] Rösler, U. and Rüschendorf, L. (2001). The contraction method for recursive algorithms,Algorithmica,29, 3–33. · Zbl 0967.68166
[21] Sibuya, M. and Itoh, Y. (1987). Random sequential bisection and its associated binary tree,Ann. Inst. Statist. Math.,39, 69–84. · Zbl 0622.60020
[22] Zolotarev, V. M. (1976). Approximation of the distributions of sums of independent random variables with values in infinite-dimensional spaces,Theory Probab. Appl.,21, 721–737. · Zbl 0378.60003
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.