The expected additive weight of trees
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.
- Asymptotic Methods in Enumeration
- Distributional properties of a model for the spread or drug abuse
- Enumerations of ordered trees
- scientific article; zbMATH DE number 3862455 (Why is no real title available?)
- scientific article; zbMATH DE number 3909754 (Why is no real title available?)
- scientific article; zbMATH DE number 3917729 (Why is no real title available?)
- scientific article; zbMATH DE number 4027492 (Why is no real title available?)
- scientific article; zbMATH DE number 4041254 (Why is no real title available?)
- scientific article; zbMATH DE number 3723873 (Why is no real title available?)
- scientific article; zbMATH DE number 17678 (Why is no real title available?)
- scientific article; zbMATH DE number 3443655 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- On the Altitude of Nodes in Random Trees
- On the average internal path length of m-ary search trees
- On the average oscillation of a stack
- The average height of binary trees and other simple trees
- The average height of planted plane trees with M leaves
- Additive weights of a special class of nonuniformly distributed backtrack trees
- Additive weights under the balanced probability model
- The scientific works of Rainer Kemp (1949--2004)
- On the lexicographical generation of compressed codes
- scientific article; zbMATH DE number 3862455 (Why is no real title available?)
- scientific article; zbMATH DE number 3917729 (Why is no real title available?)
- scientific article; zbMATH DE number 4027492 (Why is no real title available?)
- scientific article; zbMATH DE number 4045179 (Why is no real title available?)
- On the average number of registers needed to evaluate a special class of backtrack trees
- Uniformly growing backtrack trees
- THE EXFECTED INDEPENDENT DOMINATION NUMBER OF TWO TYPES OF TREES
- On the inner structure of multidimensional simply generated trees
- On the inner structure of multidimensional simply generated trees
- (Un)expected path lengths of asymmetric binary search trees
- Total Weight Choosability of Trees
- On the combinatorics of leftist trees
This page was built for publication: The expected additive weight of trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262116)