A Splay Tree is a roughly balanced Binary Search Tree (BST) that always keeps the recently accessed items closer to the root node. As a result, the search operation works must faster when the same data is accessed again.
1. Introduction
Splay Tree is not strictly balanced like the AVL Tree but is intended to work faster for cache applications. Splaying is an additional operation carried out during the insert, delete, and search operations. The recently accessed node becomes the root and the tree changes for even read-only search operations.
Representation
- Roughly balanced: Rotations are used to bring the recently accessed node to the root. This helps the tree be roughly balanced.
- Zig Rotation: Right rotation.
- Zag Rotation: Left rotation.
// Tree node representation
struct Node
{
int data; // Actual data
Node* left; // Pointer to left child
Node* right; // Pointer to right child
Node* parent; // Pointer to parent node
};
// The root node
Node* root;
Applications
- Cache applications
- Windows NT (in the virtual memory, networking, and file system code)
- GCC compiler and GNU C++ library
- The sed string editor
- Fore Systems network routers
- The most popular implementation of Unix malloc, Linux loadable kernel modules, and much other software.
2. The Splay Operation
The splay tree operations such as insertion, deletion, and search are followed by one special operation called splaying. It is nothing but a set of rotations performed to bring the recently accessed node as the root.
Rotations
Splay tree rotation works primarily on three nodes: the target node, the parent, and the grandparent. The following rotations are used by the splay-tree.
- Zig – Right rotation
- Zag – Left rotation
- Zig-Zig – Right-Right rotation (grandparent first)
- Zag-Zag – Left-Left rotation (grandparent first)
- Zig-Zag – Righ-Left rotation (parent first)
- Zag-Zig – Left-Right rotation (parent first)
The combination of simple Left and Right rotation can bring any node as root. So why should we take the grandparent into account and have additional types of rotations? Because the Zig-Zig and Zag-Zag rotations work on the grandparent first. So that it better keeps the recently accessed items closer to the root and helps to maintain the optimal balance.
2.1 Zig Rotation
Perform the Zig rotation to make the target node (10) as root.
2.2 Zag Rotation
Perform the Zag rotation to make the target node (20) as root.
2.3 Zig-Zig Rotation
Perform the Zig-Zig rotation to make the target node (10) as root. Note that the grandparent (30) is rotated first followed by the parent (20).
2.4 Zag-Zag Rotation
Perform the Zag-Zag rotation to make the target node (30) as root. Note that the grandparent (10) is rotated first followed by the parent (20).
2.5 Zig-Zag Rotation
Perform the Zig-Zag rotation to make the target node (20) as root. Note that the parent (30) is rotated first followed by the grandparent (10).
2.6 Zag-Zig Rotation
Perform the Zag-Zig rotation to make the target node (20) as root. Note that the parent node (10) is rotated first followed by the grandparent (30).
- For Zig-Zig and Zag-Zag cases, the rotation is performed on the grandparent first followed by the parent. This is required to maintain the optimal tree balance and to keep the recently accessed items closer to the root node.
- For Zig-Zag and Zag-Zig cases, the rotation is performed on the parent first followed by the grandparent. The reverse order does not work in this case, because performing the first rotation on the grandparent would affect the original position of the splaying node.
Algorithm
- Get the address of the target node.
- Iterate until the target node becomes the root.
- If the target node has only the parent and not the grandparent, perform either Zig or Zag rotation based on the position.
- Left: Zig Rotation
- Right: Zag Rotation
- If the target node has the grandparent, perform any of the following rotations based on its position.
- Left-Left: Zig-Zig Rotation
- Right-Right: Zag-Zag Rotation
- Right-Left: Zig-Zag Rotation
- Left-Right: Zag-Zig Rotation
Code
// Splay the tree by a given node
void SplayTree::splay(Node* x)
{
while (x->parent != NULL) {
if (x->parent->parent == NULL) {
// Node has only parent and not grantparent
if (x == x->parent->left) {
// Node is on left: perform right rotation
// p x
// / => \
// x p
right_rotate(x->parent);
} else {
// Node is on right: perform left rotation
// p x
// \ => /
// x p
left_rotate(x->parent);
}
} else {
// Node has parent and grandparent
Node* parent = x->parent;
Node* grandpa = x->parent->parent;
if (x == parent->left && parent == grandpa->left) {
// Zig zig rotation: Rotate grantparent first for better balance
// g p x
// / / \ \
// p => x g => p
// / \
// x g
right_rotate(x->parent->parent);
right_rotate(x->parent);
} else if (x == parent->right && parent == grandpa->right) {
// Zag zag rotation: Rotate grantparent first for better balance
// g p x
// \ / \ /
// p => g x => p
// \ /
// x g
left_rotate(x->parent->parent);
left_rotate(x->parent);
} else if (x == parent->left && parent == grandpa->right) {
// Zig zag rotation: Rotate parent first because rotating the
// grantparent first would change the position of the node
// g g x
// \ \ / \
// p => x => g p
// / \
// x p
right_rotate(x->parent);
left_rotate(x->parent);
} else {
// Zag zig rotation: Rotate parent first because rotating the
// grantparent first would change the position of the node
// g g x
// / \ /
// p => x => g
// \ / \
// x p p
left_rotate(x->parent);
right_rotate(x->parent);
}
}
}
// Make the splay node as root
root = x;
}
// Perform zag (left) rotation of the given node
void SplayTree::left_rotate(Node* p)
{
// Pull up the right side node on top
Node* top = p->right;
top->parent = p->parent;
if (top->parent != NULL) {
if (p == p->parent->left) {
p->parent->left = top;
} else {
p->parent->right = top;
}
}
// Link the left subtree to right of the target node p
p->right = top->left;
if (p->right) {
p->right->parent = p;
}
// Pull down the target node p to left
top->left = p;
top->left->parent = top;
}
// Perform zig rotation of the given node
void SplayTree::right_rotate(Node* p)
{
// Pull up the left side node on top
Node* top = p->left;
top->parent = p->parent;
if (top->parent != NULL) {
if (p == p->parent->left) {
p->parent->left = top;
} else {
p->parent->right = top;
}
}
// Link the right subtree to left of the target node p
p->left = top->right;
if (p->left) {
p->left->parent = p;
}
// Pull down the target node p to right
top->right = p;
top->right->parent = top;
}
3. Insertion on Splay Tree
A node is always inserted at the bottom of the tree. Traverse the tree based on the order, insert the new node, and perform splaying to make the new node as root.
Algorithm
- Start the traversal from the root node to find the data location.
- If the data element is smaller than the current node, traverse on the left subtree.
- Otherwise, traverse on the right subtree if the data element is greater.
- Insert the node when the traversal reached the bottom.
- Splay the tree to make the new node as root. Refer to “The Splay Operation” for detailed steps.
Code
// Insert a new node
void SplayTree::insert(int data)
{
if (root == NULL) {
// Insert the first node as root and return
root = new Node(data, NULL);
return;
}
Node* p = root;
Node* pp = NULL;
// Traverse the tree from the root
while (1) {
pp = p;
if (data < p->data) {
// Traverse the left subtree if the data is smaller
p = p->left;
if (p == NULL) {
// Insert the node on left and stop the traversal
p = new Node(data, pp);
pp->left = p;
break;
}
} else {
// Traverse the right subtree if the data is greater
p = p->right;
if (p == NULL) {
// Insert the node on right and stop the traversal
p = new Node(data, pp);
pp->right = p;
break;
}
}
}
// Splay the tree to make the new node as root
splay(p);
}
Examples
The following diagrams illustrate the insertion of the data 20, 10, 60, 40, 50, and 30.
Insert element 20
- The initial tree is empty, so insert 20 as the root node.
Insert element 10
- Create a new node 10 on the left of node (20).
- Subsequently, splay the tree to make node 10 as root.
- The node has only the parent and not the grandparent, so perform a Zig (right) rotation since the node is on the left side of the root.
Perform a Zig Rotation from the node (20)
Insert element 60
- Create a new node 60 on the right of node (10) and perform splaying.
- The node (60) has the grandparent and is located on the Right-Right side, so perform a Zag-Zag (Left-Left) rotation.
Perform a Zag-Zag Rotation
Insert element 40
- Create a new node (40) on the right of node (20) and perform splaying.
- The node (40) has the grandparent and is located on the Left-Right side, so perform a Zag-Zig (Left-Right) rotation.
- Here we perform the operation on the parent node first.
Perform a Zag-Zig Rotation
Insert element 50
- Create a new node (50) on the left of node (60) and perform splaying.
- The node has the grandparent and is located on the Right-Left side.
- Hence perform a Zig-Zag (Right-Left) rotation to make the new node as root.
Perform a Zig-Zag Rotation
Insert element 30
- Create a new node (30) on the right of node (20) and perform splaying.
- The node (30) has the grandparent and is located on the Left-Right side.
- Hence perform a Zag-Zig (Left-Right) rotation to make the new node as root.
Perform a Zag-Zig Rotation
- The new node (30) is still one level below the root node. Hence repeat the rotation until it becomes the root.
Perform a Zig Rotation since the node (30) is on the left of the root.
4. Deletion on Splay Tree
Firstly, traverse the tree to find the target and splay the node to make it root. Delete the root node and combine the left and right subtree afterward. The left subtree becomes the root if the right subtree is empty and vice versa. If it has both the left and right subtree, the next smaller element will be identified from the right subtree and becomes the new root.
Algorithm
- Start the traversal from the root node to find the target node.
- If the data element is smaller than the current node, traverse on the left subtree.
- Otherwise, traverse on the right subtree if the data element is greater.
- Splay the tree to bring the target node (or the last accessed node) as root. Refer to “The Splay Operation” for detailed steps.
- Delete the root node if the target matches and assign the new root.
- No child for the target node: Set root to NULL.
- Only has the right subtree: Set root as the right subtree.
- Only has the left subtree: Set root as the left subtree.
- Has both left and right subtree: Find the next smaller data element (in-order successor) node from the right subtree, splay to make this as the new root, and link the left subtree on its left.
Code
// Delete the node by the given data
void SplayTree::remove(int data)
{
if (root == NULL) {
// Return if the tree is empty
return;
}
// Traverse the tree and find the node
Node* p = root;
while(1) {
if (data < p->data && p->left != NULL) {
// Search on the left subtree for smaller elements.
p = p->left;
} else if (data > p->data && p->right != NULL) {
// Search on the right subtree for greater elements.
p = p->right;
} else {
// Found element
break;
}
}
// Splay the target node or the last node as root
splay(p);
if (data == p->data) {
// Delete the root node and the make it as two subtrees
Node* left_subtree = p->left;
Node* right_subtree = p->right;
delete p;
// Node has either no child or one child
if (left_subtree != NULL && right_subtree != NULL) {
// Node has both left and right child.
// Find the smallest node on its right subtree (inorder successor)
Node* min;
for (min = right_subtree; min->left != NULL; min = min->left)
;
// Splay the inorder success node to bring it as root of the right subtree
right_subtree->parent = NULL;
splay(min);
// Make it as root and link left subtree on its left
root = min;
root->left = left_subtree;
left_subtree->parent = root;
} else if (left_subtree == NULL) {
// The right child becomes root if left is NULL
root = right_subtree;
right_subtree->parent = NULL;
} else {
// The left child becomes root if right is NULL
root = left_subtree;
left_subtree->parent = NULL;
}
}
}
Examples
The following diagrams illustrate the deletion of nodes 60 and 30.
Delete the node (60)
- The node (60) has a grandparent and is located on Right-Right, so perform the Zag-Zag rotation to make it a root.
- Perform Zag rotation first on the grandparent (30)
- Perform the next Zag rotation on the parent (50)
- The target node (60) becomes the root after Zag-Zag rotation
Zag Zag Rotation to make the node (60) the Root
- Delete the node (60) as it becomes the root now. The new root will be its left child (50) since the right subtree is empty.
Delete the node (30)
- The node (30) does not have the grandparent and is located on the Left, so perform the Zig rotation to make it the root.
- Find the node (30) and perform Zig rotation
- So, the target node (30) becomes the new root
Perform Zig Rotation and Delete the node (30)
- Deleting the node (30) separates the left and right subtree. So we need to identify the smaller elements on the right subtree (Inorder-successor), and splay the node to make the Root. Finally, link the left subtree with the new root.
5. Search on Splay Tree
Search the data element by traversing the tree from the root node. A splay operation is performed at the end irrespective of whether the element is found or not. Hence a search operation can modify the splay tree to keep the recently accessed items on top.
Algorithm
- Start the traversal from the root node to find the target node.
- If the data matches the current node, return the node.
- Traverse on the left subtree if the data element is smaller than the current node,
- Traverse on the right subtree if the data element is greater.
- Splay the tree with the target node found or with the last accessed node. Refer to “The Splay Operation” for detailed steps.
Code
// Search the node by the given data
Node* SplayTree::search(int data)
{
Node* p = root;
while(1) {
if (data < p->data && p->left != NULL) {
// Search on the left subtree for smaller elements.
p = p->left;
} else if (data > p->data && p->right != NULL) {
// Search on the right subtree for greater elements.
p = p->right;
} else {
// Found element
break;
}
}
// Always splay the tree either with target or the last node
splay(p);
// Return the node if found, NULL otherwise
return (data == p->data)? p : NULL;
}
Example
Search the node (20)
The node (20) does not have a grandparent and is located on the Left, so perform the Zig rotation to make it the root.
6. Traversals on Splay Tree
See Traversals on Binary Tree that are applicable to the Splay Tree.
7. Implementation of Splay Tree in C++
/**
* C++ example to demonstrate the Splay Tree
*/
#include <iostream>
#include <queue>
using namespace std;
// Tree node representation
struct Node
{
int data; // Actual data
Node* left; // Pointer to left child
Node* right; // Pointer to right child
Node* parent; // Pointer to parent node
// Node constructor
Node(int d, Node* pp) : data(d), left(NULL), right(NULL), parent(pp)
{}
};
/**
* Splay Tree implementation
*/
class SplayTree
{
// The root node
Node* root;
public:
// Constructor
SplayTree() : root(NULL)
{}
// Insert a new node
void insert(int data);
// Delete the node by the given data
void remove(int data);
// Search the node by the given data
Node* search(int data);
// Preorder traversal
void preorder() {
preorder(root);
}
private:
// Splay the tree by the given node
void splay(Node* x);
// Perform zag rotation of the given node
void left_rotate(Node* p);
// Perform zig rotation of the given node
void right_rotate(Node* p);
// Traverse the tree in preorder
void preorder(Node* p);
};
// Splay the tree by a given node
void SplayTree::splay(Node* x)
{
while (x->parent != NULL) {
if (x->parent->parent == NULL) {
// Node has only parent and not grantparent
if (x == x->parent->left) {
// Node is on left: perform right rotation
// p x
// / => \
// x p
right_rotate(x->parent);
} else {
// Node is on right: perform left rotation
// p x
// \ => /
// x p
left_rotate(x->parent);
}
} else {
// Node has parent and grandparent
Node* parent = x->parent;
Node* grandpa = x->parent->parent;
if (x == parent->left && parent == grandpa->left) {
// Zig zig rotation: Rotate grantparent first for better balance
// g p x
// / / \ \
// p => x g => p
// / \
// x g
right_rotate(x->parent->parent);
right_rotate(x->parent);
} else if (x == parent->right && parent == grandpa->right) {
// Zag zag rotation: Rotate grantparent first for better balance
// g p x
// \ / \ /
// p => g x => p
// \ /
// x g
left_rotate(x->parent->parent);
left_rotate(x->parent);
} else if (x == parent->left && parent == grandpa->right) {
// Zig zag rotation: Rotate parent first because rotating the
// grantparent first would change the position of the node
// g g x
// \ \ / \
// p => x => g p
// / \
// x p
right_rotate(x->parent);
left_rotate(x->parent);
} else {
// Zag zig rotation: Rotate parent first because rotating the
// grantparent first would change the position of the node
// g g x
// / \ /
// p => x => g
// \ / \
// x p p
left_rotate(x->parent);
right_rotate(x->parent);
}
}
}
// Make the splay node as root
root = x;
}
// Perform zag (left) rotation of the given node
void SplayTree::left_rotate(Node* p)
{
// Pull up the right side node on top
Node* top = p->right;
top->parent = p->parent;
if (top->parent != NULL) {
if (p == p->parent->left) {
p->parent->left = top;
} else {
p->parent->right = top;
}
}
// Link the left subtree to right of the target node p
p->right = top->left;
if (p->right) {
p->right->parent = p;
}
// Pull down the target node p to left
top->left = p;
top->left->parent = top;
}
// Perform zig rotation of the given node
void SplayTree::right_rotate(Node* p)
{
// Pull up the left side node on top
Node* top = p->left;
top->parent = p->parent;
if (top->parent != NULL) {
if (p == p->parent->left) {
p->parent->left = top;
} else {
p->parent->right = top;
}
}
// Link the right subtree to left of the target node p
p->left = top->right;
if (p->left) {
p->left->parent = p;
}
// Pull down the target node p to right
top->right = p;
top->right->parent = top;
}
// Insert a new node
void SplayTree::insert(int data)
{
if (root == NULL) {
// Insert the first node as root and return
root = new Node(data, NULL);
return;
}
Node* p = root;
Node* pp = NULL;
// Traverse the tree from the root
while (1) {
pp = p;
if (data < p->data) {
// Traverse the left subtree if the data is smaller
p = p->left;
if (p == NULL) {
// Insert the node on left and stop the traversal
p = new Node(data, pp);
pp->left = p;
break;
}
} else {
// Traverse the right subtree if the data is greater
p = p->right;
if (p == NULL) {
// Insert the node on right and stop the traversal
p = new Node(data, pp);
pp->right = p;
break;
}
}
}
// Splay the tree to make the new node as root
splay(p);
}
// Delete the node by the given data
void SplayTree::remove(int data)
{
if (root == NULL) {
// Return if the tree is empty
return;
}
// Traverse the tree and find the node
Node* p = root;
while(1) {
if (data < p->data && p->left != NULL) {
// Search on the left subtree for smaller elements.
p = p->left;
} else if (data > p->data && p->right != NULL) {
// Search on the right subtree for greater elements.
p = p->right;
} else {
// Found element
break;
}
}
// Splay the target node or the last node as root
splay(p);
if (data == p->data) {
// Delete the root node and the make it as two subtrees
Node* left_subtree = p->left;
Node* right_subtree = p->right;
delete p;
// Node has either no child or one child
if (left_subtree != NULL && right_subtree != NULL) {
// Node has both left and right child.
// Find the smallest node on its right subtree (inorder successor)
Node* min;
for (min = right_subtree; min->left != NULL; min = min->left)
;
// Splay the inorder success node to bring it as root of the right subtree
right_subtree->parent = NULL;
splay(min);
// Make it as root and link left subtree on its left
root = min;
root->left = left_subtree;
left_subtree->parent = root;
} else if (left_subtree == NULL) {
// The right child becomes root if left is NULL
root = right_subtree;
right_subtree->parent = NULL;
} else {
// The left child becomes root if right is NULL
root = left_subtree;
left_subtree->parent = NULL;
}
}
}
// Search the node by the given data
Node* SplayTree::search(int data)
{
Node* p = root;
while(1) {
if (data < p->data && p->left != NULL) {
// Search on the left subtree for smaller elements.
p = p->left;
} else if (data > p->data && p->right != NULL) {
// Search on the right subtree for greater elements.
p = p->right;
} else {
// Found element
break;
}
}
// Always splay the tree either with target or the last node
splay(p);
// Return the node if found, NULL otherwise
return (data == p->data)? p : NULL;
}
// Traverse the tree in preorder (parent, left, right)
void SplayTree::preorder(Node* p)
{
if (p != NULL) {
cout << p->data << endl;
preorder(p->left);
preorder(p->right);
}
}
int main()
{
// Create a Splay tree and insert data
SplayTree tree;
tree.insert(20);
tree.insert(10);
tree.insert(60);
tree.insert(40);
tree.insert(50);
tree.insert(30);
cout << "Tree after inserting 20, 10, 60, 40, 50, and 30" << endl;
tree.preorder();
// Delete data
tree.remove(60);
tree.remove(30);
cout << "Tree after removing 60 and 30" << endl;
tree.preorder();
// Search
Node* p = tree.search(20);
if (p != NULL) {
cout << "search(20) located node: " << p->data << endl;
}
cout << "Tree after searching 20" << endl;
tree.preorder();
}
Output
Tree after inserting 20, 10, 60, 40, 50, and 30
30
20
10
50
40
60
Tree after removing 60 and 30
40
20
10
50
search(20) located node: 20
Tree after searching 20
20
10
40
50