Splay Tree
A Splay Tree is a self-adjusting binary search tree that reshapes itself based on how it’s used. Instead of trying to stay balanced all the time, it aggressively moves recently accessed nodes closer to the root. The idea is simple: if you touched it, you’ll probably touch it again. Over time, the tree adapts to access patterns rather than an abstract notion of balance.
How it Works
- When you search, insert, or delete a node, the tree performs a series of rotations called splaying to bring that node to the root.
- There are three types of rotations depending on the node’s position: zig (single rotation), zig-zig (double rotation in same direction), and zig-zag (double rotation in opposite directions).
- After splaying, frequently accessed nodes stay near the root, making repeated operations faster.
Curious to Learn More?
Hand-picked resources to deepen your understanding
As an Amazon Associate, I earn from qualifying purchases. This helps support the site at no extra cost to you.
© 2025 SEE Algorithms. Code licensed under MIT, content under CC BY-NC 4.0.