Splay Tree

Splay Tree

A splay tree is a self-balanced or self-adjusted binary search tree. We can say, Splay Tree is used in some cases where some elements or data are accessed more frequently over other elements or data. The splay tree self-adjusts after the search, insert, and delete operations. Splay trees are better than other trees, where the specific pattern of the sequence are not known. If we talk about the worst-case time complexity of binary search tree operations is O(n) if the tree is skewed and we have other trees like AVL and Red-Black Trees, their worst-case time complexity is O(log n).

What if we want to do better than AVL and Red-Black Trees: -

In the splay tree, we make recently accessed item by an application, as the root of the tree Splay tree is also self-balancing binary search tree like AVL and Red-Black Trees. In the splay tree, we make a recently accessed item by an application as the root of the tree, so if we want to search again that recently accessed item, then it would take O(1) time. The idea behind this is an application; 80% of the access are to 20% of the items. Suppose there are millions of data items and only a few of them are frequently used, so splay tree come into the picture. There are many real-world applications where the splay tree is used, like in the intrusion detection system, which is an important and essential part of the security infrastructure.

Operations on Splay Tree: -

• Searching: -

The search operation on the splay tree is the same as the binary search tree; it also does splays(move a node to the root). If searching for a node is successful by an application, then that node will be splayed and becomes the new root of the tree. Otherwise, the last not null node is splayed and becomes the new root of the tree. For searching, we need to follow some cases:

1. If the searched node is root: -

If the node which we are searching for is the root node, then we return the root and do nothing.

2. If the searched node is the child of root:

If the node which we are searching has no grandparent and node is either a left child of the root, then we need to do right rotation (Zig Rotation), or node is a right child of the root, then we need to do left rotation (Zag Rotation).

3. If Node has both parent and grandparent: -

Then some subcases should be followed:

a). Zig - Zig and Zag - Zag: -

If the node which we are searching is the left child of its parent and also the left child of its grandparent, then we have to do two right rotations, or the desired node is the right child of its parent and also the right child of its grandparent then, we have to perform two left rotations.

b). Zig - Zag and Zag - Zig: -                                                                  

If the node which we are searching is the left child of its parent and right child of its grandparent then we have to do left rotation then right rotations or the desired node is right child of its parent and the left child of its grandparent then, we have to perform right rotation and then left rotation.

These operations make the searched node as root and also help to balance the tree.

• Inserting: -

If we want to insert a key in the splay tree, then we need to follow some cases:

1. If Root is Null: -

We normally make a new node or add a new node and return it as root.

• If the key already there: -

If present already in the tree then we will make it as the root node and if it is not there, then last accessed not null node becomes the root node.

3. If the root node same as the keywe won’t do anything.     

4. Else we will make new node and compare it with the root node of tree.

• If key is smaller than the root node, then we will make root node as right child of new node, copy left child of root as left child of the new node and make left child of root as NULL.
• If key is greater than root node, then we will make root node as left child of new node, and copy right child of root node as right child of new node and make right child of root node as NULL.

5. We need to return new node which we have made as new root of tree.

• Deletion: -

   1. If Root is NULL: We directly return the root.

2. Else Splay the given key. If key is present, then we will make it as the new root node. If not there, then last accessed not null node will become the new root.

3. If new root node is not same as key, then return the root node as key is not present.

4. Else the key is present.

• Divide or Split the tree into two trees suppose T1 = root’s left sub-tree and T2 = root’s right sub-tree and delete the root node.
• Suppose the roots of T1 and T2 be Root1 and Root2 respectively.
• If Root1 is NULL, then we need to return Root2.
• Else, Splay the higher value node (node having the maximum value) of T1.
• After the Splay procedure, make Root2 as the right child of Root1 and return Root1.

Implementation of Splay Tree in C language: -

#include <stdio.h>
 #include <stdlib.h>
 typedef struct node {
 int data;
 struct node *left;
 struct node *right;
 struct node *parent;
 }node;
 typedef struct splay_tree {
 struct node *root;
 }splay_tree;
 node* new_node(int data) {
 node *n = malloc(sizeof(node));
 n -> data = data;
 n -> parent = NULL;
 n -> right = NULL;
 n -> left = NULL;
 return n;
 }
 splay_tree * new_splay_tree() {
 splay_tree * t = malloc(sizeof(splay_tree));
 t -> root = NULL;
 return t;
 }
 node* maximum(splay_tree * t, node * x) {
 while(x -> right != NULL)
   x = x -> right;
 return x;
 }
 void left_rotate(splay_tree * t, node * x)
 {
 node * y = x -> right;
 x -> right = y -> left;
 if(y -> left != NULL)
 {
   y -> left -> parent = x;
 }
 y -> parent = x -> parent;
 if(x -> parent == NULL) { // x is root
   t -> root = y;
 }
 else if(x == x -> parent -> left) { // x is left child
   x -> parent -> left = y;
 }
 else { //x is right child
   x -> parent -> right = y;
 }
 y -> left = x;
 x -> parent = y;
 }
 void right_rotate(splay_tree * t, node * x) {
 node * y = x -> left;
 x -> left = y -> right;
 if(y -> right != NULL) {
   y -> right -> parent = x;
 }
 y -> parent = x -> parent;
 if(x -> parent == NULL) { // x is root
   t -> root = y;
 }
 else if(x == x -> parent -> right)
 { // x is left child
   x -> parent -> right = y;
 }
 else { // x is right child
   x -> parent -> left = y;
 }
 y -> right = x;
 x -> parent = y;
 }
 void splay(splay_tree *t, node *n) {
 while(n -> parent != NULL) { // node is not root
   if(n -> parent == t -> root) { // node is child of root, one rotation
     if(n == n -> parent -> left) {
       right_rotate(t, n -> parent);
     }
     else {
       left_rotate(t, n -> parent);
     }
   }
   else {
     node *p = n -> parent;
     node *g = p -> parent; // grandparent
     if(n -> parent -> left == n && p -> parent -> left == p) { // both are left children
       right_rotate(t, g);
       right_rotate(t, p);
     }
     else if(n -> parent -> right == n && p -> parent -> right == p) { // both are right children
       left_rotate(t, g);
       left_rotate(t, p);
     }
     else if(n -> parent -> right == n && p -> parent -> left == p) {
       left_rotate(t, p);
       right_rotate(t, g);
     }
     else if(n -> parent -> left == n && p -> parent -> right == p) {
       right_rotate(t, p);
       left_rotate(t, g);
     }
   }
 }
 }
 void insert(splay_tree *t, node *n)
 {
 node *y = NULL;
 node *temp = t -> root;
 while(temp != NULL) {
   y = temp;
   if(n -> data < temp -> data)
     temp = temp -> left;
   else
     temp = temp -> right;
 }
 n -> parent = y;
 if(y == NULL) // newly added node is root
   t -> root = n;
 else if(n -> data < y -> data)
   y -> left = n;
 else
   y -> right = n;
 splay(t, n);
 }
 node* search(splay_tree *t, node *n, int x)
 {
 if(x == n -> data)
 {
   splay(t, n);
   return n;
 }
 else if(x < n -> data)
   return search(t, n -> left, x);
 else if(x > n -> data)
   return search(t, n -> right, x);
 else
   return NULL;
 }
 void delete(splay_tree *t, node *n)
 {
 splay(t, n);
 splay_tree *left_subtree = new_splay_tree();
 left_subtree -> root = t -> root -> left;
 if(left_subtree -> root != NULL)
   left_subtree -> root -> parent = NULL;
 splay_tree *right_subtree = new_splay_tree();
 right_subtree -> root = t -> root -> right;
 if(right_subtree -> root != NULL)
   right_subtree -> root -> parent = NULL;
 free(n);
 if(left_subtree -> root != NULL)
 {
   node *m = maximum(left_subtree, left_subtree -> root);
   splay(left_subtree, m);
   left_subtree -> root -> right = right_subtree -> root;
   t -> root = left_subtree -> root;
 }
 else
 {
   t -> root = right_subtree -> root;
 }
 }
 void inorder(splay_tree *t, node *n)
 {
 if(n != NULL) {
   inorder(t, n -> left);
   printf("%d\n", n -> data);
   inorder(t, n -> right);
 }
 }
 int main()
 {
 splay_tree *t = new_splay_tree();
 node *a, *b, *c, *d, *e, *f, *g, *h, *i, *j, *k, *l, *m;
 a = new_node(10);
 b = new_node(20);
 c = new_node(30);
 d = new_node(100);
 e = new_node(90);
 f = new_node(40);
 g = new_node(50);
 h = new_node(60);
 i = new_node(70);
 j = new_node(80);
 k = new_node(150);
 l = new_node(110);
 m = new_node(120);
 insert(t, a);
 insert(t, b);
 insert(t, c);
 insert(t, d);
 insert(t, e);
 insert(t, f);
 insert(t, g);
 insert(t, h);
 insert(t, i);
 insert(t, j);
 insert(t, k);
 insert(t, l);
 insert(t, m);
 delete(t, a);
 delete(t, m);
 inorder(t, t -> root);
 return 0;
 } 

Output: -

Complexity: -

Time complexity of splay tree operations (e.g. insertion, deletion and searching) is O(log n).

Applications of Splay Tree: -

• Splay is used to implement look-up table in Network Router.
  • Used to implement cache, memory allocators.
    • Used in Data Compression
    • Used in the gcc compiler