The analysis of an additive weight of random trees. (English) Zbl 0641.68095

A general additive weight of random trees is considered. It depends on the structure of the subtrees and 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. Choosing particular weight functions, the corresponding weight is a well known parameter appearing in the analysis of sorting and searching algorithms. For a simply generated family of rooted planar trees \({\mathcal F}\), a general approach to the computation of the average weight of a tree \(T\in {\mathcal F}\) with n nodes and m leaves for arbitrary weight functions is derived. This general result implies exact and asymptotic expressions for many types of average weights of a tree \(T\in {\mathcal F}\) with n nodes if the weight functions are arbitrary polynomials in the number of nodes and leaves with coefficients depending on the node degrees.


68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity