Deletions in random binary search trees: a story of errors

DOI10.1016/J.JSPI.2010.01.028zbMATH Open1278.68081OpenAlexW1970716997MaRDI QIDQ972839FDOQ972839

Authors Wolfgang Panny 

Publication date 21 May 2010

Published in Journal of Statistical Planning and Inference (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jspi.2010.01.028

zbMATH Keywords

analysis of algorithmsrandom binary search treedeletions

Mathematics Subject Classification ID

Data structures (68P05) Combinatorial probability (60C05)

Recommendations

• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• Randomness Preserving Deletions on Special Binary Search Trees
• Randomized binary search trees
• A trivial algorithm whose analysis is not: a continuation
• Dynamic behaviour in updating process over BST of size two with probabilistic deletion algorithms

Cites Work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• A trivial algorithm whose analysis is not: a continuation
• A trivial algorithm whose analysis isn't
• A unifying look at data structures
• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• Deletions That Preserve Randomness
• Distribution of distances in random binary search trees.
• On the efficiency of a new method of dictionary construction
• Randomized binary search trees
• Randomized search trees
• Some Combinatorial Properties of Certain Trees With Applications to Searching and Sorting
• The height of a random binary search tree
• Trees, Forests and Rearranging

Cited In (5)

• Deletion: The curse of the red-black tree
• Randomness Preserving Deletions on Special Binary Search Trees
• Analysis of the standard deletion algorithms in exact fit domain binary search trees
• A class of random recursive tree algorithms with deletion
• A trivial algorithm whose analysis isn't

This page was built for publication: Deletions in random binary search trees: a story of errors

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