Insertion in Splay Tree in C++
Today, we will describe an important DSA topic: Insertion in Splay Tree. First, we will introduce what the Splay tree is and how it works to insert an element in the Splay tree.
What is Splay Tree?
The splay tree is a self-arranged Binary Search tree (BST). In which each operation on elements rearranges the tree through that element of the tree would be placed at the root of the tree. This method was invented by Sleator and Tarjan. It is similar to the AVL Tree (Red-Black Tree) the structure of the Splay tree changes after doing any operations on it. Now, move ahead to know the need for this Splay Tree.
Why We Need Splay Tree?
There are two cases in the Binary Search Tree, which are average case and worst-case time complexity. The average case is denoted as O(log n), and O(n) is denoted as worst-case. It means that when a binary search is not skewed at that time, the time complexity will be denoted as O(log n), and if the tree is skewed right or left, then the time complexity will be O(n).
It is the limitation in the binary search tree. As a solution, there are AVL and Red-Black methods over binary search trees. But the question is, if these two options are available, then why is there a need for Splay Tree? Splay comes up with a unique feature known as Splaying, which denotes some differences from AVL and Red-Black trees. Another reason is when we need frequently accessed nodes to use again, we use Splay Trees. Here is an explanation of the insertion operation on the Splay Tree.
Insertion Operation
Using the binary search insertion method to insert a node x. After that, we splay x and move it to the root of the tree. Here is the Algo:
Insert(T, n)
Temp = T ->root
Y= NULL
While (temp != null
Y = temp)
If( n->data < temp->data
Temp = temp->left)
Else{
Temp = temp->right
}
N.Parent = Y
If (Y == NULL)
{
T->root = n
Else if
{
n->data < y->data
y->left = n
Else y->right = n
See the below code in C++ for implementing the Splay Tree:
#include <bits/stdc++.h>
using namespace std;
class nodes
{
public:
int keys;
nodes *lt, *rt;
};
nodes* newNode(int keys)
{
nodes* Node = new nodes();
Node->keys = keys;
Node->lt = Node->rt = NULL;
return (Node);
}
nodes *rightRotate(nodes *x)
{
nodes *y = x->lt;
x->lt = y->rt;
y->rt = x;
return y;
}
nodes *leftRotate(nodes *x)
{
nodes *y = x->rt;
x->rt = y->lt;
y->lt = x;
return y;
}
nodes *splay(nodes *root, int keys)
{
if (root == NULL || root->keys == keys)
return root;
if (root->keys > keys)
{
if (root->lt == NULL) return root;
if (root->lt->keys > keys)
{
root->lt->lt = splay(root->lt->lt, keys);
root = rightRotate(root);
}
else if (root->lt->keys < keys) // Zig-Zag (Left Right)
{
root->lt->rt = splay(root->lt->rt, keys);
if (root->lt->rt != NULL)
root->lt = leftRotate(root->lt);
}
return (root->lt == NULL)? root: rightRotate(root);
}
else
{
if (root->rt == NULL) return root;
if (root->rt->keys > keys)
{
root->rt->lt = splay(root->rt->lt, keys);
if (root->rt->lt != NULL)
root->rt = rightRotate(root->rt);
}
else if (root->rt->keys < keys)
{
root->rt->rt = splay(root->rt->rt, keys);
root = leftRotate(root);
}
return (root->rt == NULL)? root: leftRotate(root);
}
}
nodes *insert(nodes *root, int k)
{
if (root == NULL) return newNode(k);
root = splay(root, k);
if (root->keys == k) return root;
nodes *newnode = newNode(k);
if (root->keys > k)
{
newnode->rt = root;
newnode->lt = root->lt;
root->lt = NULL;
}
else
{
newnode->lt = root;
newnode->rt = root->rt;
root->rt = NULL;
}
return newnode; // newnode becomes new root
}
void preOrder(nodes *root)
{
if (root != NULL)
{
cout<<root->keys<<" ";
preOrder(root->lt);
preOrder(root->rt);
}
}
int main()
{
nodes *root = newNode(100);
root->lt = newNode(50);
root->rt = newNode(200);
root->lt->lt = newNode(40);
root->lt->lt->lt = newNode(30);
root->lt->lt->lt->lt = newNode(20);
root = insert(root, 25);
cout<<"Preorder traversal of the modified Splay trees are \n";
preOrder(root);
return 0;
}
Output:
After successfully executing the Splay Tree program, let's move further, where we will see other different operations on the Splay Tree.
Search Operation
Searching in the binary search tree is comparable to searching for an element in the Splay Tree. However, splaying is an additional process in a splay tree. Searching for an element in the splay tree involves two steps:
- Similar to the binary search tree, we look for the specified target element in the splay tree.
- The objective is to splay the searching element to the root.
An illustration of searching in the splay tree is provided here:
Delete Operation
In the Splay Tree, removing an element is comparable to doing the same in the binary search tree. But, splaying is an additional process in a splay tree. Inserting an element into the splay tree requires two steps:
- Just like in the binary search tree, we remove the specified node from the splay tree.
- The goal now is to use splaying to move the parent of the removed element to the root.
An illustration of deleting a node from the splay tree is provided here:
Now, let's see what are the advantages and disadvantages of Splay Tree. Here, we have pointed out them briefly.
Advantages of Using Splay Tree
- As we know, splay trees adjust themselves, and the most recently accessed element is positioned at the root.
- For these specific elements to be fetched more quickly during subsequent operations.
- Compared to other self-balancing trees, this one is easy to implement.
- Memory requirements for Splay Trees are lower than those of other self-balancing trees.
Drawbacks of Splay Tree
- It does not ensure an ideal balance; in certain worst-case situations, trees may become unbalanced and exhibit skewed shapes.
- We can't use Splay Trees in real-world systems because the worst-case scenario is too serious.