On growing random binary trees. (English) Zbl 0593.60014
Let \(Z=(Z_ n)\), \(n\geq 1\), be a sequence of i.i.d. random variables having a continuous distribution function, and let T be a complete infinite binary tree having root \(R_ 0\). The sequence Z and T are then used to construct a sequence of random subtrees \(t_ 1\subset t_ 2\subset...\) of T. Here, the tree \(t_ n\) has root \(R_ 0\) and n vertices labelled by \(Z_ 1,...,Z_ n\). Further let the tree \(T_ n\) be obtained from \(t_ n\) by adding to it all its direct descendants in T. Let \(h_ n\) \((H_ n)\) denote the length of the shortest (longest) path of \(T_ n.\)
The main result (its proof being rather long) of the paper is that there exist two constants \(c_ 1<c_ 2\) such that the limits \[ \lim h_ n/\ln n=c_ 1,\quad \lim H_ n/\ln n=c_ 2 \] exist with probability one. This considerably strengthens a result of J. M. Robson [The height of binary search trees. Aust. Comput. J. 11, 151-153 (1979)].
The main result (its proof being rather long) of the paper is that there exist two constants \(c_ 1<c_ 2\) such that the limits \[ \lim h_ n/\ln n=c_ 1,\quad \lim H_ n/\ln n=c_ 2 \] exist with probability one. This considerably strengthens a result of J. M. Robson [The height of binary search trees. Aust. Comput. J. 11, 151-153 (1979)].
Reviewer: K.Schürger
MSC:
| 60C05 | Combinatorial probability |
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 05C05 | Trees |
| 68W99 | Algorithms in computer science |
References:
| [1] | Comtet, L., Advanced Combinatorics: The Art of Finite and Infinite Expansions (1974), Reidel: Reidel Dordrecht/Boston · Zbl 0283.05001 |
| [2] | De Bruijn, N. G.; Knuth, D. E.; Rice, S. O., The average height of planted plane trees, (Read, R., Graph Theory and Computing (1972), Academic Press: Academic Press New York), 15-22 · Zbl 0247.05106 |
| [3] | Feller, W., An Introduction to Probability Theory and Its Applications, 2 (1971), Wiley: Wiley New York · Zbl 0219.60003 |
| [4] | Frisch, H. L.; Hammersley, J. M., Percolation processes and related topics, J. Soc. Indust. Appl. Math., 11, 894-918 (1963) · Zbl 0129.46002 |
| [5] | Hammersley, J. M., Postulates for subadditive processes, Ann. Probab., 2, 652-680 (1974) · Zbl 0303.60044 |
| [6] | Horowitz, E.; Sahni, S., Fundamentals of Data Structures (1976), Computer Science Press: Computer Science Press Rockville, Md · Zbl 0408.68003 |
| [7] | Kesten, H., Contribution to the discussion of Kingman’s paper, Ann. Probab., 1, 903 (1973) |
| [8] | Kingman, J. F.C, Subadditive ergodic theory, Ann. Probab., 1, 883-909 (1973) · Zbl 0311.60018 |
| [9] | Knuth, D. E., The Art of Computer Programming 3 (1973), Addison-Wesley: Addison-Wesley New York · Zbl 0191.17903 |
| [10] | Lynch, W. C., More combinatorial properties of certain trees, Comput. J., 7, 299-302 (1965) · Zbl 0136.38801 |
| [11] | Mahmoud, H.; Pittel, B., On the most probable shape of a binary search tree grown from a random permutation, SIAM J. Algebraic Discrete Methods, 5, 69-81 (1984) · Zbl 0529.05002 |
| [12] | Moser, L.; Wyman, M., Asymptotic development of the Stirling numbers of the first kind, J. London Math. Soc., 33, 133-146 (1958) · Zbl 0081.28202 |
| [13] | Pittel, B. G., A minimax analogue of the weak law of large numbers, Theory Probab. Appl., 16, 361-367 (1971) · Zbl 0247.60018 |
| [14] | Pittel, B. G., Limiting behavior of a process of runs, Ann. Probab., 9, 119-129 (1981) · Zbl 0453.60017 |
| [15] | Renyi, A.; Szekeres, G., On the height of trees, J. Austral. Math. Soc., 7, 497-507 (1967) · Zbl 0153.25802 |
| [16] | Robson, J. M., The height of binary search trees, Austral. Comput. J., 11, 151-153 (1979) |
| [17] | Ruskey, F., On the average shape of binary trees, SIAM J. Algebraic Discrete Methods, 1, 43-50 (1980) · Zbl 0496.68044 |
| [18] | Stepanov, V. E., On the distribution of the number of vertices in strata of a random tree, Theory Probab. Appl., 14, 65-78 (1969) · Zbl 0196.21001 |
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.
