Splay Tree

Daniel Sleator & Robert Tarjan, 1985

Splay trees achieve amortized O(log n) performance by splaying each accessed node to the root using zig, zig-zig, and zig-zag rotations. This makes frequently accessed elements faster to reach. Unlike AVL or Red-Black trees, splay trees require no stored balance information. The visualization shows nodes being accessed and splayed to the root step by step.