Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position. The task would be achieved this way, but the performance of the tree amortized over many accesses may not be good.
Rather, the key idea of splaying is to move the accessed node two levels up the tree at each step. Basic terminologies in this context are:
Zig: Movement of one step down the path to the left to fetch a node up. Zag: Movement of one step down the path to the right to fetch a node up.
With these two fundamental steps, the possible splay rotations are: Zig-Zig: Movement of two steps down to the left.
Zag-Zag: Movement of two steps down to the right. Zig-Zag: Movement of one step left and then right. Zag-Zig: Movement of one step right and then left.
Figure depicts the splay rotations.
Zig:
Zig-Zig:
Zig-Zag:
Splaying may be top-down or bottom-up. In bottom-up splaying, splaying begin at the accessed node, moving up the chain to root. While in top-down splaying, splaying begins from the top while searching for the node to access. In the next section, we would be discussing the top-down splaying procedure:
As top-down splaying proceeds, the tree is split into three parts:
a) Central SubTree: This is initially the complete tree and may contain the target node. Search proceeds by comparison of the target value with the root and ends with the root of the central tree being the node containing the target if present or null node if the target is not present.
b) Left SubTree: This is initially empty and is created as the central subtree is splayed. It consists of nodes with values less than the target being searched.
c) Right SubTree: This is also initially empty and is created similar to left subtree. It contains nodes with values more than the target node.