CS 269S, Winter 2011: Theory Seminar
Bren Hall, Room 1427
11 Feb 2011:

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.)