# Splay Tree problem

• 12-19-2012
ilerleartik
Splay Tree problem
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;

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); }```
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...

I just removed the line from splay function
Code:

```splay function() { ... splay(x, root); //This is removed }```
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?

Maybe you need this piece of code, which resides in main function and insert function called

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;```
P.S. Some int counter variables exist in my codes, just ignore them.

Thanks
• 12-19-2012
anduril462
Quote:

Originally Posted by ilerleartik
How can I do what I want by changing my code?

[rant]
Ugh, lines like that bug me. People who say "my code" when it's pretty obvious that they don't understand it well enough for it to be their code. Furthermore, the Wikipedia license is pretty open, but technically stipulates you must attribute the work to it's original creator. Why not just say "I found this code on Wikipedia and am trying to alter it to do X"? Heck, you already found it on the web, give us a link too, we might be able to tell you that the author who wrote it is a complete moron and you shouldn't bother trying to learn from them?
[/rant]

Okay, so you copied this code from Wikipedia (http://en.wikipedia.org/wiki/Splay_t..._in_C_language). Did you read the comment at the end:
Quote:

Originally Posted by Wikipedia - Splay tree
/*some suggestion this code is not fully functional for example
if you have inserted some elements then try to delete root then it may not work
because we are calling right and left child of a null value(parent of root)
which is not allowed and will give segmentation fault

Also for inserting second element because of splaying twice(once in insert and one in main)
will give error So I have made those changes but mainly in my cpp( c plus plus file) file,
but I guess wiki will itself look into this and made these changes */

Are you sure the tree is even being built correctly? The author acknowledges a problem when inserting the second element element, which honestly makes me wonder just how well-tested the whole thing is. Have you printed the tree after each insertion to verify that every node is there and in the correct place?

Also, you don't provide us with enough information to test and run this code ourselves, to replicate and find your problem. How do you know it loses the nodes? Which node(s) does it lose? The one you are trying to rotate up the tree? It's parent or child(ren)? Some other node all together? Is it only on when you do zig-zig, or a zig-zag, or both? I think you get the point, it would help us immensely if you provided detailed information on your problem. What is the full source code you are using (i.e. the one containing all modifications of the Wikipedia code)? It helps us if we can just copy paste your code exactly and compile and run it ourselves. What exact input did you give the program?

Lastly, why not write a splay tree yourself, so you'll actually learn how to implement it? This will also result in much better knowledge of the code (since you actually wrote it yourself), and make tracking down issues like this much easier.
• 12-20-2012
iMalc
That implementation is horrible, about 3 times longer than mine, does far more comparisons, and has the totally unnecessary parent pointer to boot. Gees that's awful, I can't believe anyone put that up on Wikipedia. Don't copy that implementation! It's far better to the allocate the node up front, insert it recursively, and then splay the tree on the way back up from the recursive calls. Ridiculously simple by comparison.
Splay trees are one of my favourite data structures. They are so underused and undervalued. They make for an extremely fast and adpative sorting algorithm, for example. Looks like I'm going to have to donate some of my code to Wikipedia again.
• 12-20-2012
ilerleartik
Quote:

Ugh, lines like that bug me. People who say "my code" when it's pretty obvious that they don't understand it well enough for it to be their code. Furthermore, the Wikipedia license is pretty open, but technically stipulates you must attribute the work to it's original creator. Why not just say "I found this code on Wikipedia and am trying to alter it to do X"? Heck, you already found it on the web, give us a link too, we might be able to tell you that the author who wrote it is a complete moron and you shouldn't bother trying to learn from them?
It might be sometimes hard to ask something in this forum. When I say, "Hey I found this on Web, and I want to change it", then people just say "Grr, do not copy and paste, and effort on your own. If you copy and paste, it is very ordinary not to understand the code"... To avoid of this, When I lie " Hey my code is not working well", then people just say what you say :) Anyway, when I copy and paste it into my compiler, it is asummed mine copied from somewhere, from this time on.

And also I really do not want to write splay tree codes from very beginning; as I do not invent something new..

Quote:

That implementation is horrible, about 3 times longer than mine, does far more comparisons, and has the totally unnecessary parent pointer to boot. Gees that's awful, I can't believe anyone put that up on Wikipedia. Don't copy that implementation! It's far better to the allocate the node up front, insert it recursively, and then splay the tree on the way back up from the recursive calls. Ridiculously simple by comparison.
Splay trees are one of my favourite data structures. They are so underused and undervalued. They make for an extremely fast and adpative sorting algorithm, for example. Looks like I'm going to have to donate some of my code to Wikipedia again.
I'm really looking forward to see your codes on wikipedia or somewhere else. This will certainly work for so many people, and really appreciate it. ;Tree algorithms and codes are always preferred by everyone, and re-coding seems very cumbersome.

I also fixed my problem. No nodes lose each other, I was wrong. When I remove splay function, it does work well!; but when I displayed, it just mis-displayed as display function runs with splay-until-root algorithm. I changed something a little bit, and I see that no nodes lose each other.