What is a Splay Tree? When would you use it?

Difficulty: 6/10

self-adjusting BST, amortized analysis, cache

Splay Tree

A Splay Tree is a self-adjusting binary search tree. Whenever a node is accessed, the tree performs rotations to move that node toward the root. It does not maintain a strict balance invariant, so an individual operation can take O(n), but the amortized cost of search, insertion, and deletion is O(log n). It is useful when access patterns exhibit locality, meaning recently accessed items are likely to be accessed again.

javascript

1
No explicit balance metadata is required.
2
Amortized operation complexity: O(log n).
3
Worst-case individual operation: O(n).
4
Frequently accessed elements tend to move near the root.
5
Useful when temporal or spatial locality is important.

Scenario Questions

0-2 years experience

Follow-up Questions