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.
