On the Generation of Random Binary Search Trees

DOI10.1137/S0097539792224954zbMATH Open0841.68061OpenAlexW2038309235MaRDI QIDQ4862789FDOQ4862789

Authors Luc 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 binary search treesrandom permutation model

Mathematics Subject Classification ID

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

Recommendations

• The generation of binary trees as a numerical problem
• Generating random binary trees -- a survey
• A Comparison of Random Binary Tree Generators
• Generating binary trees at random
• A note on the height of binary search trees

Cited in

(19)

• scientific article; zbMATH DE number 1984548 (Why is no real title available?)
• Average depth in a binary search tree with repeated keys
• Numerical studies of the expected height in randomly built binary search trees
• Constant bounds on the moments of the height of binary search trees
• An Improved Bound for Random Binary Search Trees with Concurrent Insertions
• Optimal binary search trees
• A Comparison of Random Binary Tree Generators
• On the concentration of the height of binary search trees
• scientific article; zbMATH DE number 3994870 (Why is no real title available?)
• scientific article; zbMATH DE number 1305510 (Why is no real title available?)
• Randomness Preserving Deletions on Special Binary Search Trees
• Generating binary trees at random
• Generating random binary trees -- a survey
• Analysis of the space of search trees under the random insertion algorithm
• scientific article; zbMATH DE number 168426 (Why is no real title available?)
• A generator of heavy-tailed search trees
• Binarization Trees and Random Number Generation
• A note on Rémy's algorithm for generating random binary trees
• On the probability distribution of the values of binary trees

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

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