Effective splaying with restricted rotations
Joan M. Lucas · International Journal of Computer Mathematics · 2008
The splay tree is a well-known binary search tree with many remarkable properties. It is a self-adjusting data structure whose amortized performance matches any of the many forms of balanced search trees. Furthermore, splay trees are adaptive, and have superior performance in many specialized cases. It is a long-standing open problem whether splay trees are dynamically optimal. Most search tree algorithms are based on the fundamental rotation operation. In 2002 Cleary introduced the concept of restricted rotations, which severely limits where the rotation can be performed. We show that splaying can still be effected using only restricted rotations, while maintaining the same properties as regular splay trees.