The expected additive weight of trees (Q1262116)

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.