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

## Audrey Hesse, UC Irvine

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.

(Based on a paper by Bose, Douïeb, Dujmovic,
and Fagerberg in SWAT 2010.)