Splay Tree Rotations Explained

Let Access Shape the Tree

Imagine looking up the same key again and again, only to follow the same long path through a tree on every search. In an ordinary Binary Search Tree, a frequently used key can remain buried near the leaves while rarely used keys sit closer to the root. If you repeatedly access the same deep node, BST repeats that work every time.

A Splay Tree makes access an opportunity to reorganize. After finding a node, it moves that node to the root through a sequence of rotations called splaying. If the next search asks for the same key, the answer is already at the root. As accesses change, the tree's shape changes with them.

The Building Block

Every splay step uses ordinary BST rotations. A right rotation lifts a left child above its parent; a left rotation lifts a right child. The child's inner subtree transfers to the parent so that the inorder sequence stays unchanged.

Each rotation preserves binary search order, so the tree can reshape itself without losing its search property. The key decision is which rotation to perform next. That depends on just three nodes: the accessed node, its parent, and its grandparent. Their positions give us the three splay cases: Zig, Zig-Zig, and Zig-Zag.

Right rotation at P:          Left rotation at X:

        P                            X
       / \                          / \
      X   C          <-->          A   P
     / \                              / \
    A   B                            B   C

Inorder before and after: A, X, B, P, C

Here A, B, and C represent entire subtrees, any of which may be empty. Every key in B lies between X and P, so B can safely move from X's right branch to P's left branch. With parent pointers, those pointers and the connection to the old parent's parent must also be updated.

Three Splay Cases

In the diagrams below, X is the node being splayed, P is its current parent, and G is its current grandparent. Inspect their positions, perform the matching step, then inspect X's new ancestors. Stop when X becomes the root. If X is already the root, no rotation is needed.

Case 1: Zig — One Level from the Root

X has a parent but no grandparent, so P is the root. A single rotation finishes the splay. If X is the left child, rotate right at P. If X is the right child, rotate left at P — this mirror case is called Zag.

Before:                   rotateRight(P):

        P                         X
       / \                       / \
      X   C                     A   P
     / \                           / \
    A   B                         B   C

X is now the root. Splaying is complete.

Zig is the final step when only one edge remains above X. It is not the rule to apply repeatedly when X still has a grandparent.

Case 2: Zig-Zig — Two Edges in the Same Direction

X is P's left child, and P is G's left child. First rotate right at G, lifting P above G. Then rotate right at P, lifting X above P. The order matters: rotate the grandparent first, then the parent.

Before:          rotateRight(G):    rotateRight(P):

        G                P                  X
       / \              / \                / \
      P   D            X   G              A   P
     / \              / \ / \                / \
    X   C            A  B C  D              B   G
   / \                                         / \
  A   B                                       C   D

Inorder throughout: A, X, B, P, C, G, D

X rises two levels and G moves down. For the right-right mirror, called Zag-Zag, rotate left at G, then left at P. These paired steps restructure the access path differently from simply rotating X over its parent twice. That distinction is part of the standard splay algorithm's amortized guarantee.

Case 3: Zig-Zag — Two Edges in Opposite Directions

X and P form a bend: one is a left child and the other is a right child. For example, let P be G's left child and X be P's right child. First rotate left at P, then rotate right at G. X rises between its former ancestors and becomes the root of this local subtree.

Before:          rotateLeft(P):     rotateRight(G):

        G                G                  X
       / \              / \                / \
      P   D            X   D              P   G
     / \              / \                / \ / \
    A   X            P   C              A  B C  D
       / \          / \
      B   C        A   B

Inorder throughout: A, P, B, X, C, G, D

For the mirror configuration, where P is G's right child and X is P's left child, rotate right at P, then left at G. Some descriptions distinguish the two bends as Zig-Zag and Zag-Zig. The reliable rule is to inspect the actual child positions: opposite directions mean parent first, grandparent second.

The Rotation Table

The following table covers both orientations of each case. Left and right describe child positions, while rotateLeft and rotateRight describe the operation performed at the named node.

P relative to G   X relative to P   Rotations in order
---------------   ----------------  --------------------------------
No G (P is root)  Left              rotateRight(P)
No G (P is root)  Right             rotateLeft(P)
Left              Left              rotateRight(G), rotateRight(P)
Right             Right             rotateLeft(G), rotateLeft(P)
Left              Right             rotateLeft(P), rotateRight(G)
Right             Left              rotateRight(P), rotateLeft(G)

In pseudocode, the entire bottom-up process is a loop. The rotation helpers below reconnect the rotated subtree to its former ancestor, update parent pointers, and update the tree root when necessary.

function splay(X):
  while X.parent is not null:
    P = X.parent
    G = P.parent

    if G is null:
      if X == P.left: rotateRight(P)
      else: rotateLeft(P)
    else if P == G.left and X == P.left:
      rotateRight(G)
      rotateRight(P)
    else if P == G.right and X == P.right:
      rotateLeft(G)
      rotateLeft(P)
    else if P == G.left and X == P.right:
      rotateLeft(P)
      rotateRight(G)
    else:
      rotateRight(P)
      rotateLeft(G)

Tracing a Complete Splay

Consider searching for 20 in the tree below. The BST search follows 100 → 80 → 40 → 20. Finding the key is only the first part; now splay that same node to the root.

Initial tree:    After Zig-Zig:     After final Zig:

      100              100                 20
      /                /                     \
     80               20                     100
    /                   \                   /
   40                   40                 40
  /                       \                 \
 20                       80                 80

1. X = 20, P = 40, G = 80: left-left.
   rotateRight(80), then rotateRight(40).

2. X = 20, P = 100, no grandparent: Zig.
   rotateRight(100).

Final inorder sequence: 20, 40, 80, 100

The ancestors change after each step, but X remains the same node. This splay uses three rotations. The resulting tree need not be perfectly balanced; the goal is to bring the accessed key to the root.

Open the Splay Tree Visualizer, insert a few keys, and search for a node below the root. Pause before each step and identify X, P, and G. Decide whether the edges point in the same direction or opposite directions, then predict which node rotates first. The visualizer also suppors deletion.

When Splaying Happens

• Search: follow BST comparisons, then splay the matching node. Even a lookup can change the tree. If the search is unsuccessful, splay the last visited node.
• Insertion: insert a new key as a BST leaf, then splay that new node to the root.
• Deletion: splay the target to the root and remove it. If its left subtree exists, make that subtree the tree and splay its maximum key. This new root has no right child, so attach the removed root's right subtree there. If the left subtree is empty, the right subtree becomes the tree directly.

Amortized Operations

Each rotation takes O(1), but an entire splay may require one rotation per edge on the path to the root. A tree with n nodes can have height n − 1, so one search and its splay can take O(n).

However, across a sequence of operations, splay trees guarantee O(log n) amortized time per operation. Splaying can be useful when access is concentrated on a small set of keys. It reshapes and flattens deep paths so that subsequent operations run much faster on average.