Effective splaying with restricted rotations

Abstract

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.

Keywords:

• Splay tree
• Binary tree
• Restricted rotations
• Data structures

AMS Subject Classification::

• 68P05
• 68P10
• 68P15
• 68R05
• 68W40

Additional information

Notes on contributors

Joan M. Lucas

Email: [email protected]