Splay Tree

Introduction to Splay Tree

As we know, the worst-case time complexity of operations like search, delete, and insert on a binary search tree is O(n), while the average time complexity is O(logn). The value of the left subtree in a binary search tree is smaller than the value of the root node, and the value of the right subtree is greater than the value of the root node. The time complexity, in this case, would be O(logn), and if we tried to skew left or right, the time complexity would be O(logn). We can reduce skewness by using AVL and Red-Black trees and can reduce complexity to O(logn).

But, can we do better than this?

The answer is YES. But how?

Here comes the concept of "Splay Tree".

What is Splay Tree?

Have you ever thought that AVL and Red-Black trees are also self-adjusted trees? Then, what makes the Splay Tree different from the AVL and Red-Black trees? Yes, there is one operation called splaying, which makes it different from both AVL and the Red-Black Tree.

A splay tree contains all the operations of a binary search tree, like insertion, deletion, and searching. But it also contains one more operation, which is called splaying. In a splay tree, every operation is performed at the root of the tree. All operations in the splay tree involve one common operation called splaying.

You may have questioned what splaying is and why it differentiates splay trees from AVL and Red-Black trees. So, let me tell you about splaying. Splaying is the process of bringing an element to the root by performing suitable rotations.

By splaying elements in the tree, we can bring more frequently used elements closer to the root of the tree so that any operations like insertion, searching, and deletion can be performed quickly. This means, that after applying the splaying operation, more frequently used elements come closer to the root.

Suppose we have been given a binary search tree with different nodes and we know that in the binary search tree, elements to the left are smaller and those to the right are greater than the root node.

For searching, we will perform the binary search method. Let’s say we want to search for element 9. As 9 is less than 11, we will come to the left of the root node. After performing a search operation, we need to do one thing called splaying. This means, that after splaying, the element on which we are operating should come to the root. Elements would come to the root after performing some rearrangements of elements or rotations in the tree.

Rotations in Splay Tree

To rearrange the tree, we need to perform some rotations. The rotations given below are the rotations that we are going to perform in the splay tree.

• Zig rotation [Right Rotation]
• Zig zig [Two Right Rotations]
• Zag rotation [Left Rotation]
• Zag zag [Two Left Rotations]
• Zig zag [Zig followed by Zag]
• Zag zig [Zag followed by Zig]

Zig rotation:

This rotation is similar to the right rotation in the AVL tree. In zig rotation, every node moves one position to the right of its current position. We use Zig rotation when the item which is to be searched is either a root node or a left child of the root node.

Let’s take a scenario where the search item is the left child of the root node.

In the above example, we have to search for node 9 in the tree. To search for the given node in the binary search tree, we need to perform the following steps:

Step 1: First, we compare 9 with the root node. As 9 is less than 11, it is a left child of the root node.

Step 2: We have already seen above that once the element is found, we will perform splaying. Here the right rotation is performed so that 9 becomes the root node of the tree. Have a look at the diagram below.

In the above diagram, we can see that node 9 has become the root node of the tree, this shows that the searching is completed.

Zig zig rotation:

It’s a kind of double zig rotation. Here we perform zig rotation two times. Every node moves two positions to the right of its current position. But why are we doing this?

We are doing this because sometimes situations arise where we need to search for the item that has both parent and grandparent. In such cases, we have to perform four rotations for splaying.

In the example given below, suppose we have to search for element 3.

Step 1: First, we have to perform a search operation in the tree as we did previously, which means a BST operation. As 3 is less than 6 and 4, it will be at the left of node 4. So we can say that element 3 has a parent of 4 and a grandparent of 6.

Step 2: We have to perform splaying, which means we have to make node 3 the root node. So here we will perform two right rotations because the elements to be searched have both parent and grandparent.

In the above diagram, we can see that node 3 has become the root node of the tree, this shows that the searching is completed.

Zag rotation:

This rotation is similar to the left rotation in the AVL tree. In zag rotation, every node moves one position to the left of its current position. We use Zag rotation when the item which is to be searched is either a root node or a right child of the root node.

Let’s see the case where the element to be searched for is present on the right of the root node of the tree. Now let’s say we have to search for 13, which is present on the right of the root node of the tree.

The steps involved in searching are given below:

Step 1: First, we compare 13 with the root node. As 13 is greater than the root node of the tree, it is the right child of the root node.

Step 2: Once the element is found, we will perform splaying as we did in the previous examples. Here we will perform a left rotation so that 13 becomes the root node of the tree.

In the above diagram, we can see that node 13 has become the root node of the tree, this shows that the searching is completed.

Zag Zag Rotation:

It’s a kind of double zag rotation. Here we perform zag rotation two times. Every node moves two positions to the left of its current position. But why are we doing this?

We are doing this because sometimes situations arise where we need to search for the item that has both parent and grandparent. In such cases, we have to perform four rotations for splaying.

Now we will try to understand this case with some examples:

In the example given below, suppose we have to search for element 7.

Step 1: First, we have to perform a search operation in the tree as we did previously, which means a BST operation. As 7 is greater than 4 and 6, it will be at the right of node 6. So we can say that element 7 has a parent of 6 and a grandparent of 4.

Step 2: We have to perform splaying, which means we have to make node 7 the root node. So here we will perform two left rotations because the elements to be searched have both parent and grandparent.

In the above diagram, we can see that node 7 has become the root node of the tree, this shows that the searching is completed.

Zig Zag rotation

This type of rotation is a sequence of zig rotations followed by zag rotations. So far, we've seen that both the parent and the grandparent are in a RR or LL relationship. Now, here we will see the RL and LR kinds of relationships between parent and grandparent. Every node moves one position to the right, followed by one position to the left of its current position.

Suppose we want to search for element 5. Here first we perform a BST searching operation. Like 5, it is greater than the root node 4 and smaller than the node 6. So 5 would be the left child of node 6.

So an RL relationship exists since node 5 is to the left of node 6 and node 6 is to the right of node 4. So first we will perform the right rotation on node 6, and then node 6 will move downwards, and node 5 will come upwards, as you can see in the example given below. After that, we will perform zag rotation(left rotation) at 4, and we will see that 5 will become the root node of the tree.

As we can observe in the above tree, node 5 has become the root node; therefore, the search is completed. In this case, first, we have performed the zig rotation and then the zag rotation. So it is known as zig-zag rotation.

Zag Zig Rotation

This rotation is similar to the Zig-zag rotation, the only difference is that here every node moves one position to the left, followed by one position to the right of its current position.

Suppose we want to search for element 5. Here first we perform a BST searching operation. Like 5, it is smaller than the root node 6 and greater than node 4. So 5 would be the right child of node 4, and 4 would be the left child of the root node 6.

So here $LR$ relationship exists since node 5 is to the right of node 4 and node 4 is to the left of node 6. So first we will perform the left rotation on node 4, and then node 4 will move downwards, and node 5 will come upwards, as you can see in the example given below. And after that, we will perform one zig rotation (right rotation) at 6, so finally, we will get 5 as the root node of the tree.

As we can observe in the above tree, node 5 has become the root node; therefore, the searching is completed. In this case, first, we have performed the zag rotation and then the zig rotation. So it is known as zag-zig rotation.

Advantages of Splay Tree

• In the AVL and Red-Black trees, we need to store some information. Like in AVL trees, we need to store the balance factor of each node, and in the red-black trees, we also need to store one extra bit of information that denotes the color of the node, either black or red.
• Splay tree is the fastest type of binary search tree, which is used in a variety of practical applications such as GCC compilers.
• Improve searching by moving frequently accessed nodes closer to the root node. One of the practical uses is cache implementation, in which recently used data is saved in the cache so that we can access the data more quickly without going into memory.

Disadvantages of Splay Tree

The main disadvantage of the splay tree is that trees are not strictly balanced, but rather roughly balanced. When the splay trees are linear, the time complexity is O(n).

Implementation of Splay Tree

C

C++

Java

Python

See also

Binary Search Tree (BSTs)