Limit laws for local counters in random binary search trees

DOI10.1002/rsa.3240020305zbMath0728.60027OpenAlexW2097457356WikidataQ115150350 ScholiaQ115150350MaRDI QIDQ3352193

Luc P. Devroye

Publication date: 1991

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

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

zbMATH Keywords

central limit theoremsrandom treesrandom binary search treestheory of urn modelsuniform random recursive trees

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Related Items

Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees, On rotations in fringe-balanced binary trees, On the richness of the collection of subtrees in random binary search trees, Finding the seed of uniform attachment trees, The joint distribution of the three types of nodes in uniform binary trees, Average-case analysis of multiple Quickselect: An algorithm for finding order statistics, Investigating several fundamental properties of random lobster trees and random spider trees, \(k\)-protected vertices in binary search trees, SOME PROPERTIES OF BINARY SERIES-PARALLEL GRAPHS, Unnamed Item, Consecutive patterns in permutations, A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees, DEGREE PROFILE OF m-ARY SEARCH TREES: A VEHICLE FOR DATA STRUCTURE COMPRESSION, DEGREE-BASED GINI INDEX FOR GRAPHS, Central Limit Theorems for Additive Tree Parameters with Small Toll Functions, A general limit theorem for recursive algorithms and combinatorial structures, Minimal clade size and external branch length under the neutral coalescent, Maximal clades in random binary search trees, On statistical tests of phylogenetic tree imbalance: The Sackin and other indices revisited, Random sprouts as internet models, and Pólya processes, On the Subtree Size Profile of Binary Search trees, Asymptotic distribution of two-protected nodes in random binary search trees, A functional limit theorem for the profile of \(b\)-ary trees, On degenerate sums of m-dependent variables, On weighted depths in random binary search trees, Necklace Processes Via Pólya Urns, On the shape of the fringe of various types of random trees, On a random search tree: asymptotic enumeration of vertices by distance from leaves, Normal convergence problem? Two moments and a recurrence may be the clues, Mean and variance of balanced Pólya urns

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On growing random binary trees
• Branching processes in the analysis of the heights of trees
• Central limit theorems under weak dependence
• The expected linearity of a simple equivalence algorithm
• Dependent central limit theorems and invariance principles
• Distribution of nodes of a tree by degree
• The central limit theorem for dependent random variables
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• The analysis of a fringe heuristic for binary search trees
• The Expected Distribution of Degrees in Random Binary Search Trees
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• A note on the height of binary search trees
• Two central limit problems for dependent random variables
• More Combinatorial Properties of Certain Trees
• Martingale Central Limit Theorems