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

(2) Department of Mathematics; Carleton University; Computer Science; Karim Dou\"ieb (1); Prosenjit Bose (1); Rolf Fagerberg (2) ((1) School of Computer Science; University of Southern Denmark); Vida Dujmovic (1)

arxiv: 1003.0139 · v1 · pith:CX4SQSUEnew · submitted 2010-02-27 · 💻 cs.DS

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

Prosenjit Bose (1) , Karim Dou\"ieb (1) , Vida Dujmovic (1) , Rolf Fagerberg (2) ((1) School of Computer Science , Carleton University , (2) Department of Mathematics , Computer Science , University of Southern Denmark) This is my paper

classification 💻 cs.DS

keywords accessbinarysearchtimetreeworst-casecompetitiveoptimal

0 comments

read the original abstract

We present the zipper tree, an $O(\log \log n)$-competitive online binary search tree that performs each access in $O(\log n)$ 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.

This paper has not been read by Pith yet.

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

discussion (0)