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

average case analysisbinary search treedata structure

Mathematics Subject Classification ID

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

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

• A trivial algorithm whose analysis is not: a continuation
• A trivial algorithm whose analysis isn't
• 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?)
• 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

(16)

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

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)