On the Generation of Random Binary Search Trees

DOI10.1137/S0097539792224954MaRDI QIDQ4862789zbMATH OpenOpenAlexFDO

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

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

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

(21)

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