The asymptotic distribution of leaf heights in binary trees

DOI10.1007/BF02349961MaRDI QIDQ1199121zbMATH OpenWikidataFDO

Authors Walter J. Gutjahr, Georg Ch. Pflug

Publication date 16 January 1993

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02349961

zbMATH Keywords

asymptotic distributionheightrandom tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Asymptotic distribution theory in statistics (62E20)

Review text

The height \(h_ t(i)\) of the \(i\)-th leaf (counted from left to right) in a tree \(t\) is the distance from the root to this leaf. This paper derives the asymptotic distribution of the normalized height \(h_ t(i)/\sqrt n\) as \(i/n\to x\), in a random tree with \(n\) internal nodes. This distribution is shown to be a Maxwell distribution, the distribution of the square root of a sum of squares of independent normally distributed random variables.

Recommendations

• scientific article; zbMATH DE number 1222140
• scientific article; zbMATH DE number 515653
• The height distribution of leaves in rooted trees
• On the total heights of random rooted binary trees
• The limiting common distribution of two leaf heights in a random binary tree

Cites work

• A note on the stack size of regularly distributed binary trees
• scientific article; zbMATH DE number 3847416 (Why is no real title available?)
• scientific article; zbMATH DE number 4023312 (Why is no real title available?)
• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• On Level Numbers of t-Ary Trees
• On the average oscillation of a stack
• On the Average Shape of Binary Trees
• The asymptotic contour process of a binary tree is a Brownian excursion
• The average height of binary trees and other simple trees
• The limiting common distribution of two leaf heights in a random binary tree
• The Variance of Level Numbers in Certain Families of Trees

Cited in

(21)

• The asymptotic contour process of a binary tree is a Brownian excursion
• On the total heights of random rooted binary trees
• Moments of level numbers of leaves in binary trees
• Analysis of generating functions and probabilities on trees
• The distribution of height and diameter in random non-plane binary trees
• On the asymptotic joint distribution of height and width in random trees
• scientific article; zbMATH DE number 3902674 (Why is no real title available?)
• The average height of thed-th highest leaf of a planted plane tree
• The limiting common distribution of two leaf heights in a random binary tree
• The shape of random pattern-avoiding permutations
• The Variance of Level Numbers in Certain Families of Trees
• scientific article; zbMATH DE number 1222140 (Why is no real title available?)
• scientific article; zbMATH DE number 515653 (Why is no real title available?)
• The Distribution of Heights of Binary Trees and Other Simple Trees
• The height distribution of leaves in rooted trees
• scientific article; zbMATH DE number 2038884 (Why is no real title available?)
• scientific article; zbMATH DE number 1552321 (Why is no real title available?)
• Asymptotics of heights in random trees constructed by aggregation
• scientific article; zbMATH DE number 2197876 (Why is no real title available?)
• Power-law behavior in geometric characteristics of full binary trees
• A walk in my lattice path garden

This page was built for publication: The asymptotic distribution of leaf heights in binary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199121)