The expected additive weight of trees
type: Item
instance of: scholarly article
title: The expected additive weight of trees
zbMATH Open document ID: 0685.68023
DOI: 10.1007/BF00289158
author: K. Appert
published in: Acta Informatica
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4123277
zbMATH Keywords: trees
zbMATH Keywords: average weight
zbMATH Keywords: data structures
reviewed by: Marius Zimand
MaRDI profile type: Publication
cites work: Q5558293
cites work: Asymptotic Methods in Enumeration
cites work: Q4769056
cites work: Enumerations of ordered trees
cites work: Q3912031
cites work: The average height of binary trees and other simple trees
cites work: Q3686051
cites work: On the average oscillation of a stack
cites work: The average height of planted plane trees with M leaves
cites work: Q3330524
cites work: Q3779735
cites work: Q3692885
cites work: Distributional properties of a model for the spread or drug abuse
cites work: Q3768921
cites work: Q3975006
cites work: Q5585020
cites work: On the average internal path length of m-ary search trees
cites work: On the Altitude of Nodes in Random Trees
full work available at URL: https://doi.org/10.1007/bf00289158
OpenAlex ID: W2059942290
description: scientific article; zbMATH DE number 4123277