12 May 2014, Monday

The Splay tree data structure is a self-adjusting binary search tree that reduces the number of operations required to access recently accessed nodes within the tree. 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.

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

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

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;
};
```

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.

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.

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;
```

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;
```

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;
```

Copyright © 2022 Gagarine Yaikhom