De-amortizing Binary Search Trees

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

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelAutomata, Languages, and Programming
Publikationsdato2012
Sider121-132
ISBN (Trykt)978-3-642-31593-0
ISBN (Elektronisk)978-3-642-31594-7
DOI
StatusUdgivet - 2012
Begivenhed39th International Colloquium - Warwick, Storbritannien
Varighed: 9. jul. 201213. jul. 2012
Konferencens nummer: 39

Konference

Konference39th International Colloquium
Nummer39
LandStorbritannien
ByWarwick
Periode09/07/201213/07/2012
NavnLecture Notes in Computer Science
Vol/bind7391
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'De-amortizing Binary Search Trees'. Sammen danner de et unikt fingeraftryk.

Citationsformater