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 (65)

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

This page was built for publication: Note on the heights of random recursive trees and random m‐ary search trees