Splay Trees

Self-adjusting: every access rotates its node to the root, so the keys you use most become the cheapest to reach. No balance factors, no colours — just the access pattern.

O(log n) amortised

O(n) worst single access

No extra bytes per node

Zig · Zig-Zig · Zig-Zag

Keys to insert

Then access, in order

Repeat a key to see the second access cost one comparison.

Speed: 1200ms

Step 1 of 0—

ZIG

parent is root

ZIG-ZIG

straight line

ZIG-ZAG

elbow

Tree

Empty tree — waiting for the first insertion

node being splayedparent / grandparent

Current Step

Click Play to begin

Complexity

Amortised:O(log n)

Single worst:O(n)

Repeated key:O(1)

Space:O(n)

Key Concepts

Locality for free: hot keys drift to the top
No metadata: no colour, no height, no balance factor
Zig-zig order matters — grandparent first, or the bound fails
Reads mutate the tree, which complicates concurrency

Compare with the red-black tree →

Knowledge Check

Question 1 of 3

What does a splay tree do after every single access?

Indexing

Hashing your keys…

DSAverse

Splay Trees

Tree

Current Step

Complexity

Key Concepts

Knowledge Check

Splay Trees

Tree

Current Step

Complexity

Key Concepts

Knowledge Check