I have a code that gets the number and inserts into a splay tree. You know, when you insert a key into this tree, this key will be splayed and will be taken to root by doing zig-zig or zig-zag processes.
Here is the code which is related with splay tree creation;
Now I want to change this code, and I want to splay this tree once when any insertion occurs. I mean, when you insert a key, there will be only "once" zig-zag or zig-zig movement, we do not expect our key to reach to root. Only one...Code: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){splrot_cnt++;
root=rightrotation(root,root);}
else{splrot_cnt++;
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)
{ splrot_cnt++;splrot_cnt++;
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)
{ splrot_cnt++;splrot_cnt++;
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)
{ splrot_cnt++;splrot_cnt++;
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)
{ splrot_cnt++;splrot_cnt++;
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;
p->occ=1;
}
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){splcmp_cnt++;
temp2 = temp2->left;}
else if(temp2->data < value){splcmp_cnt++;
temp2 = temp2->right;}
else if(temp2->data == value)
{ splcmp_cnt++;temp2->occ++;return temp2;}
}
par = temp1;//temp1 having the parent
if(temp1->data > value)
{
temp1->left = (struct node *)malloc(sizeof(struct node));
temp1= temp1->left;
if(temp1 != NULL)
{
temp1->data = value;
temp1->occ=1;
temp1->parent = par;//store the parent address.
temp1->left = NULL;
temp1->right = NULL;
}
else
{
printf("No memory is allocated\n");
exit(0);
}
}
else
{
temp1->right = (struct node *)malloc(sizeof(struct node));
temp1 = temp1->right;
if(temp1 != NULL)
{
temp1->data = value;
temp1->occ=1;
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 // not necessary , already done in the main function
return (temp1);
}
I just removed the line from splay function
so, there wont be any recursive calls, and I will make the program to do only one zig-zig or zig-zag. At least, I think so; but somehow, any problem occurs and some nodes loses each other. I couldn't find where the problem is. How can I do what I want by changing my code?Code:splay function()
{
...
splay(x, root); //This is removed
}
Maybe you need this piece of code, which resides in main function and insert function called
P.S. Some int counter variables exist in my codes, just ignore them.Code:printf("\n\n Enter the element to be inserted:");
scanf("%d",&ele);
x = insert(root,ele);
if(root != NULL)
{
splay(x,root);
}
root = x;
Thanks