*Splay trees* are
self-adjusting binary search trees that reduces the number of
operations required to access recently accessed nodes. It achieves
this property by bringing recently accessed nodes closer to the *root*
of the tree.

The Splay tree algorithm was invented by Daniel D. Sleator and Robert E. Tarjan in 1985. For a complete explanation of the algorithm and the time-complexity proof, see the original paper describing the algorithm.

In this article, we elaborate on the tree rotations so that they can
be recalled from memory. In the following sections, we demonstrate
*bottom-up* splaying when adding and finding tree nodes. For a
complete implementation of *top-down* splaying, see Daniel
D. Sleator's Java
and
C
implementations.

## Source code

The complete source code for *bottom-up* splaying is available at:

https://github.com/gyaikhom/binary-search-trees.git

## Structure of a tree node

Each of the tree nodes has the following structure:

```
class BinarySearchTreeNode {
public:
BinarySearchTreeNode(int keyValue) : key(keyValue) {
parent = left = right = 0;
visited = false;
};
bool operator<(const BinarySearchTreeNode& other);
bool operator==(const BinarySearchTreeNode& other);
void print() {
cout << key << " ";
}
protected:
int key;
BinarySearchTreeNode *parent, *left, *right;
bool visited;
};
```

## Tree rotations

To bring the recently accessed node closer to the tree *root*, a splay
tree uses tree rotations. There are six types of tree rotations,
three of which are symmetric to the other three. These are as follows:

- Left and right rotations
- Zig-zig left-left and zig-zig right-right rotations
- Zig-zag left-right and zig-zag right-left rotations

The first type of rotations, either left or right, is always a
*terminal rotation*. In other words, the splaying is complete when we
finish a left or right rotation.

### Deciding which rotation to use

The decision to choose one of the above rotations depends on three things:

- Does the node we are trying to rotate have a grand-parent?
- Is the node left or right child of the parent?
- Is the parent left or right child of the grand-parent?

If the node does not have a grand-parent, we carry out a left rotation if it is the right child of the parent; otherwise, we carry out a right rotation.

If the node has a grand-parent, we have four cases to choose from:

If node is left of parent and parent is left of grand-parent, we do a

*zig-zig right-right*rotation.If node is left of parent but parent is right of grand-parent, we do a

*zig-zag right-left*rotation.If node is right of parent and parent is right of grand-parent, we do a

*zig-zig left-left*rotation.Finally, if node is right of parent but parent is left or grand-parent, we do a

*zig-zag left-right*rotation.

The actual rotations are described in the following sections.

## Left and right rotations

The following shows the intermediate steps in understanding a right rotation. The left rotation is symmetric to this.

As we can see, each of the left or right rotations requires **five**
pointer updates:

```
if (current == parent->left) {
/* right rotate */
parent->left = current->right;
if (current->right)
current->right->parent = parent;
parent->parent = current;
current->right = parent;
} else {
/* left rotate */
parent->right = current->left;
if (current->left)
current->left->parent = parent;
parent->parent = current;
current->left = parent;
}
current->parent = 0;
```

## Zig-zig right-right and left-left rotations

The following shows the intermediate steps in understanding a zig-zig
right-right rotation. The zig-zig left-left rotation is symmetric to
this. Note in the following that with zig-zig rotations, we first do a
right or left rotation on the **parent**, before doing a right or
left rotation on the **node**.

As we can see, zig-zig right-right rotation requires **nine**
pointer updates.

```
/* zig-zig right-right rotations */
if (current->right)
current->right->parent = parent;
if (parent->right)
parent->right->parent = grandParent;
current->parent = grandParent->parent;
grandParent->parent = parent;
parent->parent = current;
grandParent->left = parent->right;
parent->right = grandParent;
parent->left = current->right;
current->right = parent;
```

The same number of pointer updates for zig-zig left-left rotation.

```
/* zig-zig left-left rotations */
if (current->left)
current->left->parent = parent;
if (parent->left)
parent->left->parent = grandParent;
current->parent = grandParent->parent;
grandParent->parent = parent;
parent->parent = current;
grandParent->right = parent->left;
parent->left = grandParent;
parent->right = current->left;
current->left = parent;
```

## Zig-zag left-right and right-left rotations

The following shows the intermediate steps in understanding a zig-zag
left-right rotation. The zig-zag right-left rotation is symmetric to
this. Note in the following that with zig-zag rotations, we do both
rotations on the **node**, in contrast to zig-zig rotations.

As we can see, zig-zag left-right rotation requires **nine**
pointer updates.

```
/* zig-zag right-left rotations */
if (current->left)
current->left->parent = grandParent;
if (current->right)
current->right->parent = parent;
current->parent = grandParent->parent;
grandParent->parent = current;
parent->parent = current;
grandParent->right = current->left;
parent->left = current->right;
current->right = parent;
current->left = grandParent;
```

The same number of pointer updates for zig-zag right-left rotation.

```
/* zig-zag left-right rotations */
if (current->left)
current->left->parent = parent;
if (current->right)
current->right->parent = grandParent;
current->parent = grandParent->parent;
grandParent->parent = current;
parent->parent = current;
grandParent->left = current->right;
parent->right = current->left;
current->left = parent;
current->right = grandParent;
```