An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times

Prosenjit Bose, Karim Douïeb, Vida Dujmović, Rolf Fagerberg

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

We present the zipper tree, an O(log log n)-competitive online binary search tree that performs each access in O(logn) worst-case time. This shows that for binary search trees, optimal worst-case access time and near-optimal amortized access time can be guaranteed simultaneously.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume6139
Pages (from-to)38-49
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2010

Fingerprint

Binary Search Tree
Fasteners

Cite this

Bose, Prosenjit ; Douïeb, Karim ; Dujmović, Vida ; Fagerberg, Rolf. / An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times. In: Lecture Notes in Computer Science. 2010 ; Vol. 6139. pp. 38-49.
@inproceedings{1b62b891b69e4ef0acfa74b1b619b1a0,
title = "An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times",
abstract = "We present the zipper tree, an O(log log n)-competitive online binary search tree that performs each access in O(logn) worst-case time. This shows that for binary search trees, optimal worst-case access time and near-optimal amortized access time can be guaranteed simultaneously.",
author = "Prosenjit Bose and Karim Dou{\"i}eb and Vida Dujmović and Rolf Fagerberg",
note = "Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)",
year = "2010",
doi = "10.1007/978-3-642-13731-0_5",
language = "English",
volume = "6139",
pages = "38--49",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Heinemann",

}

An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times. / Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Fagerberg, Rolf.

In: Lecture Notes in Computer Science, Vol. 6139, 2010, p. 38-49.

Research output: Contribution to journalConference articleResearchpeer-review

TY - GEN

T1 - An O(log log n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times

AU - Bose, Prosenjit

AU - Douïeb, Karim

AU - Dujmović, Vida

AU - Fagerberg, Rolf

N1 - Proc. 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT)

PY - 2010

Y1 - 2010

N2 - We present the zipper tree, an O(log log n)-competitive online binary search tree that performs each access in O(logn) worst-case time. This shows that for binary search trees, optimal worst-case access time and near-optimal amortized access time can be guaranteed simultaneously.

AB - We present the zipper tree, an O(log log n)-competitive online binary search tree that performs each access in O(logn) worst-case time. This shows that for binary search trees, optimal worst-case access time and near-optimal amortized access time can be guaranteed simultaneously.

U2 - 10.1007/978-3-642-13731-0_5

DO - 10.1007/978-3-642-13731-0_5

M3 - Conference article

VL - 6139

SP - 38

EP - 49

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -