The expected additive weight of trees. (English) Zbl 0685.68023

The paper investigates a general additive weight of rooted planar trees which depends on the structure of the subtrees, on weight functions defined on the number of internal and external nodes and on the degrees of the nodes appearing in the tree and its subtrees. In fact the author studies only the particular but important case of simply generated trees, i.e. families \({\mathcal F}\) of trees such that the numbers t(n) of all trees of \({\mathcal F}\) with n nodes leads to a generating function that satisfies a certain simple functional equation. For such classes of trees a general method for computing the average weight is developed, provided that all the trees in the class are equally likely. This approach is applied to computing important average weights which play a central role in the analysis of data structures, like the internal and external free path lengths, the internal and external degree path lengths and many other similar parameters.
Reviewer: M.Zimand


68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Abramowitz, M., Stegun, I.A.: Handbook, of Mathematical Functions. New York: Dover Publications 1970 · Zbl 0171.38503
[2] Bender, E.A.: Asymptotic Methods in Enumeration. SIAM Rev. 16, 485-515 (1974) · Zbl 0294.05002
[3] Comtet, L.: Advanced Combinatorics. Dordrecht-Holland/Boston-USA: D. Reidel 1974 · Zbl 0283.05001
[4] Dershowitz, N., Zaks, S.: Enumerations of Ordered Trees. Disc. Math. 31, 9-28 (1980) · Zbl 0443.05049
[5] Dershowitz, N., Zaks, S.: Applied Tree Enumeration. Lect. Notes Comput. Sci. 112 (6th CAAP), 180-193 (1981) · Zbl 0462.68038
[6] Flajolet, P., Odlyzko, A.: The Average Height of Binary Trees and Other Simple Trees. J. Comput. Sci. 25, 171-213 (1982) · Zbl 0499.68027
[7] Flajolet, P., Ottman, T., Wood, D.: Search Trees and Bubble Memories. R.A.I.R.O. Inf. Thèor./ Theor. Inf. 19, 137-164 (1985) · Zbl 0569.68051
[8] Kemp, R.: On The Average Oscillation of a Stack. Combinatorica 2, 157-176 (1982) · Zbl 0506.05025
[9] Kemp, R.: The Average Height of Planted Plane Trees with M. Leaves. J. Comb. Theory, Ser. B34, 191-208 (1983) · Zbl 0516.05020
[10] Kemp, R.: On a General Weight of Trees. Lect. Notes Comput. Sci. 166 (STACS 84), 109-120 (1984) · Zbl 0542.68050
[11] Kemp, R.: Fundamentals of The Average Case Analysis of Particular Algorithms. Wiley-Teubner Series in Computer Science. Stuttgart: Teubner, Chichester: Wiley 1984 · Zbl 0638.68026
[12] Kemp, R.: Free Cost Measures of Trees. Lect. Notes Comput. Sci. 199 (FCT 85), 175-190 (1985) · Zbl 0574.68058
[13] Kemp, R.: The Analysis of an Additive Weight of Random Trees. Tech. Rep. 2/86, Universität Frankfurt, Fachbereich Informatik (1986) · Zbl 0616.60086
[14] Kemp, R.: On Systems of Additive Weights of Trees. Tech. Rep. 6/87, Universität Frankfurt, Fachbereich Informatik (1987) · Zbl 0632.05021
[15] Kemp, R.: Further Results on Leftist Trees. Tech. Rep. 7/87, Universität Frankfurt, Fachbereich Informatik (1987) · Zbl 0742.05030
[16] Kemp, R.: Additive Weights of Non-Regularly Distributed Trees. Ann. Discrete Math. 33, 129-155 (1987) · Zbl 0632.05021
[17] Knuth, D.E.: The Art of Computer Programming, Vol. 1, (2nd. ed.). Reading, Mass.: Addison Wesley 1973 · Zbl 0191.17903
[18] Knuth, D.E.: The Art of Computer Programming, Vol. 3. Reading, Mass.: Addison Wesley 1973 · Zbl 0191.17903
[19] Mahmoud, H.M.: On The Average Internal Path Length of M-ary Search Trees. Acta Inf. 23, 111-117 (1986) · Zbl 0567.68038
[20] Meir, M., Moon, J.W.: On The Altitude of Nodes in Random Trees. Can. Math. 30, 997-1015 (1973) · Zbl 0394.05015
[21] Roth, P.: Scharfe obere Schranken für freie Weglängen in Wurzelbäumen. Diplomarbeit, Universität Frankfurt, Fachbereich Informatik (1987)
[22] Trier, U.: Additive Gewichte bei s-nären Leftist-Bäumen. Diplomarbeit, Universität Frankfurt, Fachbereich Informatik (1987)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.