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

DOI10.1007/BF01840390zbMATH Open0696.68031OpenAlexW2080437655MaRDI QIDQ911249FDOQ911249

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
• A trivial algorithm whose analysis is not: a continuation
• A trivial algorithm whose analysis isn't
• Trees, Forests and Rearranging
• On the efficiency of a new method of dictionary construction

Cited In (14)

• 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
• Optimal binary search trees
• Reductions in 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
• Title not available (Why is that?)
• On deletion in threaded binary trees

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)