Splay Tree

• For when some data is accessed more frequently than other data
• A Binary Search Tree with the additional property that recently accessed elements are quick to access again
• All normal operations on a binary search tree are combined with one basic operation splaying
• Best for ensuring that most commonly accessed nodes have the least access time

Splaying

• After a node is accessed (inserted/searched/delete), it is moved to the root via “zig zag” rotations
  • for delete the inorder successor is made the root
• Types of rotations
  • When only parent
    • Zig: Right rotation (L case)
    • Zag: Left rotation (R case)
  • When parent and grandparent
    • Zig-Zig: Zig grandparent, Zig parent (LL case)
    • Zag-Zag: Zag grandparent, Zag parent (RR case)
    • Zig-Zag: Zig grandparent, Zag parent (LR case)
    • Zag-Zig: Zag grandparent, Zig parent (RL case)
• When accessing node, keep splaying node until it is the root

Performance

• $m$ tree operations will take $O(m\log n)$ time, where $n$ is the number of nodes
  • that means it will the average of $O(\log n)$ performance per operation over time
• In worst case, an operation is $O(n)$, but subsequent operations are faster

Applications

• Cache
• Garbage collection