The average height of binary trees and other simple trees

DOI10.1016/0022-0000(82)90004-6zbMath0499.68027OpenAlexW2168559467MaRDI QIDQ1171885

Philippe Flajolet, Andrew M. Odlyzko

Publication date: 1982

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/inria-00076505/file/RR-0056.pdf

zbMATH Keywords

contour integration analytic behaviour of a generating function expected stack height limiting distribution of height

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Algorithms in computer science (68W99)

Related Items

XML compression via directed acyclic graphs, Uniform generation of forests of restricted height, On the peel number and the leaf-height of Galton–Watson trees, Brownian motion and algorithm complexity, The shape of random tanglegrams, Finding the two-core of a tree, The distribution of height and diameter in random non-plane binary trees, The height of multiple edge plane trees, Analytic models and ambiguity of context-free languages, Average case analysis for tree labelling schemes, Monotonically labelled Motzkin trees, Level number sequences for trees, Multiprocessor simulation strategies with optimal speed-up, On the number of induced subgraphs of trees, Random walks, Gaussian processes and list structures, Simulating theta random variates, Effective resistance of random trees, Current trends in asymptotics: Some problems and some solutions, On random cartesian trees, The Distribution of Heights of Binary Trees and Other Simple Trees, Components of Random Forests, The Sackin index of simplex networks, Analytic methods in asymptotic enumeration, Fringe analysis of plane trees related to cutting and pruning, The shape of random pattern-avoiding permutations, The effects of semantic simplifications on random \textit{BST}-like expression-trees, DEGREE-BASED GINI INDEX FOR GRAPHS, Simplifications of Uniform Expressions Specified by Systems, The continuum limit of critical random graphs, Zip-zip trees: making zip trees more balanced, biased, compact, or persistent, A distance metric on binary trees using lattice-theoretic measures, Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees, On the Joint Path Length Distribution in Random Binary Trees, Heavy subtrees of Galton-Watson trees with an application to Apollonian networks, Extremal statistics on non-crossing configurations, A stochastically quasi-optimal search algorithm for the maximum of the simple random walk, A complexity calculus for recursive tree algorithms, Uniform random generation of expressions respecting algebraic identities, Random real trees, On the Most Probable Shape of a Search Tree Grown from a Random Permutation, Unnamed Item, The Horton-Strahler number of conditioned Galton-Watson trees, The asymptotic contour process of a binary tree is a Brownian excursion, The asymptotic distribution of leaf heights in binary trees, Unnamed Item, A distributional study of the path edge-covering numbers for random trees, On the combinatorics of leftist trees, Reinforced weak convergence of stochastic processes, A note on subtrees rooted along the primary path of a binary tree, Itô's excursion theory and random trees, The shape of unlabeled rooted random trees, Analysis of three graph parameters for random trees, Critical random graphs and the structure of a minimum spanning tree, On the recursion depth of special tree traversal algorithms, Gaussian limiting distributions for the number of components in combinatorial structures, Unnamed Item, Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks, The Diagonal Poisson Transform and its application to the analysis of a hashing scheme, The shape of stretched planar trees, On the Average Size of Glushkov’s Automata, Random graphs from a block-stable class, The expected additive weight of trees, The cycle lemma and some applications, An analysis of budgeted parallel search on conditional Galton-Watson trees, Ladder variables, internal structure of Galton–Watson trees and finite branching random walks, On Functional Graphs of Quadratic Polynomials, Isomorphism and Symmetries in Random Phylogenetic Trees, The properties of random trees, On exact simulation algorithms for some distributions related to Jacobi theta functions, Universal Limit Laws for Depths in Random Trees, On the average oscillation of a stack, Trees with power-like height dependent weight, Listing and counting subtrees of equal size of a binary tree, The average height of the second highest leaf of a planted plane tree, Counting phylogenetic networks, Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations, Two results about the Sackin and Colless indices for phylogenetic trees and their shapes, Matrice de ramification des arbres binaires. (Ramification matrices of binary trees), Bandwidths and profiles of trees

Cites Work