The height of random binary unlabelled trees

MaRDI QIDQ2959857zbMATH OpenFDO

Authors Nicolas Broutin, Philippe Flajolet

Publication date 10 February 2017

Full work available at URL https://arxiv.org/abs/0807.2365, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAI0106

zbMATH Keywords

average-case analysisgenerating functionsheightlimit distributionlocal limit theorem

Mathematics Subject Classification ID

Combinatorial probability (60C05) Large deviations (60F10) Data structures (68P05)

Abstract: This extended abstract is dedicated to the analysis of the height of non-plane unlabelled rooted binary trees. The height of such a tree chosen uniformly among those of size $n$ is proved to have a limiting theta distribution, both in a central and local sense. Moderate as well as large deviations estimates are also derived. The proofs rely on the analysis (in the complex plane) of generating functions associated with trees of bounded height.

Recommendations

• On the total heights of random rooted binary trees
• The height of random k‐trees and related branching processes
• On the Variance of the Height of Random Binary Search Trees
• Profile and height of random binary search trees
• On the total heights of random rooted trees
• The height of a random binary search tree
• The Distribution of Heights of Binary Trees and Other Simple Trees
• The distribution of height and diameter in random non-plane binary trees

Cited in

(16)

• On the total heights of random rooted binary trees
• A strong law for the height of random binary pyramids
• The number of rooted trees of given depth
• The distribution of height and diameter in random non-plane binary trees
• Isomorphism and symmetries in random phylogenetic trees
• The Distribution of Heights of Binary Trees and Other Simple Trees
• A Greedy Algorithm Estimating the Height of Random Trees
• The degree profile of random Pólya trees
• scientific article; zbMATH DE number 1552322 (Why is no real title available?)
• On the Variance of the Height of Random Binary Search Trees
• The CRT is the scaling limit of unordered binary trees
• The height of random k‐trees and related branching processes
• scientific article; zbMATH DE number 2197876 (Why is no real title available?)
• Random trees have height \(O(\sqrt{n})\)
• Tree height and the asymptotic mean of the Colijn-Plazzotta rank of unlabeled binary rooted trees
• The shape of unlabeled rooted random trees

This page was built for publication: The height of random binary unlabelled trees

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