Splay Trees

Introduction

A splay tree is just a binary search tree that has excellent performance in the cases where some data is accessed more frequently than others. The tree self-adjusts after lookup, insert and delete operations.

A splay tree does not necessarily have minimum height, nor does it necessarily have logarithmically bounded height. In fact a splay tree may even be degenerate. However, it is based on the idea that if you recently used something you'll likely need it again soon, so it keeps the most commonly used data near the top where it is accessed most quickly.

A good animation of splay trees is here.

How it Works

After each insert, delete, or lookup, you splay:

• The node you just looked up, or
• The node you just inserted, or
• The parent of the node you just deleted

Splaying

The splay operation on a node N is as follows:

while N is not the root:
    if N is a child of the root:
        // ZIG:
        Rotate about the root to bring N to the root
    else:
        P ← N.parent
        G ← P.parent  // the grandparent of N
        if N and P are both left or both right children:
            // ZIG-ZIG:
            Rotate about G then about P to bring N up two levels
        else:
            // ZIG-ZAG:
            Rotate about P then about G to bring N up two levels

That's all it is! Here's an example We're splaying the 14:

Summary