# Splay Trees

Time for something really cool! We don’t have to try to minimize, or near minimize the height of a search tree to get good performance. You’ll like these, I promise.

## 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

We’ve covered:

- What a splay tree is
- The fact they can be degenerate
- How they work