Splay Tree in Data Structure

Introduction

Welcome to Coding Ninjas; The Splay tree is one of the important topics in Binary Search Trees. In this article, we will discuss what is the splay tree in data structure, why there is a need for a splay tree, and how the operations in the splay tree work.

There is a prerequisite before starting with Splay Trees; understand Binary Search Trees and self-balancing binary search trees.

I’ll recommend you read more about binary search trees and a binary tree here. Also, you can have a look at what are the self-balancing binary search trees before looking at splay trees.

What is the Splay Tree data structure?

Splay Tree in Data Structure is a self-balancing (or self-adjusting) Binary Search Tree, and these are the roughly-balanced (not strictly balanced) Binary Search Trees.

All the operations in Splay Tree, such as Searching, Insertion, and Deletion, are the same as in the Binary Search Tree. But every operation is followed by one extra operation called splaying, which is used to balance (or adjust) the given binary search tree.

Splaying is an operation that places a particular node to a root node by rearrangements or rotations in the tree. So, the rotations will be performed on such particular nodes.

Need for Splay Tree

The average case & worst case time complexity of operations in the Binary Search Tree are O(log n) and O(n), respectively. Meaning that if the binary search tree is not skewed, then the time complexity will be O(log n), but if the tree is skewed (left or right), then the time complexity will be O(n).

This is one of the limitations of the binary search trees, and we have multiple solutions to reduce the time complexity. AVL and Red-Black Trees can be used as the solutions over binary search trees.

But if AVL and Red-Black Trees work as a solution, why use Splay Trees?

Splay Trees has a unique operation called splaying that differentiates it from AVL and Red-Black Trees. And Splay Trees are used when the frequently accessed nodes need to use again.

Rotations in Splay Tree

Here are some rotations in the splay tree.

1. Zig Rotation

2. Zag Rotation

3. Zig - Zig Rotation

4. Zag - Zag Rotation

5. Zig - Zag Rotation

6. Zag - Zig Rotation

Zig Rotation

Every node will move one position to the right in the tree while maintaining the conditions of the binary search tree. You can imagine the word ‘zig’ as right here.

Here’s an example showing zig rotation:

Here 10 is the node that was chosen to splay, and 10 places to the root after the right rotation is completed with satisfying all the conditions of the binary search tree.

Zag Rotation

Every node will move one position to the left in the tree while maintaining the conditions of the binary search tree. You can imagine the word ‘zag’ as left here.

Here’s an example showing zag rotation:

Here 60 is the node that was chosen to splay, and 60 places to the root after the left rotation is completed with satisfying all the conditions of the binary search tree.

Zig - Zig Rotation

Every node will move two positions to the right in the tree while maintaining the conditions of the binary search tree. You can imagine the word ‘zig - zig’ as right and right here.

Here’s an example showing zig-zig rotation:

Here 20 is the node that was chosen to splay, and 20 places to the root after the 2 right rotation is completed with satisfying all the conditions of the binary search tree.

Zag - Zag Rotation

Every node will move two positions to the left in the tree while maintaining the conditions of the binary search tree. You can imagine the word ‘zag - zag’ as left and left here.

Here’s an example showing zag-zag rotation:

Here 20 is the node that was chosen to splay, and 20 places to the root after the 2 left rotation is completed with satisfying all the conditions of the binary search tree.

Zig - Zag Rotation

Every node will move in one position, first to the right and then to the left in the tree while maintaining the conditions of the binary search tree. You can imagine the word ‘zig - zag’ as right and left here.

Here’s an example showing zig-zag rotation:

Here 40 is the node that was chosen to splay; first, its parent will be zig rotate, that is, 50, and second, its grand-parent will be zag rotate, that is, 20. And Zig-Zag Rotation is completed by satisfying all the conditions of the binary search tree.

Zag - Zig Rotation

Every node will move in one position, first to the left and then to the right in the tree while maintaining the conditions of the binary search tree. You can imagine the word ‘zig - zag’ as left and right here.

Here’s an example showing zag-zig rotation:

Here 15 is the node that was chosen to splay; first, its parent will be zag rotate, that is,10, and second, its grand-parent will be zig rotate, that is, 20. And Zag-Zig Rotation is completed by satisfying all the conditions of the binary search tree.

Operations in Splay Tree

Searching for an element

Searching an element in Splay Tree is similar to searching in the binary search tree. But there is an extra operation in a splay tree called splaying.

There are 2 steps for searching for an element in the splay tree:

we search for the given target element in the splay tree as in the binary search tree.
The aim is to place the searched element to the root by splaying.

Here’s an example showing searching in the splay tree:

In the above example, we had to search for 10 in the given tree, and we searched for 10 that were present in the tree at level 2. After searching the element, splaying is done on the element, and just by doing a zig rotation 10 places to the root and searching operation in the splay tree is done.

Inserting an element

Inserting an element in Splay Tree is similar to inserting in the binary search tree. But there is an extra operation in a splay tree called splaying.

There are 2 steps for inserting an element in the splay tree:

we insert the given element in the splay tree as in the binary search tree.
Now The aim is to place the inserted element to the root by splaying.

Here’s an example showing searching in the splay tree:

In the above example, we had to insert 10 in the given tree, and we inserted 10 were inserted in the tree at level 2. After searching the element, splaying is done on the element, and just by doing a zig rotation 10 places to the root, an insertion operation in the splay tree is done.

Deleting an element

Deleting an element in Splay Tree is similar to deleting in the binary search tree. But there is an extra operation in a splay tree called splaying.

There are 2 steps for inserting an element in the splay tree:

We delete the given element in the splay tree as in the binary search tree.
Now The aim is to place the parent of the deleted element to the root by splaying.

Here’s an example showing searching in the splay tree:

In the above example, we had to delete 15 in the given tree; as 15 is a leaf node, it can be deleted directly. After deleting the element, splaying is done on the parent of the deleted element, which is 10, and just by doing a zig rotation 10 places to the root, a deletion operation in the splay tree is done.

Implementation of Splay Trees

C++

#include <iostream>
using namespace std;

struct node
{
	int data;
	node *left, *right, *parent;
};

node *newnode(int data)
{
	node *ninja_node = new node;
	ninja_node->data = data;
	ninja_node->left = ninja_node->right = ninja_node->parent = nullptr;
	return ninja_node;
}

void splay(node *ninja_node)
{
	while (ninja_node->parent)
	{
		node *parent = ninja_node->parent;
		node *grandparent = parent->parent;
		if (!grandparent)
		{
			if (ninja_node == parent->left)
			{
				// Zig Rotation
				node *right = ninja_node->right;
				ninja_node->right = parent;
				parent->left = right;
			}
			else
			{
				// Zag Rotation
				node *left = ninja_node->left;
				ninja_node->left = parent;
				parent->right = left;
			}
			ninja_node->parent = nullptr;
			parent->parent = ninja_node;
		}
		else
		{
			if (ninja_node == parent->left && parent == grandparent->left)
			{
				// Zig-Zig rotation
				node *right = ninja_node->right;
				ninja_node->right = parent;
				parent->left = right;
				parent->parent = grandparent->parent;
				grandparent->parent = parent;
				if (parent->parent)
				{
					if (parent->parent->left == grandparent)
						parent->parent->left = parent;
					else
						parent->parent->right = parent;
				}
				ninja_node->parent = nullptr;
				parent->parent = ninja_node;
			}
			else if (ninja_node == parent->right && parent == grandparent->right)
			{
				// Zag-Zag rotation
				node *left = ninja_node->left;
				ninja_node->left = parent;
				parent->right = left;
				parent->parent = grandparent->parent;
				grandparent->parent = parent;
				if (parent->parent)
				{
					if (parent->parent->left == grandparent)
						parent->parent->left = parent;
					else
						parent->parent->right = parent;
				}
				ninja_node->parent = nullptr;
				parent->parent = ninja_node;
			}
			else
			{
				// Zig-Zag rotation
				if (ninja_node == parent->right)
				{
					node *left = ninja_node->left;
					ninja_node->left = parent;
					parent->right = left;
				}
				else
				{
					node *right = ninja_node->right;
					ninja_node->right = parent;
					parent->left = right;
				}
				grandparent->left = ninja_node;
				parent->parent = ninja_node;
				ninja_node->parent = grandparent;
			}
		}
	}
}

node *search(node *root, int data)
{
	if (!root)
		return nullptr;
	node *ninja_node = root;
	while (ninja_node)
	{
		if (ninja_node->data == data)
		{
			splay(ninja_node);
			return ninja_node;
		}
		else if (ninja_node->data < data)
		{
			if (!ninja_node->right)
			{
				splay(ninja_node);
				return nullptr;
			}
			ninja_node = ninja_node->right;
		}
		else
		{
			if (!ninja_node->left)
			{
				splay(ninja_node);
				return nullptr;
			}
			ninja_node = ninja_node->left;
		}
	}
}

node *insert(node *root, int data)
{
	if (!root)
		return newnode(data);
	node *ninja_node = root;
	while (ninja_node)
	{
		if (ninja_node->data == data)
		{
			splay(ninja_node);
			return ninja_node;
		}
		else if (ninja_node->data < data)
		{
			if (!ninja_node->right)
			{
				ninja_node->right = newnode(data);
				ninja_node->right->parent = ninja_node;
				splay(ninja_node->right);
				return ninja_node->right;
			}
			ninja_node = ninja_node->right;
		}
		else
		{
			if (!ninja_node->left)
			{
				ninja_node->left = newnode(data);
				ninja_node->left->parent = ninja_node;
				splay(ninja_node->left);
				return ninja_node->left;
			}
			ninja_node = ninja_node->left;
		}
	}
}

void deletenode(node *ninja_node)
{
	if (!ninja_node)
		return;
	if (!ninja_node->left && !ninja_node->right)
	{
		if (ninja_node->parent)
		{
			if (ninja_node->parent->left == ninja_node)
				ninja_node->parent->left = nullptr;
			else
				ninja_node->parent->right = nullptr;
			delete ninja_node;
		}
	}
	else if (!ninja_node->left)
	{
		if (ninja_node->parent)
		{
			if (ninja_node->parent->left == ninja_node)
				ninja_node->parent->left = ninja_node->right;
			else
				ninja_node->parent->right = ninja_node->right;
			ninja_node->right->parent = ninja_node->parent;
			delete ninja_node;
		}
		else
		{
			ninja_node->right->parent = nullptr;
			delete ninja_node;
		}
	}
	else if (!ninja_node->right)
	{
		if (ninja_node->parent)
		{
			if (ninja_node->parent->left == ninja_node)
				ninja_node->parent->left = ninja_node->left;
			else
				ninja_node->parent->right = ninja_node->left;
			ninja_node->left->parent = ninja_node->parent;
			delete ninja_node;
		}
		else
		{
			ninja_node->left->parent = nullptr;
			delete ninja_node;
		}
	}
	else
	{
		node *successor = ninja_node->right;
		while (successor->left)
		{
			successor = successor->left;
		}
		ninja_node->data = successor->data;
		deletenode(successor);
	}
}

int main()
{
	node *root = nullptr;

	root = insert(root, 10);
	root = insert(root, 20);
	root = insert(root, 30);
	root = insert(root, 40);
	root = insert(root, 50);
	root = insert(root, 60);

	node *searchResult = search(root, 80);
	if (searchResult)
		cout << "Searched for 40, found 40!" << endl;
	else
		cout << "Searched for 40, not found!" << endl;

	deletenode(search(root, 30));
	cout << "Deleted 30 from the splay tree!" << endl;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Searched for 40, could not find it!
Deleted 30 from the splay tree!

Complexities of Splay Trees

The Time Complexity of operations in a splay tree depends on the height of the tree. If the tree is skewed, the time complexity for all operations will be O(n) in the worst case. But, In most cases, splay trees balance the tree, so the time complexity will be O(log n) in best and average cases both.

The Time Complexity for Splaying a node to the root is O(log n). O(log n) is the worst-case time complexity for all the rotations such as Zig, Zag, Zig-Zig, Zag-Zag, Zig-Zag, Zag-Zig.

The splay trees only store the data of n nodes that take the space complexity of O(n) in the worst case.

Deletion in Splay tree

Deletion in a Splay tree involves removing a node while adjusting the tree structure for efficient access. The node to be deleted is splayed to the root, removed, and the tree is restructured as needed for balance. Splay trees maintain self-adjustment to optimize future data access.

Types of Deletions:

There are two types of deletions in the splay trees:

Bottom-up splaying
Top-down splaying

Bottom-up splaying

Bottom-up splaying is an operation in Splay trees where a node is moved to the root of the tree by repeatedly performing single or double rotations. This operation helps balance and optimize the tree, improving search and retrieval efficiency for the node.

Top-down splaying

Top-down splaying is an operation in Splay trees where a node is moved to the root of the tree by repeatedly performing rotations and restructuring the tree. This operation aims to optimize search and retrieval by bringing frequently accessed nodes closer to the root for faster access.

Advantages of Splay Trees

As splay trees are self-adjusting, means that the recently accessed element is placed at the root. So that these particular elements can be accessed faster in later operations.
Simple to implement as compared to other self-balancing trees.
Splay Trees require less memory as compared to other self-balancing trees.

Disadvantages of Splay Trees

Splay Trees do not guarantee an optimal balance, meaning trees can become unbalanced and have skewed shapes in some worst-case scenarios.
As the worst-case is critical, Splay Trees can not be used in real-life systems.

Frequently Asked Questions

What is another name for a splay tree?

Another name for a Splay tree is a "self-adjusting binary search tree." It's called so because it dynamically reorganizes itself for efficient data access.

What is the role of splay trees in searching?

Splay trees improve search efficiency by dynamically adjusting their structure, bringing frequently accessed nodes closer to the root, reducing search times for frequently queried elements.

Is an AVL tree a splay tree?

No, an AVL tree and a Splay tree are different types of self-balancing binary search trees with distinct balancing mechanisms.

What is the split operation of a splay tree?

The split operation in a Splay tree involves dividing the tree into two parts at a specified key, resulting in two separate Splay trees with elements less than and greater than the specified key.

How Splay Trees are different from Binary Search Trees?

Splay Trees is a variant of the binary search tree, and every operation works the same as the binary search tree and but the only difference is that every operation is followed by an operation called splaying that is used to balance the tree, which includes rotations.

You can also read about the topic - hash function in data structure

Conclusion

Splay Tree in Data Structure is a type of self-balancing binary search tree. Splay Tree is one of the variants of binary search trees. You can check out this if you want to read more about the self-balancing binary search tree. Splaying is the extra operation that is used in splay trees for balancing or adjusting. We discussed what the need for a splay tree is, what a splay tree is, its rotations, and operations in the splay tree. I hope you understood everything about splay trees.

Do check out The Interview Guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc., on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.