Data Structures and Algorithms are an essential part of programming. Understanding the different data structures and algorithms, and how to use them, is essential to becoming an effective programmer. In this article, we will be discussing Splay Trees, a type of self-balancing tree data structure, and how to implement them in C++. We will discuss the structure of the tree, its time and space complexities, and provide some code examples.
What is a Splay Tree?
A Splay Tree is a self-balancing binary search tree. It was first introduced by Daniel Sleator and Robert Tarjan in 1985 and is an efficient data structure for fast retrieval, insertion, and deletion. Splay Trees use the splay operation, which is a modification of the standard binary tree operations. The splay operation reorganizes the tree so that the recently accessed elements are faster to access again.
Splay Trees are a type of self-balancing tree, which means they keep the tree balanced after each operation. This helps to ensure the tree remains balanced and efficient.
How Does the Tree Structure Work?
A Splay Tree is a binary search tree, which means that each node in the tree has a left and right child. The root node of the tree is the entry point. Each node in the tree holds a data value. The tree is structured such that the left child of a node contains a data value that is smaller than or equal to the parent node, and the right child of a node contains a data value that is larger than or equal to the parent node.
The splay operation works by reorganizing the tree after each operation. When an element is accessed, the tree is modified such that the recently accessed element becomes the root of the tree. This makes it easier to access again.
Time Complexity
Splay Trees have an average time complexity of O(log n) for access, search, insertion, and deletion. This means that the time to complete an operation is proportional to the logarithm of the number of elements in the tree.
The worst-case time complexity of Splay Trees is also O(log n). This means that even in the worst case, the time to complete an operation is proportional to the logarithm of the number of elements in the tree.
Space Complexity
The space complexity of Splay Trees is O(n). This means that the amount of memory used by the tree is proportional to the number of elements in the tree.
Implementing Splay Trees in C++
Now that we have discussed the structure of Splay Trees and their time and space complexities, let’s look at how to implement them in C++.
First, we must define the structure of the Splay Tree node. This will store the data value and the pointers to the left and right child nodes.
struct Node {
int data;
Node *left;
Node *right;
};
Next, we must define the structure of the Splay Tree. This will store the root node of the tree and the number of elements in the tree.
struct SplayTree {
Node *root;
int size;
};
Now, we must define the operations that can be performed on the Splay Tree. These operations include insertion, search, deletion, and splay.
Insertion
The insertion operation adds a new element to the Splay Tree. It takes the data value to be inserted and the root node of the tree as parameters.
// Function to insert a node in the Splay Tree
void insert(int data, Node *&root)
{
// Create a new node
Node *newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
// If the tree is empty, make the new node the root
if (root == NULL)
{
root = newNode;
return;
}
// Start at the root node
Node *curr = root;
// Traverse the tree to find the correct position for the new node
while (true)
{
if (data < curr->data)
{
// Go left
if (curr->left == NULL)
{
curr->left = newNode;
break;
}
else
{
curr = curr->left;
}
}
else
{
// Go right
if (curr->right == NULL)
{
curr->right = newNode;
break;
}
else
{
curr = curr->right;
}
}
}
// Perform the splay operation
splay(data, root);
}
Search
The search operation searches the Splay Tree for a given data value. It takes the data value to be searched for and the root node of the tree as parameters.
// Function to search for a node in the Splay Tree
Node *search(int data, Node *&root)
{
// Start at the root node
Node *curr = root;
// Traverse the tree to find the node
while (curr != NULL)
{
if (data == curr->data)
{
// Perform the splay operation
splay(data, root);
return curr;
}
else if (data < curr->data)
{
// Go left
curr = curr->left;
}
else
{
// Go right
curr = curr->right;
}
}
// If the node is not found, return NULL
return NULL;
}
Deletion
The deletion operation deletes a node from the Splay Tree. It takes the data value to be deleted and the root node of the tree as parameters.
// Function to delete a node from the Splay Tree
void deleteNode(int data, Node *&root)
{
// If the tree is empty, there is nothing to delete
if (root == NULL)
{
return;
}
// Search for the node to be deleted
Node *nodeToDelete = search(data, root);
if (nodeToDelete != NULL)
{
// If the node has no children, just delete it
if (nodeToDelete->left == NULL && nodeToDelete->right == NULL)
{
delete nodeToDelete;
nodeToDelete = NULL;
root = NULL;
}
else
{
// Find the inorder successor of the node
Node *inorderSuccessor = findInorderSuccessor(nodeToDelete);
// Copy the data of the inorder successor to the node to be deleted
nodeToDelete->data = inorderSuccessor->data;
// Delete the inorder successor
delete inorderSuccessor;
inorderSuccessor = NULL;
}
}
}
Splay
The splay operation reorganizes the tree after each operation. It takes the data value of the node to be splayed and the root node of the tree as parameters.
// Function to perform the splay operation
void splay(int data, Node *&root)
{
// If the tree is empty, there is nothing to splay
if (root == NULL)
{
return;
}
// Create two auxiliary trees
Node *leftTreeMax = NULL;
Node *rightTreeMin = NULL;
// Start at the root node
Node *curr = root;
while (true)
{
if (data < curr->data)
{
// Go left
if (curr->left == NULL)
{
break;
}
if (data < curr->left->data)
{
// Zig-Zig (Left Left)
rotateRight(curr);
if (curr->left == NULL)
{
break;
}
}
// Link Right
if (rightTreeMin == NULL)
{
rightTreeMin = curr;
}
else
{
rightTreeMin->right = curr;
}
curr = curr->left;
}
else if (data > curr->data)
{
// Go right
if (curr->right == NULL)
{
break;
}
if (data > curr->right->data)
{
// Zig-Zag (Right Left)
rotateLeft(curr);
if (curr->right == NULL)
{
break;
}
}
// Link Left
if (leftTreeMax == NULL)
{
leftTreeMax = curr;
}
else
{
leftTreeMax->left = curr;
}
curr = curr->right;
}
else
{
break;
}
}
// Reassemble the tree
if (leftTreeMax != NULL)
{
leftTreeMax->left = curr->right;
}
if (rightTreeMin != NULL)
{
rightTreeMin->right = curr->left;
}
curr->left = root;
curr->right = root->right;
root->right = NULL;
root = curr;
}
Conclusion
In this article, we discussed Splay Trees, a type of self-balancing binary search tree. We discussed the structure of the tree, its time and space complexities, and how to implement it in C++. We also provided code examples for the operations of insertion, search, deletion, and splay.
Exercises
Write a function to count the number of nodes in a Splay Tree.
// Function to count the number of nodes in a Splay Tree
int countNodes(Node *root)
{
// Base case
if (root == NULL)
{
return 0;
}
// Recursive case
return 1 + countNodes(root->left) + countNodes(root->right);
}
Write a function to find the maximum value stored in a Splay Tree.
// Function to find the maximum value stored in a Splay Tree
int maxValue(Node *root)
{
// Base case
if (root == NULL)
{
return INT_MIN;
}
// Recursive case
int leftMax = maxValue(root->left);
int rightMax = maxValue(root->right);
return max(root->data, max(leftMax, rightMax));
}
Write a function to delete all nodes in a Splay Tree.
// Function to delete all nodes in a Splay Tree
void deleteAllNodes(Node *&root)
{
// Base case
if (root == NULL)
{
return;
}
// Recursive case
deleteAllNodes(root->left);
deleteAllNodes(root->right);
delete root;
root = NULL;
}
Write a function to check if a Splay Tree is a valid binary search tree.
// Function to check if a Splay Tree is a valid binary search tree
bool isBST(Node *root, int minValue, int maxValue)
{
// Base case
if (root == NULL)
{
return true;
}
// Recursive case
if (root->data < minValue || root->data > maxValue)
{
return false;
}
return isBST(root->left, minValue, root->data) && isBST(root->right, root->data, maxValue);
}
Write a function to find the height of a Splay Tree.
// Function to find the height of a Splay Tree
int height(Node *root)
{
// Base case
if (root == NULL)
{
return 0;
}
// Recursive case
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return 1 + max(leftHeight, rightHeight);
}