Splay Trees: Self-Adjusting BSTs
You'll learn: What splay trees are and how they maintain efficiency through self-adjustment rather than strict balance rules.
The Core Idea
Unlike AVL trees or Red-Black trees that enforce strict balance conditions, splay trees take a completely different approach: they automatically restructure themselves during every access operation. When you search, insert, or delete a node, the tree "splays" that node to the root through a series of rotations. This means recently accessed nodes move toward the top, making future accesses faster.
Think of a splay tree like a self-organizing bookshelf: every time you pick up a book, you move it to eye level. Frequently used books naturally end up in easy-to-reach spots, while rarely used ones drift to less convenient positions.
How They Differ from Balanced Trees
AVL and Red-Black trees maintain worst-case guarantees—every single operation is guaranteed to be O(log n). Splay trees instead provide amortized efficiency: while a single operation might occasionally take O(n) time in a degenerate case, any sequence of m operations is guaranteed to take O(m log n) time total. The expensive operations are "paid for" by many cheap ones.
Why Use Splay Trees?
Splay trees excel when access patterns have locality—when you repeatedly access the same elements or nearby elements. They're simpler to implement than AVL or Red-Black trees (no color bits or balance factors to maintain), and the self-adjusting property means hot data automatically stays near the root.
The splaying operations you'll learn next use the same rotation primitives you've seen in AVL trees, but apply them in specific patterns to move a target node upward.
Key Takeaway: Splay trees are self-adjusting BSTs that achieve amortized O(log n) performance by moving accessed nodes to the root through splaying operations, making them ideal for workloads with temporal locality.