Splay Tree in Data Structure

In this article, we will discuss what is a splay tree in data structure. We will discuss what a splay tree is, its different rotations, and its implementation programs in C++, Java, and Python. So, let’s get started. We will first start off by revising what are Binary Search Trees.

What are Binary Search Trees?
Binary Search Trees (BSTs) are also binary trees i.e. the maximum number of child nodes of any node is 2. A binary search tree has one special property that makes it very efficient for searching purposes and hence it gets its name i.e. Binary Search Tree. The property states that all the values in the left subtree of a node will be smaller than the value in that node and all the values in the right subtree of any node will be greater than the value inside that node. Consider the binary search tree shown below.

The values in the left subtree of the root node are smaller than 10 and the values in the right subtree of the root node are greater than 10. The condition of the left subtree containing smaller values and the right subtree containing larger values is not just true for the root node, rather it is true for every node of the binary search tree.

The node structure of a binary tree and BST is exactly the same as a BST is also a binary tree only. This is shown below.

What is a Splay Tree in Data Structure?

When we use BSTs for searching the data, the time complexity in an average case is O(log2N). This is because the average case height of a binary tree is O(log2N). However, the worst case can be a left or a right-skewed tree i.e. a linear tree. Then the worst-case time complexity of the operations like searching, insertion, and deletion becomes O(N).

However, what if the trees are made self-balancing such that they never form skewed structures and the height always remains O(log2N)? This is done in AVL trees and Red-Black trees. These are self-balancing BSTs; hence, the worst-case time complexity of searching, insertion and deletion is O(log2N).

However, the question is, can we do better than this? The answer is yes. In some practical scenarios, we can do better than AVL and Red-Black Trees. How? Using splay trees.

The main idea of splay trees is based on the “most frequently used elements”. Basically, a splay tree in data structure, involves all the operations of a normal Binary Search Tree i.e. searching, insertion, deletion, etc. However, it also includes one special operation i.e. always performed and it is called splaying. The idea is to bring the more frequently used elements closer to the root of the BST so that if they are searched again, they can be found more quickly as compared to the less frequently used elements.

Consider the BST shown below.

Let us say we want to search for 8. So, we start from the root node. Since the value at the root node is 10 and we are searching for 8 i.e. a smaller element than the current node, we will move toward the left. So, we go to the next node and we found 8. This is a normal search operation in BST. However, we will do a little more than this in the splay tree. We will perform splaying i.e. 8 will now become the root node of the tree. How? We can do this with some rotations. There are 6 different types of rotations that can be performed in a splay tree. These are as follows.

  1. Zig Rotation (Right Rotation)
  2. Zig Zig Rotation (2 Zig Rotations or 2 right rotations)
  3. Zag Rotation (Left Rotation)
  4. Zag Zag Rotation (2 Zag rotations or 2 left rotations)
  5. Zig Zag Rotation (Right-Left Rotation i.e. first do Zig then Zag)
  6. Zag Zig Rotation (Left-Right Rotation i.e. first do Zag then Zig)

Let us study these rotations one by one.

Zig Rotation or Right Rotation

Consider the tree shown below.

In this rotation, we move every node to 1 position towards its right. This rotation is used in the case when the element that we are searching for is either present in the root node of the BST or it is present in the left child of the root node.

Consider that we are searching for node 9. This means that we are searching for the left child of the root node. So, we can perform zig rotation.

So, the steps for searching node 9 are the same as we perform the search in BST and have already been discussed. Now, since this is the zig rotation i.e. we need to rotate each element 1 position to its right. This rotation is shown below.

So, every element has to go 1 position to its right. Now, we can imagine every element going to 1 position to its right and we imagine that 9 will become the root node and 11 will; be its right child and the left child will be 7. What about node 10?

So, node 10 is the right child of node 9 before rotation. So, after rotation, it will remain in the right subtree of node 9. However, it will now become the left child of node 11 as shown below.

Zig Zig Rotation or Right-Right Rotation

In this rotation, 2 right rotations are performed one after another. This is used in the case when the element that we are searching for is neither the root node nor the left child of the root node but is present below in the left subtree of the root node. This means that the node has both, parent and grandparent. Consider the tree shown below.

So, if we are searching for node 3, we find it at the last level. Now, we will perform the 1st right rotation.

After one rotation, the tree is shown below. Now, we perform the second rotation.

So, after 2 right rotations, node 3 is now the root node of the tree.

Zag Rotation or Left Rotation

Again, consider the tree shown below.

The Zag rotation or the left rotation is performed when the element that we are searching for is either the root node or the right child of the root node.

So, consider that we are searching for node 13. Since it is the right child of the root node, we perform the zig rotation. Every element will rotate and reach 1 position to its current left. This is shown below.

So, since after rotation, 14 has to become the right child of 13 and 12 was present as its left child, 12 will remain in the left subtree but becomes the right child of node 11. Node 13 has become the root node now.

Zag Zag Rotation or Left-Left Rotation

Here, we perform 2 left rotations. Again, it is done when we are searching for an element i.e., not the root or the right child of the root but present in the right subtree and has both parent and grandparent. So, consider the tree shown below.

If we are searching 7, the result of the zag zag rotation is shown below.

So, node 7 has now become the root node of the tree.

Zig Zag Rotation or Right Left Rotation

This is a sequence of zig rotations which are then followed by a sequence of zag rotations. The zig-zag rotation is used when the parent node and the grandparent node of a node are in LR or RL relationship with each other. Consider the tree shown below.

If we want to search 5, then the parent and grandparent are in an RL relationship with each other. So, we first perform the Right rotation i.e. Zig rotation about node 6, and then the left rotation i.e. Zag rotation about the root node i.e. node 4, thus completing the Zig Zag rotation. This is shown below.

Finally, we can see that 5 is the root node of the tree. So, this is Zig Zag rotation.

Zag Zig Rotation or Left-Right Rotation

This rotation is the same as the zig-zag rotation. The only difference is that the left rotation happens first and then the right rotation. Consider the tree shown below.

So, here if we want to search 5, the zag zig rotation is shown below.

So, we can see that node 5 is at the root of the tree. This is Zag Zig Rotation.

Now that we have studied the splay trees, let us implement these rotations and other BST operations of a splay tree in the program shown below.

#include <bits/stdc++.h>
using namespace std;

class node
{
public:
    int key;
    node *left, *right;
};

node *TreeNode(int key)
{
    node *Node = new node();
    Node->key = key;
    Node->left = Node->right = NULL;
    return (Node);
}

node *rightRotate(node *x)
{
    node *y = x->left;
    x->left = y->right;
    y->right = x;
    return y;
}

node *leftRotate(node *x)
{
    node *y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
}
node *splay(node *root, int key)
{
    if (root == NULL || root->key == key)
        return root;

    if (root->key > key)
    {
        if (root->left == NULL)
            return root;

        // Zig-Zig Rotation
        if (root->left->key > key)
        {
            root->left->left = splay(root->left->left, key);
            root = rightRotate(root);
        }
        else if (root->left->key < key) // Zig-Zag 
        {
            root->left->right = splay(root->left->right, key);
            if (root->left->right != NULL)
                root->left = leftRotate(root->left);
        }

        return (root->left == NULL) ? root : rightRotate(root);
    }
    else
    {
        if (root->right == NULL)
            return root;

        // Zag-Zig Rotation
        if (root->right->key > key)
        {
            root->right->left = splay(root->right->left, key);

            if (root->right->left != NULL)
                root->right = rightRotate(root->right);
        }
        else if (root->right->key < key)
        {
            root->right->right = splay(root->right->right, key);
            root = leftRotate(root);
        }

        return (root->right == NULL) ? root : leftRotate(root);
    }
}

node *bstSearch(node *root, int key)
{
    return splay(root, key);
}

void preOrder(node *root)
{
    if (root != NULL)
    {
        cout << root->key << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
    node *root = TreeNode(100);
    root->left = TreeNode(50);
    root->right = TreeNode(200);
    root->left->left = TreeNode(40);
    root->left->left->left = TreeNode(30);
    root->left->left->left->left = TreeNode(20);

    root = bstSearch(root, 20);
    preOrder(root);
    return 0;
}
class Tree
{
static class node
{

    int key;
    node left, right;
};

static node TreeNode(int key)
{
    node Node = new node();
    Node.key = key;
    Node.left = Node.right = null;
    return (Node);
}

static node rightRotate(node x)
{
    node y = x.left;
    x.left = y.right;
    y.right = x;
    return y;
}

static node leftRotate(node x)
{
    node y = x.right;
    x.right = y.left;
    y.left = x;
    return y;
}

static node splay(node root, int key)
{
    if (root == null || root.key == key)
        return root;

    if (root.key > key)
    {
        if (root.left == null) return root;

        if (root.left.key > key)
        {
            root.left.left = splay(root.left.left, key);

            root = rightRotate(root);
        }
        // Zig-Zag 
        else if (root.left.key < key) 
        {
        	root.left.right = splay(root.left.right, key);

        	if (root.left.right != null)
                root.left = leftRotate(root.left);
        }

        return (root.left == null) ? root : rightRotate(root);
    }
    else 
    {
        if (root.right == null) return root;

        if (root.right.key > key)
        {
            root.right.left = splay(root.right.left, key);

            if (root.right.left != null)
                root.right = rightRotate(root.right);
        }
        // Zag-Zag 
        else if (root.right.key < key)
        {
         	root.right.right = splay(root.right.right, key);
            root = leftRotate(root);
        }
        return (root.right == null) ? root : leftRotate(root);
    }
}


static node bstSearch(node root, int key)
{
    return splay(root, key);
}

static void preOrder(node root)
{
    if (root != null)
    {
        System.out.print(root.key + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}
}

public class Main {
    
    public static void main(String[] args)
    {
        Tree.node root = Tree.TreeNode(100);
        root.left = Tree.TreeNode(50);
        root.right = Tree.TreeNode(200);
        root.left.left = Tree.TreeNode(40);
        root.left.left.left = Tree.TreeNode(30);
        root.left.left.left.left = Tree.TreeNode(20);
    
        root = Tree.bstSearch(root, 20);
        Tree.preOrder(root);
    }
}
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None


class SplayTree:
    def __init__(self):
        self.root = None

    def leftRotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != None:
            y.left.parent = x

        y.parent = x.parent
        # x is root
        if x.parent == None:
            self.root = y
        # x is left child
        elif x == x.parent.left:
            x.parent.left = y
        # x is right child
        else:
            x.parent.right = y

        y.left = x
        x.parent = y

    def rightRotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != None:
            y.right.parent = x

        y.parent = x.parent
        # x is root
        if x.parent == None:
            self.root = y
        # x is right child
        elif x == x.parent.right:
            x.parent.right = y
        # x is left child
        else:
            x.parent.left = y

        y.right = x
        x.parent = y

    def splay(self, n):
        # node is not root
        while n.parent != None:
            # node is child of root, one rotation
            if n.parent == self.root:
                if n == n.parent.left:
                    self.rightRotate(n.parent)
                else:
                    self.leftRotate(n.parent)

            else:
                p = n.parent
                g = p.parent  # grandparent

                if n.parent.left == n and p.parent.left == p:  # both are left children
                    self.rightRotate(g)
                    self.rightRotate(p)

                elif n.parent.right == n and p.parent.right == p:  # both are right children
                    self.leftRotate(g)
                    self.leftRotate(p)

                elif n.parent.right == n and p.parent.left == p:
                    self.leftRotate(p)
                    self.rightRotate(g)

                elif n.parent.left == n and p.parent.right == p:
                    self.rightRotate(p)
                    self.leftRotate(g)

    def insert(self, n):
        y = None
        temp = self.root
        while temp != None:
            y = temp
            if n.data < temp.data:
                temp = temp.left
            else:
                temp = temp.right

        n.parent = y

        if y == None:  # newly added node is root
            self.root = n
        elif n.data < y.data:
            y.left = n
        else:
            y.right = n

        self.splay(n)

    def bstSearch(self, n, x):
        if x == n.data:
            self.splay(n)
            return n
        elif x < n.data:
            return self.bstSearch(n.left, x)
        elif x > n.data:
            return self.bstSearch(n.right, x)
        else:
            return None

    def preOrder(self, n):
        if n != None:
            print(n.data)
            self.preOrder(n.left)
            self.preOrder(n.right)


if __name__ == '__main__':
    tree = SplayTree()
    a = TreeNode(10)
    b = TreeNode(20)
    c = TreeNode(30)
    d = TreeNode(100)
    e = TreeNode(90)
    f = TreeNode(40)
    g = TreeNode(50)
    tree.insert(a)
    tree.insert(b)
    tree.insert(c)
    tree.insert(d)
    tree.insert(e)
    tree.insert(f)
    tree.insert(g)
    tree.bstSearch(tree.root, 90)
    tree.preOrder(tree.root)

Conclusion
So, we have talked about the Splay tree in data structure and its various rotations and advantages and disadvantages. We hope that you liked the discussion and understood the concept completely. We hope to see you again soon at PrepBytes.

So, this was all about the Splay Tree in Data Structure. Let us now discuss some Frequently Asked Questions (FAQs).

Frequently Asked Questions (FAQs)

1. What are some advantages of a Splay Tree in Data Structure?
We do not need to store any extra information when we talk about the splay tree. Basically, a splay tree is a self-balancing BST. There are other self-balancing BSTs like AVL tree and Red Black Tree. However, in the AVL tree, we need to store the balance factor of each node and in the Red Black Tree, we need one extra bit for storing the color of the node i.e. red or black. In a splay tree, however, we do not need to store any such information.

2. What is the disadvantage of a Splay Tree in Data Structure?
The main disadvantage of the Splay Tree is that these trees, unlike the AVL tree are roughly balanced just like Red-Black trees. So, sometimes they can be linear i.e. skewed, and then the time complexity will be O(N).

3. Is there any practical use of Splay Tree?
Splay trees are practically the fastest BSTs used. They are even used in GCC compilers.

Leave a Reply

Your email address will not be published. Required fields are marked *