Projects

Splay tree

You are not Member of this Project.
Project Owner : vani.R
Created Date : Thu, 15/03/2012 - 14:46
Project Description :

 

Insertion

To insert a node x into a splay tree:

  1. First insert the node as with a normal binary search tree.
  2. Then splay the newly inserted node x to the top of the tree.

 

Deletion

To delete a node x, we use the same method as with a binary search tree: if x has two children, we swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Then we remove that node instead. In this way, deletion is reduced to the problem of removing a node with 0 or 1 children.

Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree. OR The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. This leaves the tree with two sub trees. The maximum element of the left sub tree (: METHOD 1), or minimum of the right sub tree (: METHOD 2) is then splayed to the root. The right sub tree is made the right child of the resultant left sub tree (for METHOD 1). The root of left sub tree is the root of melded tree.

 

Code in C language


Splay operation in BST

Here x is the node on which the splay operation is performed and root is the root node of the tree.

		#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node 
{
        int data;
        struct node *parent;
        struct node *left;
        struct node *right;
};
int data_print(struct node *x);
struct node *rightrotation(struct node *p,struct node *root);
struct node *leftrotation(struct node *p,struct node *root);
void splay (struct node *x, struct node *root);
struct node *insert(struct node *p,int value);
struct node *inorder(struct node *p);
struct node *delete(struct node *p,int value);
struct node *sucessor(struct node *x);
struct node *lookup(struct node *p,int value);
 
void splay (struct node *x, struct node *root)
{
        struct node *p,*g;
        /*check if node x is the root node*/
        if(x==root)
                return;
        /*Performs Zig step*/
        else if(x->parent==root)
        {
                if(x==x->parent->left)
                        root=rightrotation(root,root);
                else
                        root=leftrotation(root,root);
        }
        else
        {
                p=x->parent; /*now points to parent of x*/
                g=p->parent; /*now points to parent of x's parent*/
                /*Performs the Zig-zig step when x is left and x's parent is left*/
                if(x==p->left&&p==g->left)
                {
                        root=rightrotation(g,root);
                        root=rightrotation(p,root);
                }
                /*Performs the Zig-zig step when x is right and x's parent is right*/
                else if(x==p->right&&p==g->right)
                {
                        root=leftrotation(g,root);
                        root=leftrotation(p,root);
                }
                /*Performs the Zig-zag step when x's is right and x's parent is left*/
                else if(x==p->right&&p==g->left)
                {
                        root=leftrotation(p,root);
                        root=rightrotation(g,root);
                }
                /*Performs the Zig-zag step when x's is left and x's parent is right*/
                else if(x==p->left&&p==g->right)
                {
                        root=rightrotation(p,root);
                        root=leftrotation(g,root);
                }
                splay(x, root);
        }
}
struct node *rightrotation(struct node *p,struct node *root)
{
        struct node *x;
        x = p->left;
        p->left = x->right;
        if (x->right!=NULL) x->right->parent = p;
        x->right = p;
        if (p->parent!=NULL)
                if(p==p->parent->right) p->parent->right=x;
                else
                         p->parent->left=x;
        x->parent = p->parent;
        p->parent = x;
        if (p==root)
                return x;
        else 
                return root;
}
struct node *leftrotation(struct node *p,struct node *root)
{
        struct node *x;
        x = p->right;
        p->right = x->left;
        if (x->left!=NULL) x->left->parent = p;
        x->left = p;
        if (p->parent!=NULL)
                if (p==p->parent->left) p->parent->left=x;
                else
                         p->parent->right=x;
        x->parent = p->parent;
        p->parent = x;
        if(p==root) 
                return x;
        else
                return root;
}
struct node *insert(struct node *p,int value)
{
        struct node *temp1,*temp2,*par,*x;
        if(p == NULL)
        {
                p=(struct node *)malloc(sizeof(struct node));
                if(p != NULL)
                {
                        p->data = value;
                        p->parent = NULL;
                        p->left = NULL;
                        p->right = NULL;
                }
                else
                {
                        printf("No memory is allocated\n");
                        exit(0);
                }
                return(p);
        } //the case 2 says that we must splay newly inserted node to root
        else
        {
                        temp2 = p;
                        while(temp2 != NULL)
                        {
                                temp1 = temp2;
                                if(temp2->data > value)
                                        temp2 = temp2->left;
                                else if(temp2->data < value)
                                        temp2 = temp2->right;
                                else
                                        if(temp2->data == value)
                                                return temp2;
                        }
                        if(temp1->data > value)
                        {
                                par = temp1;//temp1 having the parent address,so that's it 
                                temp1->left = (struct node *)malloc(sizeof(struct node));
                                temp1= temp1->left;
                                if(temp1 != NULL)
                                {
                                        temp1->data = value;
                                        temp1->parent = par;//store the parent address.
                                        temp1->left = NULL;
                                        temp1->right = NULL;
                                }
                                else
                                {
                                        printf("No memory is allocated\n");
                                        exit(0);
                                }
                        }
                        else
                        {
                                par = temp1;//temp1 having the parent node address.
                                temp1->right = (struct node *)malloc(sizeof(struct node));
                                temp1 = temp1->right;
                                if(temp1 != NULL)
                                {
                                        temp1->data = value;
                                        temp1->parent = par;//store the parent address
                                        temp1->left = NULL;
                                        temp1->right = NULL;
                                }
                                else
                                {
                                        printf("No memory is allocated\n");
                                        exit(0);
                                }
                        }
        }
        splay(temp1,p);//temp1 will be new root after splaying
        return (temp1);
}
struct node *inorder(struct node *p)
{
        if(p != NULL)
        {
                inorder(p->left);
                printf("CURRENT %d\t",p->data);
                printf("LEFT %d\t",data_print(p->left));
                printf("PARENT %d\t",data_print(p->parent));
                printf("RIGHT %d\t\n",data_print(p->right));
                inorder(p->right);
        }
}
struct node *delete(struct node *p,int value)
{
        struct node *x,*y,*p1;
        struct node *root;
        struct node *s;
        root = p;
        x = lookup(p,value);
        if(x->data == value)
        {       //if the deleted element is leaf
                if((x->left == NULL) && (x->right == NULL))
                {
                        y = x->parent;
                        if(x ==(x->parent->right)) 
                                y->right = NULL;
                        else 
                                y->left = NULL;
                        free(x);
                }
                //if deleted element having left child only
                else if((x->left != NULL) &&(x->right == NULL))
                {
                        if(x == (x->parent->left))
                        {
                                y = x->parent;
                                x->left->parent = y;
                                y->left = x->left;
                                free(x);
                        }
                        else
                        {
                                y = x->parent;
                                x->left->parent = y;
                                y->right = x->left;
                                free(x);
                        }
                }
                //if deleted element having right child only
                else if((x->left == NULL) && (x->right != NULL))
                {
                        if(x == (x->parent->left))
                        {
                                y = x->parent;
                                x->right->parent = y;
                                y->left = x->right;
                                free(x);
                        }
                        else
                        {
                                y = x->parent;
                                x->right->parent = y;
                                y->right = x->right;
                                free(x);
                        }
                }
                //if the deleted element having two children
                else if((x->left != NULL) && (x->right != NULL))
                {
                        if(x == (x->parent->left))
                        {
                                s = sucessor(x);
                                if(s != x->right)
                                {
                                        y = s->parent;
                                        if(s->right != NULL)
                                        {
                                                s->right->parent = y;
                                                y->left = s->right;
                                        }
                                        else y->left = NULL;
                                        s->parent = x->parent;
                                        x->right->parent = s;
                                        x->left->parent = s;
                                        s->right = x->right;
                                        s->left = x->left;
                                        x->parent->left = s;
                                }
                                else
                                {
                                        y = s;
                                        s->parent = x->parent;
                                        x->left->parent = s;
                                        s->left = x->left;
                                        x->parent->left = s;
                                }
                                free(x);
                        }
                        else if(x == (x->parent->right))
                        {
                                s = sucessor(x);
                                if(s != x->right)
                                {
                                        y = s->parent;
                                        if(s->right != NULL)
                                        {
                                                s->right->parent = y;
                                                y->left = s->right;
                                        }
                                        else y->left = NULL;
                                        s->parent = x->parent;
                                        x->right->parent = s;
                                        x->left->parent = s;
                                        s->right = x->right;
                                        s->left = x->left;
                                        x->parent->right = s;
                                }
                                else
                                {
                                        y = s;
                                        s->parent = x->parent;
                                        x->left->parent = s;
                                        s->left = x->left;
                                        x->parent->right = s;
                                }
                                free(x);
                        }
 
                }
                splay(y,root);
        }
        else
        {
                splay(x,root);
        }
}
struct node *sucessor(struct node *x)
{
        struct node *temp,*temp2;
        temp=temp2=x->right;
        while(temp != NULL)
        {
                temp2 = temp;
                temp = temp->left;
        }
        return temp2;
}
//p is a root element of the tree
struct node *lookup(struct node *p,int value)
{
        struct node *temp1,*temp2;
        if(p != NULL)
        {
                temp1 = p;
                while(temp1 != NULL)
                {
                        temp2 = temp1;
                        if(temp1->data > value)
                                temp1 = temp1->left;
                        else if(temp1->data < value)
                                temp1 = temp1->right;
                        else
                                        return temp1;
                }
                return temp2;
        }
        else
        {
                printf("NO element in the tree\n");
                exit(0);
        }
}
struct node *search(struct node *p,int value)
{
        struct node *x,*root;
        root = p;
        x = lookup(p,value);
        if(x->data == value)
        {
                printf("Inside search if\n");
                splay(x,root);
        }
        else
        {
                printf("Inside search else\n");
                splay(x,root);
        }
}
main()
{
        struct node *root;//the root element
        struct node *x;//x is which element will come to root.
        int i;
        root = NULL;
        int choice = 0;
        int ele;
        while(1)
        {
                printf("\n\n 1.Insert");
                printf("\n\n 2.Delete");
                printf("\n\n 3.Search");
                printf("\n\n 4.Display\n");
                printf("\n\n Enter your choice:");
                scanf("%d",&choice);
                if(choice==5)
                        exit(0);
                switch(choice)
                {
                        case 1:
                                printf("\n\n Enter the element to be inserted:");
                                scanf("%d",&ele);
                                x = insert(root,ele);
                                if(root != NULL)
                                {
                                        splay(x,root);
                                }
                                root = x;
                                break;
                        case 2:
                                if(root == NULL)
                                {
                                        printf("\n Empty tree...");
                                        continue;
                                }
                                printf("\n\n Enter the element to be delete:");
                                scanf("%d",&ele);
                                root = delete(root,ele);
                                break;
                        case 3:
                                printf("Enter the element to be search\n");
                                scanf("%d",&ele);
                                x = lookup(root,ele);
                                        splay(x,root);
                                root = x;
                                break;
                        case 4:
                                printf("The elements are\n");
                                inorder(root);
                                break;
                        default:
                                printf("Wrong choice\n");
                                break;
                }
        }
}
int data_print(struct node *x)
{
        if ( x==NULL )
                return 0;
        else
                return x->data;
}
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.