On the Generation of Random Binary Search Trees

DOI10.1137/S0097539792224954zbMath0841.68061OpenAlexW2038309235MaRDI QIDQ4862789

Luc P. Devroye, John Michael Robson

Publication date: 25 February 1996

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

Full work available at URL: https://doi.org/10.1137/s0097539792224954

zbMATH Keywords

random permutation modelrandom binary search trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Monte Carlo methods (65C05) Combinatorial probability (60C05) Random number generation in numerical analysis (65C10) Data structures (68P05) Pseudo-random numbers; Monte Carlo methods (11K45)

Related Items (4)

On the concentration of the height of binary search trees ⋮ Optimal binary search trees ⋮ Generating random binary trees -- a survey ⋮ Constant bounds on the moments of the height of binary search trees

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