A**splay tree**is abinary search treewith the additional property that recently accessed elements are quick to access again. Like self-balancing binary search tree

All normal operations on a binary search tree are combined with one basic operation, called*splaying*.

**Advantages**

- Good performance for a splay tree depends on the fact that it is self-optimizing.

2. Frequently accessed nodes will move nearer to the root where they can be accessed more quickly.

3. Comparable performance: Average-case performance is as efficient as other trees.

4. Small memory footprint: Splay trees do not need to store any bookkeeping data.

**Disadvantages**

- The most significant disadvantage of splay trees is that the height of a splay tree can be linear.
- this will be the case after accessing all
*n*elements in non-decreasing order. - Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of a single operation can be high.
- The representation of splay trees can change even when they are accessed in a 'read-only' manner.

**Zig step:** In this step is done when*p*is the root.The tree is rotated on the edge between*x*and*p*. Zig steps exist to deal with the parity issue, will be done only as the last step in a splay operation, and only when*x*has odd depth at the beginning of the operation.

**Zig-zig step:**this step is done when*p*is not the root and*x*and*p*are either both right children or are both left children. The picture below shows the case where*x*and*p*are both left children. The tree is rotated on the edge joining*p*with*its*parent*g*, then rotated on the edge joining*x*with*p*. Note that zig-zig steps are the only thing that differentiate splay trees from the*rotate to root*method introduced by Allen and Munro[4]prior to the introduction of splay trees.

**Zig-zag step:**this step is done when*p*is not the root and*x*is a right child and*p*is a left child or vice versa. The tree is rotated on the edge between*p*and x, and then rotated on the resulting edge between*x*and g.