Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees

DOI10.1137/S0097539701383923zbMath1029.68076MaRDI QIDQ4785635

Luc P. Devroye

Publication date: 5 January 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

convergenceStein's methodprobabilistic analysisdata structuresrandom treesbinary search treelimit lawtoll functions

Mathematics Subject Classification ID

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