Data Structures algorithms / interactive lesson

Splay Tree

Watch a self-adjusting binary search tree move each inserted key to the root with zig, zig-zig, and zig-zag rotations.

University Guided lesson

Self-adjusting binary search tree

Splay tree

Step 1 / 51initialize

About the algorithm

A splay tree is a self-adjusting binary search tree. After every access or insertion, the touched node is rotated to the root using zig, zig-zig, and zig-zag steps.

Self-adjusting idea

Unlike AVL or Red-Black trees, a splay tree stores no balance metadata. It adapts to the access sequence: recently used keys move near the root and become cheap to access again.

Rotations

If the node has only a parent, use one zig rotation. If node, parent, and grandparent lean in the same direction, use zig-zig. If they form an inner corner, use zig-zag.

Amortized cost

A single operation can take linear time on an unlucky tree, but over a sequence of operations the amortized cost is O(log n).

Code companion

Connect each visual decision to an implementation pattern.

splay(x):
  while x.parent exists:
    p = x.parent
    g = p.parent

    if g does not exist:
      rotate x over p                  // zig
    else if x and p are both left or both right children:
      rotate p over g
      rotate x over p                  // zig-zig
    else:
      rotate x over p
      rotate x over g                  // zig-zag