๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the Total Heights of Random Rooted Binary Trees

โœ Scribed by L. Takacs

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
306 KB
Volume
61
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 heights of its vertices. The height of a vertex in a rooted tree is the distance from the vertex to the root of the tree, that is, the number of edges in the path from the vertex to the root. This paper is concerned with the distribution and the moments of (\sigma_{n}) and their asymptotic behavior as (n \rightarrow \infty). 1994 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

On the Automorphism Group of the One-Roo
On the Automorphism Group of the One-Rooted Binary Tree
โœ A.M. Brunner; Said Sidki ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 339 KB

Let A be the automorphism group of the one-rooted regular binary tree T and 2 G the subgroup of A consisting of those automorphisms admitting a ''finite ลฝ . description'' in their action on T . Let N G be the normaliser of G in A, let 2 A ลฝ . ลฝ . Aut G be the group of automorphisms of G, and let End

On the distribution of binary search tre
On the distribution of binary search trees under the random permutation model
โœ James Allen Fill ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 865 KB

We study the distribution Q on the set B, of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B,, when successive requests ar

On the profile of random trees
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

The Characterization of Topology: A Comp
The Characterization of Topology: A Comparison of Four topological Indices for Rooted Binary Trees
โœ G.M. Berntson ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 388 KB

The quantification of the topological features of binary trees has been applied in several branches of biology, from botany to neurobiology to animal behaviour. The methods available for quantifying tree topology differ, both in how they are applied and how they relate to one another. In this paper,

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