De-amortizing binary search trees

DOI10.1007/978-3-642-31594-7_11MaRDI QIDQ2843241zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Sébastien Collette, Rolf Fagerberg, Stefan Langerman

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1665

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05)

Abstract: We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in O(log n) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(log log n) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(log n) worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in O(log n) worst case time.

Recommendations

• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• Binary search trees: How low can you go?
• Combining binary search trees
• scientific article; zbMATH DE number 5237331
• Self-adjusting binary search trees

Cited in

(9)

• Layered working-set trees
• In pursuit of the dynamic optimality conjecture
• The amortized complexity of non-blocking binary search trees
• Greedy is an almost optimal deque
• Layered working-set trees
• An \(O(\log \log n)\)-competitive binary search tree with optimal worst-case access times
• scientific article; zbMATH DE number 1222814 (Why is no real title available?)
• File maintenance: when in doubt, change the layout!
• Combining binary search trees

This page was built for publication: De-amortizing binary search trees

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