Randomized binary search trees

DOI10.1145/274787.274812MaRDI QIDQ3841653zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Conrado Martínez, Salvador Roura

Publication date 20 August 1998

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

Full work available at URL http://www.acm.org/pubs/contents/journals/jacm/1998-45/

zbMATH Keywords

binary search treesrandomized algorithms

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Recommendations

• Randomization of search trees by subtree size
• Randomized search trees
• Maintaining Ideally Distributed Random Search Trees without Extra Space
• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• Random binary search tree with equal elements

Cited in

(33)

• Dynamic behaviour in updating process over BST of size two with probabilistic deletion algorithms
• Emerging behavior as binary search trees are symmetrically updated.
• Depth of a random binary search tree with concurrent insertions
• Radix sort trees in the large
• Randomized search trees
• Zip trees
• Reductions in binary search trees
• Can a randomized binary search have an \(O(1)\) complexity at least in practice?
• Self-adjusting trees in preactice for large text collections
• Martingales and large deviations for binary search trees
• Selection by rank in K-dimensional binary search trees
• Skip lift: a probabilistic alternative to red-black trees
• STRONGER QUICKHEAPS
• Expected Costs in Some Classes of Binary Search Trees
• Maintaining Ideally Distributed Random Search Trees without Extra Space
• Fibonacci BSTs: a new balancing method for binary search trees
• scientific article; zbMATH DE number 168426 (Why is no real title available?)
• scientific article; zbMATH DE number 1305510 (Why is no real title available?)
• Skip lift: a probabilistic alternative to red-black trees
• Randomization of search trees by subtree size
• scientific article; zbMATH DE number 7051217 (Why is no real title available?)
• Randomness Preserving Deletions on Special Binary Search Trees
• Zip Trees
• Algorithms and Computation
• Verified analysis of random binary tree structures
• Random binary search tree with equal elements
• Zip-zip trees: making zip trees more balanced, biased, compact, or persistent
• Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
• Bottom-up rebalancing binary search trees by flipping a coin
• Zip-zip trees: making zip trees more balanced, biased, compact, or persistent
• Lazy B-trees
• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• Deletions in random binary search trees: a story of errors

This page was built for publication: Randomized binary search trees

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