Asplay treeis 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, calledsplaying.

Advantages

1. 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

1. The most significant disadvantage of splay trees is that the height of a splay tree can be linear.
2. this will be the case after accessing allnelements in non-decreasing order.
3. 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.
4. The representation of splay trees can change even when they are accessed in a 'read-only' manner.

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

Zig-zig step:this step is done whenpis not the root andxandpare either both right children or are both left children. The picture below shows the case wherexandpare both left children. The tree is rotated on the edge joiningpwithitsparentg, then rotated on the edge joiningxwithp. Note that zig-zig steps are the only thing that differentiate splay trees from therotate to rootmethod introduced by Allen and Munro[4]prior to the introduction of splay trees.

Zig-zag step:this step is done whenpis not the root andxis a right child andpis a left child or vice versa. The tree is rotated on the edge betweenpand x, and then rotated on the resulting edge betweenxand g.