✦ LIBER ✦

On the altitude of specified nodes in random trees

✍ Scribed by Helmut Prodinger

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 130 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080405

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The distribution of nodes of given degre

The distribution of nodes of given degree in random trees

✍ Drmota, Michael; Gittenberger, Bernhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 391 KB 👁 2 views

Let T n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ µ k n and variance ∼ σ 2 k n with positive constants µ

On the profile of random trees

✍ Michael Drmota; Bernhard Gittenberger 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB 👁 2 views

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processe

On the joint distribution of the nodes i

On the joint distribution of the nodes in uniform multidimensional binary trees

✍ Rainer Kemp 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 313 KB 👁 2 views

Multidimensional binary trees represent a symbiosis of trees and tries, and they essentially arise in the construction of search trees for multidimensional keys. The set of nodes in a d-dimensional binary tree can be partitioned into layers according to the nodes appearing in the ith dimension. We d

On the Total Heights of Random Rooted Bi

On the Total Heights of Random Rooted Binary Trees

✍ L. Takacs 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

On the log-product of the subtree-sizes

On the log-product of the subtree-sizes of random trees

✍ A. Meir; J. W. Moon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 2 views

We determine the asymptotic behavior of the expected value and the variance of the log-product of the subtree-sizes of trees T belonging to simply generated families of n

On the shape of the fringe of various ty

On the shape of the fringe of various types of random trees

✍ Michael Drmota; Bernhard Gittenberger; Alois Panholzer; Helmut Prodinger; Mark D 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract We analyze a fringe tree parameter w in a variety of settings, utilizing a variety of methods from the analysis of algorithms and data structures. Given a tree __t__ and one of its leaves __a__, the w(__t, a__) parameter denotes the number of internal nodes in the subtree rooted at __a