Applications of the theory of records in the study of random trees

DOI10.1007/BF02915448zbMath0656.68065OpenAlexW2060242260MaRDI QIDQ1110339

Luc P. Devroye

Publication date: 1988

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02915448

zbMATH Keywords

random variablesrandom treesbinary search treestheory of records

Mathematics Subject Classification ID

Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Data structures (68P05)

Related Items

Distribution of distances in random binary search trees., Uniform recursive trees: branching structure and simple random downward walk, A provably fast linear-expected-time maxima-finding algorithm, Permutations with equal orders, One-sided variations on binary search trees, Depths in hooking networks, On random cartesian trees, On the Asymptotic Behavior of a Dynamic Version of the Neyman Contagious Point Process, The left-right-imbalance of binary search trees, Combinatorics of geometrically distributed random variables: Left-to-right maxima, Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon, Long and short paths in uniform random recursive dags, A note on the distance in random recursive trees, Random walks with preferential relocations and fading memory: a study through random recursive trees, Note on the outdegree of a node in random recursive trees, Random binary trees: from the average case analysis to the asymptotics of distributions, Probabilistic analysis of bucket recursive trees, Distances in random plane-oriented recursive trees, Asymptotic normality for the number of records from general distributions, Depth of vertices with high degree in random recursive trees, Mixed Poisson approximation of node depth distributions in random binary search trees, Branching structure of uniform recursive trees, The Hitting Time for the Height of a Random Recursive Tree, On weighted depths in random binary search trees, Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey, Limiting Distributions for Path Lengths in Recursive Trees, On the asymptotic behaviour of random recursive trees in random environments, On joint properties of vertices with a given degree or label in the random recursive tree, A new approach to Pólya urn schemes and its infinite color generalization, Broadcasting on random recursive trees, Limit distribution for the maximum degree of a random recursive tree

Cites Work

• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• Linear expected time of a simple union-find algorithm
• The expected linearity of a simple equivalence algorithm
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• On Random Binary Trees
• A note on the height of binary search trees
• Breaking Records and Breaking Boards
• More Combinatorial Properties of Certain Trees
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item