Data Structures

Splay Tree in Data Structure

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

Splay Tree 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.

Zig Rotation of Splay Tree
Zig Rotation of Splay Tree

2.2 Zag Rotation

Perform the Zag rotation to make the target node (20) as root.

Zag Rotation of Splay Tree
Zag Rotation of Splay Tree

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).

Zig-Zig Rotation of Splay Tree
Zig-Zig Rotation of Splay Tree

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).

Zag-Zag Rotation of AVL Tree
Zag-Zag Rotation of AVL Tree

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).

Zig Zag Rotation of AVL Tree
Zig Zag Rotation of AVL Tree

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).

Zag-Zig Rotation of AVL Tree
Zag-Zig Rotation of AVL Tree
  • 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

  1. Get the address of the target node.
  2. Iterate until the target node becomes the root.
  3. 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
  4. 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

  1. Start the traversal from the root node to find the data location.
  2. If the data element is smaller than the current node, traverse on the left subtree.
  3. Otherwise, traverse on the right subtree if the data element is greater.
  4. Insert the node when the traversal reached the bottom.
  5. 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
Insert element 20
Insert element 20
  • The initial tree is empty, so insert 20 as the root node.
Insert element 10
Insert element 10
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)
Perform a Zig Rotation from the node (20) on Splay Tree
Perform a Zig Rotation from the node (20)
Insert element 60
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
Perform a Zag-Zag Rotation on Splay Tree
Perform a Zag-Zag Rotation
Insert element 40
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
Perform a Zag-Zig Rotation on Splay Tree
Perform a Zag-Zig Rotation
Insert element 50
Insert element 50
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
Perform a Zig-Zag Rotation on Splay Tree
Perform a Zig-Zag Rotation
Insert element 30
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
Perform a Zag-Zig Rotation on Splay Tree
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.
Perform Zig rotation on the parent (50) on Splay Tree
Perform Zig rotation on the parent (50)

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

  1. Start the traversal from the root node to find the target node.
  2. If the data element is smaller than the current node, traverse on the left subtree.
  3. Otherwise, traverse on the right subtree if the data element is greater.
  4. Splay the tree to bring the target node (or the last accessed node) as root. Refer to “The Splay Operation” for detailed steps.
  5. 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)
Delete the node (60) on Splay Tree
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
Splay Tree Zag Zag Rotation to make the node (60) as Root
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.
After Deleting the node (60)
After Deleting the node (60)
Delete the node (30)
Delete the node (30) from Splay Tree
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)
Zig Rotation to delete the node (30)
Zig Rotation to 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.
Merge subtrees after Splay Tree deletion
Merge subtrees after Splay Tree deletion

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

  1. Start the traversal from the root node to find the target node.
  2. If the data matches the current node, return the node.
  3. Traverse on the left subtree if the data element is smaller than the current node,
  4. Traverse on the right subtree if the data element is greater.
  5. 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.

Search node (20) on Splay Tree
Search node (20) on Splay Tree
Zig rotation after Search
Zig rotation after Search

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

8. References

Copyright copyright 2024 Simplerize