Articles • About

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.

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:

1. Left and right rotations
2. Zig-zig left-left and zig-zig right-right rotations
3. 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:

1. Does the node we are trying to rotate have a grand-parent?
2. Is the node left or right child of the parent?
3. 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:

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

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

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

4. 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;