Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
From MaRDI portal
Publication:4785635
DOI10.1137/S0097539701383923zbMath1029.68076MaRDI QIDQ4785635
Publication date: 5 January 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
convergenceStein's methodprobabilistic analysisdata structuresrandom treesbinary search treelimit lawtoll functions
Analysis of algorithms and problem complexity (68Q25) Central limit and other weak theorems (60F05) Data structures (68P05)
Related Items (11)
Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates ⋮ A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees ⋮ Central Limit Theorems for Additive Tree Parameters with Small Toll Functions ⋮ A general limit theorem for recursive algorithms and combinatorial structures ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ Cost functionals for large (uniform and simply generated) random trees ⋮ Maximal clades in random binary search trees ⋮ On degenerate sums of m-dependent variables ⋮ Metric dimension of critical Galton-Watson trees and linear preferential attachment trees ⋮ A central limit theorem for additive functionals of increasing trees
This page was built for publication: Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
