Thread: Splay Tree problem

  1. #1
    Registered User
    Join Date
    Mar 2012
    Posts
    19

    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
    Last edited by ilerleartik; 12-19-2012 at 01:39 PM.

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,909
    Quote Originally Posted by ilerleartik View Post
    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.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Mar 2012
    Posts
    19
    Thanks for your replies.
    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..

    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.

    Thanks for your replies again;
    Happy codings

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with my Rb tree
    By Nyah Check in forum C Programming
    Replies: 5
    Last Post: 08-30-2012, 10:18 PM
  2. How to destroy a splay tree?
    By RichSelian in forum C Programming
    Replies: 4
    Last Post: 04-19-2011, 01:25 PM
  3. Binary Tree Problem
    By noodle24 in forum C++ Programming
    Replies: 2
    Last Post: 04-16-2007, 02:20 PM
  4. Tree Problem
    By recluse in forum C Programming
    Replies: 36
    Last Post: 12-04-2004, 03:06 PM