Last Updated on June 6, 2023 by Mayank Dham
Binary Search Trees (BSTs) are fundamental data structures that allow efficient searching, insertion, and deletion operations. They follow a specific property where values in the left subtree of a node are smaller than the value in that node, and values in the right subtree are greater. However, traditional BSTs can become unbalanced, leading to degraded performance. Splay trees offer a solution to this problem by automatically adapting their structure based on the access pattern of elements. They bring frequently accessed nodes closer to the root through a process called splaying. In this article, we will explore the concept of splay trees, their rotations, and the advantages and disadvantages they offer.
What are Binary Search Trees?
Binary Search Trees (BSTs) are also binary trees i.e. the maximum number of child nodes of any node is 2. A binary search tree has one special property that makes it very efficient for searching purposes and hence it gets its name i.e. Binary Search Tree. The property states that all the values in the left subtree of a node will be smaller than the value in that node and all the values in the right subtree of any node will be greater than the value inside that node. Consider the binary search tree shown below.
The values in the left subtree of the root node are smaller than 10 and the values in the right subtree of the root node are greater than 10. The condition of the left subtree containing smaller values and the right subtree containing larger values is not just true for the root node, rather it is true for every node of the binary search tree.
The node structure of a binary tree and BST is exactly the same as a BST is also a binary tree only. This is shown below.
What is a Splay Tree in Data Structure?
When we use BSTs for searching the data, the time complexity in an average case is O(log2N). This is because the average case height of a binary tree is O(log2N). However, the worst case can be a left or a right-skewed tree i.e. a linear tree. Then the worst-case time complexity of the operations like searching, insertion, and deletion becomes O(N).
However, what if the trees are made self-balancing such that they never form skewed structures and the height always remains O(log2N)? This is done in AVL trees and Red-Black trees. These are self-balancing BSTs; hence, the worst-case time complexity of searching, insertion and deletion is O(log2N).
However, the question is, can we do better than this? The answer is yes. In some practical scenarios, we can do better than AVL and Red-Black Trees. How? Using splay trees.
The main idea of splay trees is based on the “most frequently used elements”. Basically, a splay tree in data structure, involves all the operations of a normal Binary Search Tree i.e. searching, insertion, deletion, etc. However, it also includes one special operation i.e. always performed and it is called splaying. The idea is to bring the more frequently used elements closer to the root of the BST so that if they are searched again, they can be found more quickly as compared to the less frequently used elements.
Consider the BST shown below.
Let us say we want to search for 8. So, we start from the root node. Since the value at the root node is 10 and we are searching for 8 i.e. a smaller element than the current node, we will move toward the left. So, we go to the next node and we found 8. This is a normal search operation in BST. However, we will do a little more than this in the splay tree. We will perform splaying i.e. 8 will now become the root node of the tree. How? We can do this with some rotations. There are 6 different types of rotations that can be performed in a splay tree. These are as follows.
- Zig Rotation (Right Rotation)
- Zig Zig Rotation (2 Zig Rotations or 2 right rotations)
- Zag Rotation (Left Rotation)
- Zag Zag Rotation (2 Zag rotations or 2 left rotations)
- Zig Zag Rotation (Right-Left Rotation i.e. first do Zig then Zag)
- Zag Zig Rotation (Left-Right Rotation i.e. first do Zag then Zig)
Let us study these rotations one by one.
Zig Rotation or Right Rotation
Consider the tree shown below.
In this rotation, we move every node to 1 position towards its right. This rotation is used in the case when the element that we are searching for is either present in the root node of the BST or it is present in the left child of the root node.
Consider that we are searching for node 9. This means that we are searching for the left child of the root node. So, we can perform zig rotation.
So, the steps for searching node 9 are the same as we perform the search in BST and have already been discussed. Now, since this is the zig rotation i.e. we need to rotate each element 1 position to its right. This rotation is shown below.
So, every element has to go 1 position to its right. Now, we can imagine every element going to 1 position to its right and we imagine that 9 will become the root node and 11 will; be its right child and the left child will be 7. What about node 10?
So, node 10 is the right child of node 9 before rotation. So, after rotation, it will remain in the right subtree of node 9. However, it will now become the left child of node 11 as shown below.
Zig Zig Rotation or Right-Right Rotation
In this rotation, 2 right rotations are performed one after another. This is used in the case when the element that we are searching for is neither the root node nor the left child of the root node but is present below in the left subtree of the root node. This means that the node has both, parent and grandparent. Consider the tree shown below.
So, if we are searching for node 3, we find it at the last level. Now, we will perform the 1st right rotation.
After one rotation, the tree is shown below. Now, we perform the second rotation.
So, after 2 right rotations, node 3 is now the root node of the tree.
Zag Rotation or Left Rotation
Again, consider the tree shown below.
The Zag rotation or the left rotation is performed when the element that we are searching for is either the root node or the right child of the root node.
So, consider that we are searching for node 13. Since it is the right child of the root node, we perform the zig rotation. Every element will rotate and reach 1 position to its current left. This is shown below.
So, since after rotation, 14 has to become the right child of 13 and 12 was present as its left child, 12 will remain in the left subtree but becomes the right child of node 11. Node 13 has become the root node now.
Zag Zag Rotation or Left-Left Rotation
Here, we perform 2 left rotations. Again, it is done when we are searching for an element i.e., not the root or the right child of the root but present in the right subtree and has both parent and grandparent. So, consider the tree shown below.
If we are searching 7, the result of the zag zag rotation is shown below.
So, node 7 has now become the root node of the tree.
Zig Zag Rotation or Right Left Rotation
This is a sequence of zig rotations which are then followed by a sequence of zag rotations. The zig-zag rotation is used when the parent node and the grandparent node of a node are in LR or RL relationship with each other. Consider the tree shown below.
If we want to search 5, then the parent and grandparent are in an RL relationship with each other. So, we first perform the Right rotation i.e. Zig rotation about node 6, and then the left rotation i.e. Zag rotation about the root node i.e. node 4, thus completing the Zig Zag rotation. This is shown below.
Finally, we can see that 5 is the root node of the tree. So, this is Zig Zag rotation.
Zag Zig Rotation or Left-Right Rotation
This rotation is the same as the zig-zag rotation. The only difference is that the left rotation happens first and then the right rotation. Consider the tree shown below.
So, here if we want to search 5, the zag zig rotation is shown below.
So, we can see that node 5 is at the root of the tree. This is Zag Zig Rotation.
Now that we have studied the splay trees, let us implement these rotations and other BST operations of a splay tree in the program shown below.
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int key;
node *left, *right;
};
node *TreeNode(int key)
{
node *Node = new node();
Node->key = key;
Node->left = Node->right = NULL;
return (Node);
}
node *rightRotate(node *x)
{
node *y = x->left;
x->left = y->right;
y->right = x;
return y;
}
node *leftRotate(node *x)
{
node *y = x->right;
x->right = y->left;
y->left = x;
return y;
}
node *splay(node *root, int key)
{
if (root == NULL || root->key == key)
return root;
if (root->key > key)
{
if (root->left == NULL)
return root;
// Zig-Zig Rotation
if (root->left->key > key)
{
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
else if (root->left->key < key) // Zig-Zag
{
root->left->right = splay(root->left->right, key);
if (root->left->right != NULL)
root->left = leftRotate(root->left);
}
return (root->left == NULL) ? root : rightRotate(root);
}
else
{
if (root->right == NULL)
return root;
// Zag-Zig Rotation
if (root->right->key > key)
{
root->right->left = splay(root->right->left, key);
if (root->right->left != NULL)
root->right = rightRotate(root->right);
}
else if (root->right->key < key)
{
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
return (root->right == NULL) ? root : leftRotate(root);
}
}
node *bstSearch(node *root, int key)
{
return splay(root, key);
}
void preOrder(node *root)
{
if (root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
node *root = TreeNode(100);
root->left = TreeNode(50);
root->right = TreeNode(200);
root->left->left = TreeNode(40);
root->left->left->left = TreeNode(30);
root->left->left->left->left = TreeNode(20);
root = bstSearch(root, 20);
preOrder(root);
return 0;
} class Tree
{
static class node
{
int key;
node left, right;
};
static node TreeNode(int key)
{
node Node = new node();
Node.key = key;
Node.left = Node.right = null;
return (Node);
}
static node rightRotate(node x)
{
node y = x.left;
x.left = y.right;
y.right = x;
return y;
}
static node leftRotate(node x)
{
node y = x.right;
x.right = y.left;
y.left = x;
return y;
}
static node splay(node root, int key)
{
if (root == null || root.key == key)
return root;
if (root.key > key)
{
if (root.left == null) return root;
if (root.left.key > key)
{
root.left.left = splay(root.left.left, key);
root = rightRotate(root);
}
// Zig-Zag
else if (root.left.key < key)
{
root.left.right = splay(root.left.right, key);
if (root.left.right != null)
root.left = leftRotate(root.left);
}
return (root.left == null) ? root : rightRotate(root);
}
else
{
if (root.right == null) return root;
if (root.right.key > key)
{
root.right.left = splay(root.right.left, key);
if (root.right.left != null)
root.right = rightRotate(root.right);
}
// Zag-Zag
else if (root.right.key < key)
{
root.right.right = splay(root.right.right, key);
root = leftRotate(root);
}
return (root.right == null) ? root : leftRotate(root);
}
}
static node bstSearch(node root, int key)
{
return splay(root, key);
}
static void preOrder(node root)
{
if (root != null)
{
System.out.print(root.key + " ");
preOrder(root.left);
preOrder(root.right);
}
}
}
public class Main {
public static void main(String[] args)
{
Tree.node root = Tree.TreeNode(100);
root.left = Tree.TreeNode(50);
root.right = Tree.TreeNode(200);
root.left.left = Tree.TreeNode(40);
root.left.left.left = Tree.TreeNode(30);
root.left.left.left.left = Tree.TreeNode(20);
root = Tree.bstSearch(root, 20);
Tree.preOrder(root);
}
} class TreeNode:
def __init__(self, data):
self.data = data
self.parent = None
self.left = None
self.right = None
class SplayTree:
def __init__(self):
self.root = None
def leftRotate(self, x):
y = x.right
x.right = y.left
if y.left != None:
y.left.parent = x
y.parent = x.parent
# x is root
if x.parent == None:
self.root = y
# x is left child
elif x == x.parent.left:
x.parent.left = y
# x is right child
else:
x.parent.right = y
y.left = x
x.parent = y
def rightRotate(self, x):
y = x.left
x.left = y.right
if y.right != None:
y.right.parent = x
y.parent = x.parent
# x is root
if x.parent == None:
self.root = y
# x is right child
elif x == x.parent.right:
x.parent.right = y
# x is left child
else:
x.parent.left = y
y.right = x
x.parent = y
def splay(self, n):
# node is not root
while n.parent != None:
# node is child of root, one rotation
if n.parent == self.root:
if n == n.parent.left:
self.rightRotate(n.parent)
else:
self.leftRotate(n.parent)
else:
p = n.parent
g = p.parent # grandparent
if n.parent.left == n and p.parent.left == p: # both are left children
self.rightRotate(g)
self.rightRotate(p)
elif n.parent.right == n and p.parent.right == p: # both are right children
self.leftRotate(g)
self.leftRotate(p)
elif n.parent.right == n and p.parent.left == p:
self.leftRotate(p)
self.rightRotate(g)
elif n.parent.left == n and p.parent.right == p:
self.rightRotate(p)
self.leftRotate(g)
def insert(self, n):
y = None
temp = self.root
while temp != None:
y = temp
if n.data < temp.data:
temp = temp.left
else:
temp = temp.right
n.parent = y
if y == None: # newly added node is root
self.root = n
elif n.data < y.data:
y.left = n
else:
y.right = n
self.splay(n)
def bstSearch(self, n, x):
if x == n.data:
self.splay(n)
return n
elif x < n.data:
return self.bstSearch(n.left, x)
elif x > n.data:
return self.bstSearch(n.right, x)
else:
return None
def preOrder(self, n):
if n != None:
print(n.data)
self.preOrder(n.left)
self.preOrder(n.right)
if __name__ == '__main__':
tree = SplayTree()
a = TreeNode(10)
b = TreeNode(20)
c = TreeNode(30)
d = TreeNode(100)
e = TreeNode(90)
f = TreeNode(40)
g = TreeNode(50)
tree.insert(a)
tree.insert(b)
tree.insert(c)
tree.insert(d)
tree.insert(e)
tree.insert(f)
tree.insert(g)
tree.bstSearch(tree.root, 90)
tree.preOrder(tree.root)
Conclusion
So, we have talked about the Splay tree in data structure and its various rotations and advantages and disadvantages. We hope that you liked the discussion and understood the concept completely. We hope to see you again soon at PrepBytes.
So, this was all about the Splay Tree in Data Structure. Let us now discuss some Frequently Asked Questions (FAQs).
Frequently Asked Questions (FAQs)
1. What are some advantages of a Splay Tree in Data Structure?
We do not need to store any extra information when we talk about the splay tree. Basically, a splay tree is a self-balancing BST. There are other self-balancing BSTs like AVL tree and Red Black Tree. However, in the AVL tree, we need to store the balance factor of each node and in the Red Black Tree, we need one extra bit for storing the color of the node i.e. red or black. In a splay tree, however, we do not need to store any such information.
2. What is the disadvantage of a Splay Tree in Data Structure?
The main disadvantage of the Splay Tree is that these trees, unlike the AVL tree are roughly balanced just like Red-Black trees. So, sometimes they can be linear i.e. skewed, and then the time complexity will be O(N).
3. Is there any practical use of Splay Tree?
Splay trees are practically the fastest BSTs used. They are even used in GCC compilers.
Advantages and disadvantages of splay tree
1. Efficient Access Patterns: Splay trees adapt to the access pattern of elements, bringing frequently accessed nodes closer to the root. This results in faster access times for frequently accessed elements.
2. Self-Adjusting: Splay trees automatically adjust their structure based on the recent access history, which helps maintain a balanced tree. This adaptability allows them to handle dynamic or changing data sets effectively.
3. Simple Implementation: The basic operations of splay trees, such as insert, delete, and search, can be implemented using simple rules, making the implementation relatively straightforward compared to other balanced search tree structures.
Disadvantages of Splay Trees:
1. Lack of Strict Balance: Unlike other balanced search tree structures like AVL or Red-Black trees, splay trees do not guarantee strict balance. In certain cases, they may become skewed, leading to worst-case time complexity for operations.
2. Amortized Time Complexity: While the average time complexity of operations in a splay tree is good, the worst-case time complexity is higher compared to other balanced tree structures. In rare cases, a sequence of operations can result in a degraded structure and increase the time complexity.
3. Increased Variance in Performance: Due to the self-adjusting nature of splay trees, the performance can vary depending on the access pattern. In some cases, if the access pattern is not favorable, the tree may not provide significant performance improvements over simpler data structures.
It’s important to consider these advantages and disadvantages of splay tree while evaluating whether a splay tree is suitable for a specific use case. The choice of data structure should depend on the specific requirements and characteristics of the application or problem at hand.
Conclusion
Conclusion
So, we have talked about the Splay tree in data structure and its various rotations and advantages and disadvantages. We hope that you liked the discussion and understood the concept completely. We hope to see you again soon at PrepBytes. So, this was all about the Splay Tree in Data Structure. Let us now discuss some Frequently Asked Questions (FAQs).
Frequently Asked Questions (FAQs)
Q1. What are some advantages of a Splay Tree in Data Structure?
We do not need to store any extra information when we talk about the splay tree. Basically, a splay tree is a self-balancing BST. There are other self-balancing BSTs like AVL tree and Red Black Tree. However, in the AVL tree, we need to store the balance factor of each node and in the Red Black Tree, we need one extra bit for storing the color of the node i.e. red or black. In a splay tree, however, we do not need to store any such information.
Q2. What is the disadvantage of a Splay Tree in Data Structure?
The main disadvantage of the Splay Tree is that these trees, unlike the AVL tree are roughly balanced just like Red-Black trees. So, sometimes they can be linear i.e. skewed, and then the time complexity will be O(N).
Q3. Is there any practical use of Splay Tree?
Splay trees are practically the fastest BSTs used. They are even used in GCC compilers.