Skip to content

Splay Tree Hot Sheet

Use this page when one self-adjusting ordered set is the real structure, or you want the rotate / splay / parent-pointer refresher before link-cut tree.

Do Not Use When

Choose By Signal

  • one dynamic ordered set with rank / k-th and GNU allowed -> PBDS
  • split/merge ordered set or mutable sequence -> Treap
  • self-adjusting ordered set and you explicitly want the splaying machinery -> Splay
  • dynamic forest with link / cut / path -> Link-Cut Tree

Core Invariants

  • BST order on keys
  • duplicates are usually stored through one cnt field
  • subtree size includes duplicates
  • every important access ends with splay(x)
  • parent pointers and child pointers must stay consistent through rotations

Main Traps

  • forgetting to update size after rotate
  • forgetting to maintain parent pointers
  • confusing amortized O(log n) with worst-case per operation
  • using splay because it is "advanced" when PBDS or treap is the cleaner route
  • bringing the wrong node to the root after a failed search

Exact Starter Route

Reopen Paths