De-amortizing Binary Search Trees

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

Research output: Chapter in Book/Report/Conference proceedingBook chapterResearchpeer-review

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(logn) worst case time. By transforming Multi-Splay Trees, we obtain a BST that is O(loglogn) competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in O(logn) worst case time. Transforming OPT proves the existence of an O(1)-competitive offline BST algorithm which performs at most O(log n) BST operations between each access to the keys in the input sequence. Finally, we obtain that if there is an O(1)-competitive online BST algorithm, then there is also one that performs every search in O(logn) operations worst case.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming
Publication date2012
Pages121-132
ISBN (Print)978-3-642-31593-0
ISBN (Electronic)978-3-642-31594-7
DOIs
Publication statusPublished - 2012
Event39th International Colloquium - Warwick, United Kingdom
Duration: 9. Jul 201213. Jul 2012
Conference number: 39

Conference

Conference39th International Colloquium
Number39
Country/TerritoryUnited Kingdom
CityWarwick
Period09/07/201213/07/2012
SeriesLecture Notes in Computer Science
Volume7391
ISSN0302-9743

Fingerprint

Dive into the research topics of 'De-amortizing Binary Search Trees'. Together they form a unique fingerprint.

Cite this