The average height of binary trees and other simple trees. (English) Zbl 0499.68027


68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C30 Enumeration in graph theory
68W99 Algorithms in computer science
Full Text: DOI Link


[1] Bender, E. A., Asymptotic methods in enumeration, SIAM Rev., 16, 485-515 (1974) · Zbl 0294.05002
[2] de Bruijn, N., Asymptotic Methods in Analysis (1961), North-Holland: North-Holland Amsterdam · Zbl 0109.03502
[3] de Bruijn, N.; Knuth, D.; Rice, S., The average height of planted plane trees, (Read, R. R.C., Graph Theory and Computing (1972), Academic Press: Academic Press New York), 15-22 · Zbl 0247.05106
[5] Flajolet, P.; Odlyzko, A. M., Exploring binary trees and other simple trees, (Proceedings of 21st IEEE Found. Computer Sci. Symposium. Proceedings of 21st IEEE Found. Computer Sci. Symposium, New York (1980)), 207-216
[6] Flajolet, P.; Raoult, J. C.; Vuillemin, J., The number of registers required to evaluate arithmetic expressions, Theoret. Comput. Sci., 9, 99-125 (1979) · Zbl 0407.68057
[7] Flajolet, P.; Steyaert, J. M., On the analysis of tree matching algorithms, (Proceedings, 7th ICALP Conf.. Proceedings, 7th ICALP Conf., Amsterdam (1980)) · Zbl 0444.68054
[8] Kemp, R., The average number of registers needed to evaluate a binary tree optimally, Acta Inform., 11, 363-372 (1979) · Zbl 0395.68059
[9] Kemp, R., The Average Height of a Derivation Tree Generated by a Linear Grammar in a Special Chomsky Normal Form, Saarbrucken University Report A 78/01 (1978)
[10] Kemp, R., On the stack size of regularly distributed binary trees, (Proceedings, 6th ICALP Conf.. Proceedings, 6th ICALP Conf., Udine (1979)) · Zbl 0415.05019
[11] Knuth, D. E., The Art of Computer Programming: Fundamental Algorithms (1968), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0191.17903
[12] Knuth, D. E., The Art of Computer Programming: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0302.68010
[13] Meir, A.; Moon, J. W., On the altitude of nodes in random trees, Canad. J. Math, 30, 997-1015 (1978) · Zbl 0394.05015
[14] Meir, A.; Moon, J. W.; Pounder, J. R., On the order of random channel networks, SIAM J. Algebraic Discrete Math., 1, 25-33 (1980) · Zbl 0496.94020
[15] Odlyzko, A., Periodic oscillations of coefficients of power series that satisfy functional equations, Adv. in Math., 44, 180-205 (1982) · Zbl 0484.30002
[16] Polya, G., Kombinatorische Anzahlbestimmungen für Graphen, Gruppen, und Chemische Verbindungen, Acta Math., 68, 145-254 (1937) · JFM 63.0547.04
[17] Renyi, A.; Szekeres, G., On the height of trees, Austral. J. Math., 7, 497-507 (1967) · Zbl 0153.25802
[18] Riordan, J., The enumeration of trees by height and diameter, IBM J. Res. Dev., 4, 473-478 (1960) · Zbl 0097.25201
[19] Robson, J. M., The height of binary search trees, Austral. Comput. J., 11, 151-153 (1979)
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.