On the Variance of the Height of Random Binary Search Trees

DOI10.1137/S0097539792237541zbMATH Open0845.68027MaRDI QIDQ4862790FDOQ4862790

Publication date: 15 September 1996

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

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

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

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 binary search trees
The variance of the height of digital search trees
A Greedy Algorithm Estimating the Height of Random Trees
Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
On Robson's convergence and boundedness conjectures concerning the height of binary search trees
Combinatorial differential operators in: Faà di Bruno formula, enumeration of ballot paths, enriched rooted trees and increasing rooted trees
Uniform distribution modulo one and binary search trees
Constant bounds on the moments of the height of binary search trees
How tall is a tree?
Smoothed analysis of binary search trees
An analytic approach to the height 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
Title not available (Why is that?)
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)