On the Variance of the Height of Random Binary Search Trees

DOI10.1137/S0097539792237541MaRDI QIDQ4862790zbMATH OpenFDO

Authors Luc Devroye, Bruce Reed

Publication date 15 September 1996

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

zbMATH Keywords

random binary search tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10) Combinatorial probability (60C05)

Recommendations

• The variance of the height of binary search trees
• Profile and height of random binary search trees
• On the height of random m‐ary search trees
• The height of a random binary search tree
• On the total heights of random rooted binary trees
• Numerical studies of the expected height in randomly built binary search trees
• The variance of the height of digital search trees
• The height of random binary unlabelled trees
• Constant bounds on the moments of the height of binary search trees

Cited in

(28)

• The height of increasing trees
• Asymptotic variance of random symmetric digital search trees
• Depth properties of scaled attachment random recursive trees
• The variance of the height of digital search trees
• The variance of the height of binary search trees
• A Greedy Algorithm Estimating the Height of Random Trees
• On Robson's convergence and boundedness conjectures concerning the height of binary search trees
• Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
• Uniform distribution modulo one and binary search trees
• Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees
• Constant bounds on the moments of the height of binary search trees
• How tall is a tree?
• An analytic approach to the height of binary search trees
• Smoothed analysis of binary search trees
• Almost sure asymptotics for the random binary search tree
• Optimal binary search trees
• The height of a binary search tree: the limiting distribution perspective.
• Limiting theorems for the nodes in binary search trees
• Minima in branching random walks
• Martingales and large deviations for binary search trees
• scientific article; zbMATH DE number 1552321 (Why is no real title available?)
• Branching processes in the analysis of the heights of trees
• The height of a random binary search tree
• Long monotone trails in random edge-labellings of random graphs
• Numerical studies of the expected height in randomly built binary search trees
• On the concentration of the height of binary search trees
• The height of random binary unlabelled trees
• A strong law for the height of random binary pyramids

This page was built for publication: On the Variance of the Height of Random Binary Search Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862790)