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


Jonathan Derryberry, Daniel Dominic Sleator


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


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