Explore modules

Splay Tree

Visualize a self-adjusting search tree that moves recently accessed elements to the root.

Free theory article

Visualize a self-adjusting search tree that moves recently accessed elements to the root.

Concept & interpretation

A Splay Tree is a self-adjusting binary search tree that stores no explicit height or color metadata. Instead, every insertion, lookup, or access performs a sequence of double rotations (splaying) that moves the accessed node x all the way to the root while roughly halving the depth of every node along the access path, achieving O(log n) amortized time per operation.

Interactive Experiment: What to Enter and Observe

Open the Splay Tree module to watch newly inserted keys splay to the root and observe the sequence of Zig, Zig-Zig, and Zig-Zag steps:

  1. Set Nodes to Insert to 10 and Animation Speed to 1200ms.
  2. Note the first value in the Pending Insertions queue, then click Play.
  3. For each insertion, confirm two things on the canvas and in the Status card: (a) the newly inserted value always finishes at the amber-highlighted root node at the top of the canvas, and (b) the Status card lists the exact sequence of splay steps (e.g., Zig-Zag (Left-Right) -> Zig (Right)) used to bring it there.
  4. Press Pause when a deep leaf is inserted to compare how a Zig-Zig step restructures the path into a more balanced subtree before the next key is inserted.
Read the full free theory article