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

DOI10.1007/978-3-642-13731-0_5MaRDI QIDQ3569877zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

Data structures (68P05)

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?

Cited in

(8)

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

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)