Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance

DOI10.1007/11940128_29MaRDI QIDQ5459123zbMATH OpenOpenAlexFDO

Authors Jussi Kujala, Tapio Elomaa

Publication date 24 April 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11940128_29

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• Dynamic Optimality—Almost
• A balanced search tree O(1) worst-case update time
• Alternatives to splay trees with O( n) worst-case access times
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME

Cited in

(1)

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

This page was built for publication: Poketree: A Dynamically Competitive Data Structure with Good Worst-Case Performance

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