An O( n)-competitive binary search tree with optimal worst-case access times

DOI10.1007/978-3-642-13731-0_5zbMATH Open1285.68041OpenAlexW3122708175MaRDI QIDQ3569877FDOQ3569877

Authors: Prosenjit Bose, Karim Douïeb, Vida Dujmović, Rolf Fagerberg 

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_5

Recommendations

• De-amortizing binary search trees
• Dynamic Optimality—Almost
• Combining binary search trees
• Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance
• Binary search trees: How low can you go?

Mathematics Subject Classification ID

Data structures (68P05)

Cited In (8)

• Lower Bounds for Accessing Binary Search Trees with Rotations
• Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance
• De-amortizing binary search trees
• A history of distribution-sensitive data structures
• A balanced search tree O(1) worst-case update time
• Combining binary search trees
• Title not available (Why is that?)
• Better analysis of binary search tree on decomposable sequences

This page was built for publication: An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times

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