Analysis of the standard deletion algorithms in exact fit domain binary search trees

DOI10.1007/BF01840390MaRDI QIDQ911249zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, J. Culberson

Publication date 1990

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01840390

zbMATH Keywords

data structurebinary search treeaverage case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• Randomized binary search trees
• Deletions in random binary search trees: a story of errors
• A trivial algorithm whose analysis is not: a continuation
• Deletion without rebalancing in binary search trees
• Randomization of search trees by subtree size

Cites work

• scientific article; zbMATH DE number 4033041 (Why is no real title available?)
• scientific article; zbMATH DE number 3724172 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• A trivial algorithm whose analysis is not: a continuation
• A trivial algorithm whose analysis isn't
• On the efficiency of a new method of dictionary construction
• Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
• Trees, Forests and Rearranging

Cited in

(14)

• On deletion in threaded binary trees
• Average search and update costs in skip lists
• Emerging behavior as binary search trees are symmetrically updated.
• Deletions in random binary search trees: a story of errors
• Maintaining Ideally Distributed Random Search Trees without Extra Space
• Randomness Preserving Deletions on Special Binary Search Trees
• Reductions in binary search trees
• Optimal binary search trees
• Optimal Key Tree Structure for Deleting Two or More Leaves
• Analysis of the expected search cost in skip lists
• The Analysis of an Improved Symmetric Binary B-tree Algorithm
• Randomized binary search trees
• A trivial algorithm whose analysis isn't
• scientific article; zbMATH DE number 1629950 (Why is no real title available?)

This page was built for publication: Analysis of the standard deletion algorithms in exact fit domain binary search trees

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