SPLAY TREE

A splay tree is a self-balancing binary search tree intended to provide quick access to frequently accessed items in the tree. The tree performs key functions such as insert, search, and delete in O(log\space n)O(log n) amortized time. A splay tree performs these basic operations in combination with the splay operation.

Splaying involves rearranging the tree to bring a particular element to the root of the tree. This is typically done using the standard binary search tree (BST) operation in combination with tree rotations to bring the particular element to the root of the tree. These rotations do not change the BST property of the tree

SPLAYING:

After an element is accessed, the splay operation is performed, which brings the element to the root of the tree. If the element is not in a root position, splaying can take one of three patterns:

Zig (or zag) step
Zig-zig (or zag-zag) step
Zig-zag (or zag-zig) step
The step you take is dependent on the position of the node. If the node is at the root, it is immediately returned.

Zig (or zag):

When no grandparent node exists, the splay function will move the node up to the parent with a single rotation. A left rotation is a zag and a right rotation is a zig.
Note: A left rotation corresponds to a right placement (the node is right of the parent) and vice versa.

Zig-zig (or zag-zag):

When a grandparent and parent node exist and are placed in a similar orientation (e.g., the parent is left of the grandparent and the node is left of the parent), the operation is either zig-zig (left) or zag-zag (right).

Zig-zag (or zag-zig):

A zig-zag corresponds to the parent being left of the grandparent and right of the parent. A zag-zig is the opposite.

Advantages:

Splaying ensures that frequently accessed elements stay near the root of the tree so that they are easily accessible. By staying near the top of the tree, the tree can benefit from the locality of reference.
The average case performance of splay trees is comparable to other fully-balanced trees: O(log\space n)O(log n).
Splay trees do not need bookkeeping data; therefore, they have a small memory footprint.

Disadvantages:

The major disadvantage of splay trees is that - although unlikely - a splay tree can arrange itself linearly. Therefore, the worst-case performance of a splay tree is O(n)O(n).
Multithreaded operations can be complicated since, even in a read-only configuration, splay trees can reorganize themselves.