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 rotation occurs when the node is a child of the root (single rotation).
  • zig-zig rotation occurs when the node and its parent are on the same side (double rotation in same direction).
  • zig-zag rotation occurs when the node and its parent are on opposite sides (double rotation in opposite directions).
• After splaying, frequently accessed nodes stay near the root, making repeated operations faster.