O(log log n)-Competitive Dynamic Binary Search Trees

Co-authors

Jonathan Derryberry, Daniel Dominic Sleator

Abstract

We introduce the multi-splay tree (MST) data structure, which is the
first binary search tree (BST) to simultaneously achieve $O(\log n)$
amortized, $O(\log^2 n)$ worst-case, and $O(\log \log n)$-competitive
costs for a sequence of queries. We also prove the sequential access
lemma for MSTs, which states that sequentially accessing all keys
takes linear time.

Furthermore, we generalize the standard framework for competitive
analysis of BST algorithms to include updates (insertions and
deletions) in addition to queries. In doing so, we extend the lower
bound of Wilber and Demaine et al. to
handle these update operations. We show how MSTs can be modified to
support these update operations and be expected $O(\log \log
n)$-competitive in the new framework, while maintaining the rest of
the properties above in expectation. (The modified MST algorithm
makes use of randomization.)