On the Variance of the Height of Random Binary Search Trees
From MaRDI portal
Publication:4862790
DOI10.1137/S0097539792237541zbMath0845.68027MaRDI QIDQ4862790
Publication date: 15 September 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05)
Related Items (13)
Smoothed analysis of binary search trees ⋮ Depth Properties of scaled attachment random recursive trees ⋮ On the concentration of the height of binary search trees ⋮ The height of increasing trees ⋮ Martingales and large deviations for binary search trees ⋮ Limiting theorems for the nodes in binary search trees ⋮ Optimal binary search trees ⋮ On Robson's convergence and boundedness conjectures concerning the height of binary search trees ⋮ Minima in branching random walks ⋮ The variance of the height of binary search trees ⋮ Long Monotone Trails in Random Edge-Labellings of Random Graphs ⋮ The height of a binary search tree: the limiting distribution perspective. ⋮ Constant bounds on the moments of the height of binary search trees
This page was built for publication: On the Variance of the Height of Random Binary Search Trees
