An o(log log n)-competitive binary search tree with optimal worst-case access times
Prosenjit K. Bose, Karim Douïeb, Vida Dujmović, Rolf Fagerberg · 2010
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.