Randomized binary search technique

DOI10.1145/362848.362856MaRDI QIDQ5554721zbMATH OpenOpenAlexFDO

Authors Warren T. Dent, S. R. Arora

Publication date 1969

Published in Communications of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/362848.362856

zbMATH Keywords

numerical analysis

Cited in

(8)

• A principle of independence for binary tree searching
• Binary search trees constructed from nondistinct keys with/without specified probabilities
• Emerging behavior as binary search trees are symmetrically updated.
• Mixed Poisson approximation of node depth distributions in random binary search trees
• One-sided variations on binary search trees
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• The m-version of binary search trees: an average case analysis
• Random binary trees: from the average case analysis to the asymptotics of distributions

This page was built for publication: Randomized binary search technique

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