Next: 4.5.1 Search, Insert, Delete in Bottom-up Splaying Up: 4. Binary Trees Previous: 4.4.1 Average Case Analysis of BST Operations

4.5 Splay Trees

REF.: Daniel D Sleator and Robert E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, Volume 32, Number 3, pp. 652-686, 1985.
REF.: Robert E. Tarjan. Amortized computational complexity. SIAM Journal on Algebraic and Discrete Methods, Volume 6, Number 2, pp. 306-318, 1985.

These are binary search trees which are self-adjusting in the following way:
Every time we access a node of the tree, whether for retrieval or insertion or deletion, we perform radical surgery on the tree, resulting in the newly accessed node becoming the root of the modified tree. This surgery will ensure that nodes that are frequently accessed will never drift too far away from the root whereas inactive nodes will get pushed away farther from the root.
Amortized complexity
- Splay trees can become highly unbalanced so that a single access to a node of the tree can be quite expensive.
- However, over a long sequence of accesses, the few expensive cases are averaged in with many inexpensive cases to obtain good performance.
Does not need heights or balance factors as in AVL trees and colours as in Red-Black trees.
The surgery on the tree is done using rotations, also called as splaying steps. There are six different splaying steps.

1.
Zig Rotation (Right Rotation)
2.
Zag Rotation (Left Rotation)
3.
Zig-Zag (Zig followed by Zag)
4.
Zag-Zig (Zag followed by Zig)
5.
Zig-Zig
6.
Zag-Zag
Consider the path going from the root down to the accessed node.
- Each time we move left going down this path, we say we ``zig'' and each time we move right, we say we ``zag.''
Figure 4.17: Zig rotation and zag rotation
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzigzag1.ps,width=5.5in}} \end{figure}$


Figure 4.18: Zig-zag rotation
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzigzag2.ps,width=5in}} \end{figure}$


Figure 4.19: Zag-zig rotation
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzagzig.ps,width=5in}} \end{figure}$


Figure 4.20: Zig-zig and zag-zag rotations
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzigzag3.ps,width=5in}} \end{figure}$


Figure 4.21: Two successive right rotations
$\begin{figure} \par \centerline{\psfig{figure=figures/Fright2.ps,width=5in}} \end{figure}$
Zig Rotation and Zag Rotation
- Note that a zig rotation is the same as a right rotation whereas the zag step is the left rotation.
- See Figure 4.17.
Zig-Zag
- This is the same as a double rotation in an AVL tree. Note that the target element is lifted up by two levels.
- See Figure 4.18.
Zag-Zig
- This is also the same as a double rotation in an AVL tree.
- Here again, the target element is lifted up by two levels.
- See Figure 4.19.
Zig-Zig and Zag-Zag
- The target element is lifted up by two levels in each case.
- Zig-Zig is different from two successive right rotations; zag-zag is different from two successive left rotations. For example, see Figures 4.20, and 4.21.
See Figure 4.22 for an example

Figure 4.22: An example of splaying
$\begin{figure} \centerline{\psfig{figure=figures/Fsplay1.ps,width=5in}} \end{figure}$
The above scheme of splaying is called bottom-up splaying.
In top-down splaying, we start from the root and as we locate the target element and move down, we splay as we go. This is more efficient.

**Figure 4.17:** Zig rotation and zag rotation
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzigzag1.ps,width=5.5in}} \end{figure}$

**Figure 4.18:** Zig-zag rotation
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzigzag2.ps,width=5in}} \end{figure}$

**Figure 4.19:** Zag-zig rotation
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzagzig.ps,width=5in}} \end{figure}$

**Figure 4.20:** Zig-zig and zag-zag rotations
$\begin{figure} \par \centerline{\psfig{figure=figures/Fzigzag3.ps,width=5in}} \end{figure}$

**Figure 4.21:** Two successive right rotations
$\begin{figure} \par \centerline{\psfig{figure=figures/Fright2.ps,width=5in}} \end{figure}$

**Figure 4.22:** An example of splaying
$\begin{figure} \centerline{\psfig{figure=figures/Fsplay1.ps,width=5in}} \end{figure}$

4.5.1 Search, Insert, Delete in Bottom-up Splaying

Next: 4.5.1 Search, Insert, Delete in Bottom-up Splaying Up: 4. Binary Trees Previous: 4.4.1 Average Case Analysis of BST Operations

eEL,CSA_Dept,IISc,Bangalore