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

DOI10.1002/RSA.3240050207MaRDI QIDQ4286299zbMATH OpenOpenAlexFDO

Authors Boris 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)

Recommendations

• On the height of random m‐ary search trees
• The height of scaled attachment random recursive trees
• Branching processes in the analysis of the heights of trees
• scientific article; zbMATH DE number 17686
• An analytic approach to the height of binary search trees

Cites work

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

Cited in

(83)

• The Hitting Time for the Height of a Random Recursive Tree
• Critical random graphs and the structure of a minimum spanning tree
• Diameter of the stochastic mean-field model of distance
• The variance of the average depth of a pure birth process converges to 7
• The longest minimum-weight path in a complete graph
• Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
• A bijection of plane increasing trees with relaxed binary trees of right height at most one
• Long and short paths in uniform random recursive dags
• A functional limit theorem for the profile of random recursive trees
• The height of increasing trees
• The height of increasing trees
• Depth properties of scaled attachment random recursive trees
• Weighted height of random trees
• Random maps with sociological flavor
• Geometry of weighted recursive and affine preferential attachment trees
• Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves
• A Theory of Network Security: Principles of Natural Selection and Combinatorics
• The random multisection problem, travelling waves and the distribution of the height of m-ary search trees
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• Depth of vertices with high degree in random recursive trees
• The height of scaled attachment random recursive trees
• Width of a scale-free tree
• Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees
• Weak convergence of the number of vertices at intermediate levels of random recursive trees
• Random recursive hypergraphs
• On tail bounds for random recursive trees
• Probabilistic analysis of bucket recursive trees
• On bucket increasing trees, clustered increasing trees and increasing diamonds
• Condensation phenomena in preferential attachment trees with neighbourhood influence
• scientific article; zbMATH DE number 17686 (Why is no real title available?)
• Justifying the small-world phenomenon via random recursive trees
• A functional limit theorem for the profile of \(b\)-ary trees
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• A random model of publication activity
• Limiting probabilities for vertices of a given rank in 1-2 trees
• Twitter event networks and the superstar model
• Dynamics of information networks
• Degree distribution of the FKP network model
• On leaf related statistics in recursive tree models
• High degrees in recursive trees
• It's a small world for random surfers
• Random recursive trees and preferential attachment trees are random split trees
• The \(k\)-cut model in deterministic and random trees
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• The small-community phenomenon in networks
• Community modulated recursive trees and population dependent branching processes
• Archaeology of random recursive dags and Cooper-Frieze random networks
• On a sufficient condition for explosion in CMJ branching processes and applications to recursive trees
• The robot crawler graph process
• Broadcasting‐induced colorings of preferential attachment trees
• Multiway trees of maximum and minimum probability under the random permutation model
• A non-increasing tree growth process for recursive trees and applications
• The metric space of limit laws for \(q\)-hook formulas
• Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study
• Investigating several fundamental properties of random lobster trees and random spider trees
• Depths in random recursive metric spaces
• Diameters in preferential attachment models
• On martingale tail sums for the path length in random trees
• Branching processes in the analysis of the heights of trees
• Asymptotic results on Hoppe trees and their variations
• The permuton limit of random recursive separable permutations
• Poisson-Dirichlet branching random walks
• SMALL-WORLD EFFECT IN GEOGRAPHICAL ATTACHMENT NETWORKS
• Search problems in groups and branching processes.
• A class of random recursive tree algorithms with deletion
• The idemetric property: when most distances are (almost) the same
• Limit distribution for the maximum degree of a random recursive tree
• Universal Limit Laws for Depths in Random Trees
• Profile of random exponential recursive trees
• scientific article; zbMATH DE number 3965074 (Why is no real title available?)
• Building random trees from blocks
• On the asymptotic behaviour of random recursive trees in random environments
• On a random graph evolving by degrees
• On joint properties of vertices with a given degree or label in the random recursive tree
• The height of random k‐trees and related branching processes
• On the height of random m‐ary search trees
• A random graph of moderate density
• Correction terms for the height of weighted recursive trees
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees
• On finding a minimum spanning tree in a network with random weights
• A note on the growth of random trees
• Note on the exponential recursive k-ary trees
• Limit theorems for depths and distances in weighted random \(b\)-ary recursive trees

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

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