Chain-splay trees, or, how to achieve and prove log log N-competitiveness by splaying

摘要

We present an extension of the splay technique, the chain-splay. Chain-splay trees 'splay' the accessed element to the root as classical splay trees do, but also perform some local 'house-keeping' splay operations below the accessed element. We prove that chain-splay is log log N-competitive to any off-line algorithm that maintains a binary search tree with rotations. This result is the nearest point to the dynamic optimality that splay trees have reached since 1983.