The amortized complexity of non-blocking binary search trees

DOI10.1145/2611462.2611486MaRDI QIDQ2943634zbMATH OpenOpenAlexFDO

Authors Faith Ellen, Panagiota Fatourou, Joanna Helga, Eric Ruppert

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2611462.2611486

zbMATH Keywords

amortized analysisasynchronousbinary search treecompare-and-swapconcurrentlock-freenon-blocking

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• De-amortizing binary search trees
• Efficient lock-free binary search trees
• Binary search trees: How low can you go?
• The amortized analysis of a non-blocking chromatic tree
• Binary search trees of almost optimal height

Cited in

(12)

• On the existence and construction of non-extreme (a,b)-trees.
• Non-blocking Patricia tries with replace operations
• The amortized analysis of a non-blocking chromatic tree
• The cost of offline binary search tree algorithms and the complexity of the request sequence
• Efficient lock-free binary search trees
• Lower bounds on the amortized time complexity of shared objects
• The amortized analysis of a non-blocking chromatic tree
• Non-blocking doubly-linked lists with good amortized complexity
• A Wait-free Queue with Polylogarithmic Step Complexity
• TSLQueue: an efficient lock-free design for priority queues
• Lower bounds on the amortized time complexity of shared objects
• A wait-free queue with polylogarithmic step complexity

This page was built for publication: The amortized complexity of non-blocking binary search trees

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