A splay tree is a binary search tree with 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.

## 0 टिप्पणियाँ:

## Post a Comment