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

DOI10.1002/RSA.3240050207zbMATH Open0790.05077OpenAlexW2152197249MaRDI QIDQ4286299FDOQ4286299

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

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

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)

Cites Work

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

Cited In (80)

• The variance of the average depth of a pure birth process converges to 7
• 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
• The height of increasing trees
• A functional limit theorem for the profile of random recursive trees
• Depth properties of scaled attachment random recursive trees
• Weighted height of random trees
• Geometry of weighted recursive and affine preferential attachment trees
• Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
• Random plane increasing trees: Asymptotic enumeration of vertices by distance from leaves
• The metric space of limit laws for $q$-hook formulas
• Depth of vertices with high degree in random recursive trees
• The random multisection problem, travelling waves and the distribution of the height of \(m\)-ary search trees
• Width of a scale-free tree
• Limit Theorems for Depths and Distances in Weighted Random B-Ary Recursive Trees
• Weak convergence of the number of vertices at intermediate levels of random recursive trees
• On tail bounds for random recursive trees
• Probabilistic analysis of bucket recursive trees
• Search problems in groups and branching processes
• The Longest Minimum-Weight Path in a Complete Graph
• Condensation phenomena in preferential attachment trees with neighbourhood influence
• On a random search tree: asymptotic enumeration of vertices by distance from leaves
• Justifying the small-world phenomenon via random recursive trees
• A functional limit theorem for the profile of \(b\)-ary trees
• Title not available (Why is that?)
• Limiting probabilities for vertices of a given rank in 1-2 trees
• A random model of publication activity
• Degree distribution of the FKP network model
• On leaf related statistics in recursive tree models
• BUILDING RANDOM TREES FROM BLOCKS
• Twitter event networks and the superstar model
• High degrees in recursive trees
• It's a small world for random surfers
• The \(k\)-cut model in deterministic and random trees
• The small-community phenomenon in networks
• The robot crawler graph process
• A non-increasing tree growth process for recursive trees and applications
• Multiway trees of maximum and minimum probability under the random permutation model
• Strict monotonic trees arising from evolutionary processes: combinatorial and probabilistic study
• Investigating several fundamental properties of random lobster trees and random spider trees
• On martingale tail sums for the path length in random trees
• Diameters in preferential attachment models
• Diameter of the Stochastic Mean-Field Model of Distance
• Branching processes in the analysis of the heights of trees
• Asymptotic results on Hoppe trees and their variations
• Poisson-Dirichlet branching random walks
• A class of random recursive tree algorithms with deletion
• Universal Limit Laws for Depths in Random Trees
• Profile of random exponential recursive trees
• Limit distribution for the maximum degree of a random recursive tree
• Title not available (Why is that?)
• On the asymptotic behaviour of random recursive trees in random environments
• The height of random k‐trees and related branching processes
• On a random graph evolving by degrees
• On joint properties of vertices with a given degree or label in the random recursive tree
• A random graph of moderate density
• Correction terms for the height of weighted recursive trees
• On the height of random m‐ary search 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
• Note on the exponential recursive k-ary trees
• A note on the growth of random trees
• Critical random graphs and the structure of a minimum spanning tree
• Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
• Random maps with sociological flavor
• A Theory of Network Security: Principles of Natural Selection and Combinatorics
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees
• Random recursive hypergraphs
• On bucket increasing trees, clustered increasing trees and increasing diamonds
• Dynamics of information 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
• Broadcasting‐induced colorings of preferential attachment trees
• Depths in random recursive metric spaces
• The permuton limit of random recursive separable permutations
• SMALL-WORLD EFFECT IN GEOGRAPHICAL ATTACHMENT NETWORKS
• The idemetric property: when most distances are (almost) the same
• The Hitting Time for the Height of a Random Recursive Tree

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)