Splay Tree - self-adjusting binary search tree
Insert, search, and delete integer keys. Every access splays the touched node toward the root with zig, zig-zig, or zig-zag rotations, making recently used values cheaper to reach next time.
zig happens when the parent is the root. Two-step zig-zig rotates parent then node in the same direction. zig-zag rotates node twice in opposite directions.
O(n), but the amortized bound for search, insert, and delete is O(log n).
x, the visualization first splays x to the root. Then it joins the remaining left and right subtrees by splaying the maximum node of the left subtree to the top and attaching the old right subtree as its right child.
They are simple to implement, adapt to skewed workloads, and satisfy useful bounds like the working-set and static-finger properties. This makes them attractive when recent accesses strongly predict future accesses.