DMTCS Proceedings, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

Font Size:  Small  Medium  Large

Label-based parameters in increasing trees

Markus Kuba, Alois Panholzer

Abstract


Grown simple families of increasing trees are a subclass of increasing trees, which can be constructed by an insertion process. Three such tree families contained in the grown simple families of increasing trees are of particular interest: recursive trees, plane-oriented recursive trees and binary increasing trees. Here we present a general approach for the analysis of a number of label-based parameters in a random grown simple increasing tree of size n as, e.g., the degree of the node labeled j, the subtree-size of the node labeled j, etc. Further we apply the approach to the random variable Xn,j,a, which counts the number of size-a branches attached to the node labeled j (= subtrees of size a rooted at the children of the node labeled j) in a random grown simple increasing tree of size n. We can give closed formulæ for the probability distribution and the factorial moments. Furthermore limiting distribution results for Xn,j,a are given dependent on the growth behavior of j=j(n) compared to n.

Full Text: PDF

Valid XHTML 1.0 Transitional