Questions
24 of 26
What is a Splay Tree? When would you use it?
Difficulty: 5/10
Splay Tree
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.
Follow-up Questions
- What are Zig, Zig-Zig, and Zig-Zag operations?
- Why can an individual splay operation be O(n)?