Note on the heights of random recursive trees and random m‐ary search trees

DOI10.1002/rsa.3240050207zbMath0790.05077OpenAlexW2152197249MaRDI QIDQ4286299

Boris G. Pittel

Publication date: 22 June 1994

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240050207

zbMATH Keywords

heightrandom recursive treeuniform recursive treeCrump-Mode branching processDevroye's limit lawordered recursive treerandom \(m\)-ary search tree

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Related Items

On bucket increasing trees, clustered increasing trees and increasing diamonds, The small-community phenomenon in networks, Random recursive hypergraphs, On Tail Bounds for Random Recursive Trees, Degree distribution of the FKP network model, The metric space of limit laws for $q$-hook formulas, On leaf related statistics in recursive tree models, SMALL-WORLD EFFECT IN GEOGRAPHICAL ATTACHMENT NETWORKS, Depth Properties of scaled attachment random recursive trees, High degrees in recursive trees, Condensation phenomena in preferential attachment trees with neighbourhood influence, It's a small world for random surfers, The robot crawler graph process, Giant descendant trees, matchings, and independent sets in age-biased attachment graphs, A note on the growth of random trees, Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study, A class of random recursive tree algorithms with deletion, Profile of random exponential recursive trees, Investigating several fundamental properties of random lobster trees and random spider trees, Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves, Community modulated recursive trees and population dependent branching processes, Broadcasting‐induced colorings of preferential attachment trees, Long and short paths in uniform random recursive dags, Poisson-Dirichlet branching random walks, Weak convergence of the number of vertices at intermediate levels of random recursive trees, Diameter of the Stochastic Mean-Field Model of Distance, Justifying the small-world phenomenon via random recursive trees, A functional limit theorem for the profile of random recursive trees, A bijection of plane increasing trees with relaxed binary trees of right height at most one, The \(k\)-cut model in deterministic and random trees, Weighted height of random trees, The height of increasing trees, The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees, Asymptotic results on Hoppe trees and their variations, Probabilistic analysis of bucket recursive trees, The Longest Minimum-Weight Path in a Complete Graph, The idemetric property: when most distances are (almost) the same, BUILDING RANDOM TREES FROM BLOCKS, Depth of vertices with high degree in random recursive trees, Diameters in preferential attachment models, On martingale tail sums for the path length in random trees, Multiway Trees of Maximum and Minimum Probability under the Random Permutation Model, Critical random graphs and the structure of a minimum spanning tree, A functional limit theorem for the profile of \(b\)-ary trees, On finding a minimum spanning tree in a network with random weights, Width of a scale-free tree, Geometry of weighted recursive and affine preferential attachment trees, A random model of publication activity, Twitter event networks and the superstar model, Random Recursive Trees and Preferential Attachment Trees are Random Split Trees, On a random search tree: asymptotic enumeration of vertices by distance from leaves, Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees, The variance of the average depth of a pure birth process converges to 7, A non-increasing tree growth process for recursive trees and applications, Limiting probabilities for vertices of a given rank in 1-2 trees, A random graph of moderate density, Universal Limit Laws for Depths in Random Trees, Correction terms for the height of weighted recursive trees, On the asymptotic behaviour of random recursive trees in random environments, On a random graph evolving by degrees, Search problems in groups and branching processes, A Theory of Network Security: Principles of Natural Selection and Combinatorics, The height of random k‐trees and related branching processes, On joint properties of vertices with a given degree or label in the random recursive tree, Limit distribution for the maximum degree of a random recursive tree

Cites Work

• Unnamed Item
• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• On the distribution of leaves in rooted subtrees of recursive trees
• Distances in random plane-oriented recursive trees
• Postulates for subadditive processes
• The first birth problem for an age-dependent branching process
• Linear expected time of a simple union-find algorithm
• The expected linearity of a simple equivalence algorithm
• A general age-dependent branching process. I
• Distribution of nodes of a tree by degree
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• On the height of random m‐ary search trees
• A note on the height of binary search trees
• The first- and last-birth problems for a multitype age-dependent branching process
• A Probability Model of a Pyramid Scheme
• Chernoff's theorem in the branching random walk
• On the structure of random plane‐oriented recursive trees and their branches