The average height of binary trees and other simple trees

Philippe Flajolet, Andrew Odlyzko

Type: Article

Publication Date: 1982-10-01

Citations: 257

DOI: https://doi.org/10.1016/0022-0000(82)90004-6

View Publication

Locations

Journal of Computer and System Sciences - View
HAL (Le Centre pour la Communication Scientifique Directe) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Exploring binary trees and other simple trees	1980	Philippe Flajolet Andrew Odlyzko
+	On the average stack size of regularly distributed binary trees	1979	Rainer Kemp
+	On the heights and widths of random rooted trees	1992	L Takács
+	Shedding new light on random trees	2007	Nicolas Broutin
+	The asymptotic distribution of leaf heights in binary trees	1992	Walter J. Gutjahr Georg Ch. Pflug
+ PDF Chat	Upper Bounds on the Average Height of Random Binary Trees	2024	Louisa Seelbach Benkner
+	Trees with power-like height dependent weight	2021	Bergfinnur Durhuus Meltem Ünel
+	Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees	2016	Shalosh B. Ekhad Doron Zeilberger
+	The Variance of the Number of 2-Protected Nodes in a Trie	2013	Jeffrey Gaither Mark Daniel Ward
+	On the total heights of random rooted trees	1992	Lajos Takács
+	On the total heights of random rooted trees	1992	Lajos Takács
+	Constant bounds on the moments of the height of binary search trees	2002	J. M. Robson
+	The size of the biggest Caterpillar subtree in binary rooted planar trees	2012	Filippo Disanto
+ PDF Chat	SYNTHÈSE N° 1	2019	A. Magnan
+	On the Total Heights of Random Rooted Binary Trees	1994	L Takács
+	An analytic approach to the height of binary search trees	2001	Michael Drmota
+ PDF Chat	Weighted height of random trees	2008	Nicolas Broutin Luc Devroye Erin McLeish
+	The average height of planted plane trees with M leaves	1983	Rainer Kemp
+	Enumeration of rooted trees with a height distribution	1985	Cheryl E. Praeger P. Schultz Nicholas Wormald
+	The Subtree Size Profile of Plane-oriented Recursive Trees	2011	Michael Fuchs

Works That Cite This (190)

Action	Title	Year	Authors
+ PDF Chat	The continuum limit of critical random graphs	2010	Louigi Addario‐Berry Nicolas Broutin Christina Goldschmidt
+	Branching processes in the analysis of the heights of trees	1987	Luc Devroye
+	On Network Structure Function Computations	1993	Edward C. Waymire
+ PDF Chat	Random real trees	2009	Jean‐François Le Gall
+	An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms	2002	Hua‐Huai Chern Hsien‐Kuei Hwang Tsung‐Hsi Tsai
+	States Spaces of the Snake and Its Tour—Convergence of the Discrete Snake	2003	Jean‐François Marckert Abdelkader Mokkadem
+	ON THE WIENER INDEX OF TREES FROM CERTAIN FAMILIES	1994	R. C. Entringer A. Meir J. W. Moon László Á. Székely
+	Uniform bounds for exponential moment of maximum of a Dyck paths	2009	Oleksiy Khorunzhiy Jean‐François Marckert
+ PDF Chat	A Note on the Probability of Cutting a Galton-Watson Tree	2011	Luc Devroye
+	Analysis of three graph parameters for random trees	2009	Cyril Banderier Markus Kuba Alois Panholzer

Works Cited by This (9)

Action	Title	Year	Authors
+	On the average stack size of regularly distributed binary trees	1979	Rainer Kemp
+	The number of registers required for evaluating arithmetic expressions	1979	Philippe Flajolet Jean -Claude Raoult Jean Vuillemin
+ PDF Chat	On the Altitude of Nodes in Random Trees	1978	A. Meir J. W. Moon
+	The average number of registers needed to evaluate a binary tree optimally	1979	Rainer Kemp
+	The Enumeration of Trees by Height and Diameter	1960	John Riordan
+	Asymptotic Methods in Enumeration	1974	Edward A. Bender
+	Periodic oscillations of coefficients of power series that satisfy functional equations	1982	Andrew Odlyzko
+	Exploring binary trees and other simple trees	1980	Philippe Flajolet Andrew Odlyzko
+ PDF Chat	On the height of trees	1967	A. Rényi G Szekeres