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.

School of Computer Science

Bose, P, Douïeb, K. (Karim), Dujmović, V, & Fagerberg, R. (Rolf). (2010). An O(log log n)-competitive binary search tree with optimal worst-case access times. doi:10.1007/978-3-642-13731-0_5