Splay Tree

Splay Tree

A splay tree is a self-adjusting binary search tree that automatically reorganizes itself after each operation to optimize access to frequently accessed elements. It was introduced by Daniel Sleator and Robert Tarjan in 1985.

The key feature of a splay tree is its "splay" operation, which reorganizes the tree by moving a recently accessed node to the root. The splay operation performs a series of rotations on the tree to bring the accessed node to the top, making it easier and faster to access the node again in future operations.

The splay operation consists of three main steps:


Zig-Zig or Zig-Zag:

If the accessed node (referred to as the "splay node") is a child of the root, a series of rotations called "zig-zig" or "zig-zag" rotations are performed to move the splay node to the root.

Zig-zig rotations are applied when both the splay node and its parent are left children or right children.

Zig-zag rotations are applied when the splay node is a left child and its parent is a right child, or vice versa.


Zig:

If the splay node is a direct child of the root, a single rotation called a "zig" rotation is performed to bring the splay node to the root position.


Split and Join:

After applying the zig-zig, zig-zag, or zig rotations, the splay node becomes the root of the tree.

The tree is then split into two subtrees: one containing all nodes with keys less than the splay node's key, and the other containing all nodes with keys greater than the splay node's key.

These two subtrees are joined together with the splay node as the root.


By performing the splay operation after each access, the frequently accessed nodes gradually move closer to the root, improving the overall access time for subsequent operations. This self-adjusting behavior allows the splay tree to adapt to the access patterns of the elements stored in the tree.

Splay trees have a flexible structure that allows efficient search, insertion, and deletion operations with an amortized time complexity of O(log n), where n is the number of elements in the tree. They are particularly useful in scenarios where certain elements are accessed more frequently than others, as the splay operation optimizes access to those elements.

It's important to note that splay trees do not guarantee strict balance like AVL trees or red-black trees. Instead, they optimize for frequent access patterns, which can lead to a more skewed tree structure over time. However, this does not significantly impact the overall performance of the tree in practice.