Premium
Level of nodes in increasing trees revisited
Author(s) -
Panholzer Alois,
Prodinger Helmut
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20161
Subject(s) - mathematics , weight balanced tree , combinatorics , simple (philosophy) , polynomial , random binary tree , generating function , discrete mathematics , tree (set theory) , binary tree , function (biology) , heap (data structure) , time complexity , binary search tree , algorithm , mathematical analysis , philosophy , epistemology , evolutionary biology , biology
Simply generated families of trees are described by the equation T ( z ) = ϕ( T ( z )) for their generating function. If a tree has n nodes, we say that it is increasing if each node has a label ∈ { 1,…, n }, no label occurs twice, and whenever we proceed from the root to a leaf, the labels are increasing. This leads to the concept of simple families of increasing trees. Three such families are especially important: recursive trees, heap ordered trees, and binary increasing trees. They belong to the subclass of very simple families of increasing trees, which can be characterized in 3 different ways. This paper contains results about these families as well as about polynomial families (the function ϕ( u ) is just a polynomial). The random variable of interest is the level of the node (labelled) j , in random trees of size n ≥ j . For very simple families, this is independent of n , and the limiting distribution is Gaussian. For polynomial families, we can prove this as well for j , n → ∞ such that n − j is fixed. Additional results are also given. These results follow from the study of certain trivariate generating functions and Hwang's quasi power theorem. They unify and extend earlier results by Devroye, Mahmoud, and others. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007