Splay Trees are a variation of binary search trees that possess a distinctive characteristic of adapting their configuration according to the most recent access patterns. This adaptive behavior enhances their effectiveness for specific tasks, with node insertion being a notable example. Here, we will explore the process of adding nodes to a splay tree using the C++ programming language.
Before we explore the insertion process, let's take a moment to review the key attributes of a Splay Tree. Splay Trees are a type of binary search tree that emphasizes the most recently accessed node by relocating it to the root. This operation, referred to as "splaying," consists of a sequence of rotations and reorganizations.
Inserting a node into a Splay Tree involves two main steps:
Initially, the new node is added to the binary search tree following the standard insertion procedure. This involves locating the correct position according to the node's value and inserting it as a leaf node.
Post the regular insertion process, the recently added node experiences a splaying procedure to guarantee its placement as the root node. This dynamic reordering is crucial for preserving the tree's flexibility according to its access patterns over time.
Example:
Let's examine the C++ code that makes this process possible in more detail.
#include <iostream>
// Node structure for Splay Tree
struct Node {
int key;
Node* left, *right;
};
// Function to perform right rotation
Node* rightRotate(Node* x) {
Node* y = x->left;
x->left = y->right;
y->right = x;
return y;
}
// Function to perform left rotation
Node* leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// Splay operation to move the recently accessed node to the root
Node* splay(Node* root, int key) {
if (!root || root->key == key)
return root;
// Key lies in the left subtree
if (key < root->key) {
// Key is not present in the tree
if (!root->left)
return root;
// Zig-Zig (Left Left)
if (key < root->left->key) {
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
// Zig-Zag (Left Right)
else if (key > root->left->key) {
root->left->right = splay(root->left->right, key);
if (root->left->right)
root->left = leftRotate(root->left);
}
// Perform the second rotation for Zig-Zag and Zig-Zig
return (root->left) ? rightRotate(root) : root;
}
// Key lies in the right subtree
else {
// Key is not present in the tree
if (!root->right)
return root;
// Zag-Zag (Right Right)
if (key > root->right->key) {
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
// Zag-Zig (Right Left)
else if (key < root->right->key) {
root->right->left = splay(root->right->left, key);
if (root->right->left)
root->right = rightRotate(root->right);
}
// Perform the second rotation for Zag-Zig and Zag-Zag
return (root->right) ? leftRotate(root) : root;
}
}
// Function to insert a key into the Splay Tree
Node* insert(Node* root, int key) {
// If the tree is empty, create a new node
if (!root)
return new Node{ key, nullptr, nullptr };
// Perform a standard BST insert
if (key < root->key)
root->left = insert(root->left, key);
else if (key > root->key)
root->right = insert(root->right, key);
else
return root; // Duplicate keys are not allowed
// Perform the splay operation on the newly inserted node
return splay(root, key);
}
// Function to print the in-order traversal of the tree
void inOrder(Node* root) {
if (root) {
inOrder(root->left);
std::cout << root->key << " ";
inOrder(root->right);
}
}
int main() {
Node* root = nullptr;
// Insert elements into the Splay Tree
root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 15);
root = insert(root, 2);
root = insert(root, 8);
std::cout << "In-order traversal of the Splay Tree: ";
inOrder(root);
return 0;
}
Output:
In-order traversal of the Splay Tree: 2 5 8 10 15
Explanation:
The given C++ code contains the implementation of Splay Tree insertion. It encompasses methods for performing right and left rotations, the splaying mechanism, and the actual insertion algorithm. Within the main function, there is a demonstration of inserting a series of values (10, 5, 15, 2, 8) into the Splay Tree.
Conclusion:
Splay Trees offer an intriguing method for managing binary search trees, adapting their layout according to recent access patterns. Illustrated in the C++ snippet, the process of inserting a node smoothly combines traditional binary search tree insertion with a follow-up splaying process, maintaining the tree's ability to self-adjust.
A thorough understanding of Splay Trees and their insert operation is essential for leveraging their benefits in scenarios where responsive flexibility is key.
