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

preprint2010arXivOpen access

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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Write a reviewWrite

No reviews yet.

Add a commentWrite

No comments yet.

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

Abstract

Connections

Building this map preview

Reviews 0

Discussion 0