A Refined Analysis of the Sequential Access Theorem for Splay Trees

Naonori Kakimura, Yoshihiko Terai

A splay tree is a self-adjusting binary search tree that allows access, insertion, and deletion to be performed in amortized $O(\log n)$ time, where $n$ is the number of stored ele…