Comparision of binary trees, balance.

This is a discussion on Comparision of binary trees, balance. within the C Programming forums, part of the General Programming Boards category; Hi! I got this little assignment on fundamentals of computer programming. Task is about creating two binary trees (simple binary ...

  1. #1
    Registered User
    Join Date
    Jan 2012
    Posts
    29

    Comparision of binary trees, balance.

    Hi! I got this little assignment on fundamentals of computer programming. Task is about creating two binary trees (simple binary tree and balanced one) and comparision of it. I've got a whole code. Everything went perfect until I added balance function.

    Code:
    #include <stdio.h>#include <minmax.h>
    
    
    struct tree
    {
        int val;
        struct tree *left;
        struct tree *right;
    };
    
    
    typedef struct tree one;
    typedef struct tree two;
    
    
    int insert(one **, int);
    //void inserttwo(two **, int);
    int find(one *, int);
    int height(one *);
    int leftbalance(two *);
    int rightbalance(two *);
    void DSWbalance(two *);
    
    
    int main()
    {
        int choice, value, val, c, d;
        one *headone;
        two *headtwo;
        headone=(one*)malloc(sizeof(one));
        headtwo=(two*)malloc(sizeof(two));
    
    
        printf("Making a tree. Enter a value:\n");
        scanf("%d",&val);
        headone->val=val;
        headtwo->val=val;
        headone->left=NULL;
        headone->right=NULL;
        headtwo->left=NULL;
        headtwo->right=NULL;
    
    
        do
        {
            system("cls");
            printf("1. Enter a value.\n2. Find height.\n3. Find element.\n4. Rotate left.\n5. Rotate right.\n6. Balance.\n9. EXIT.\n\n");
            scanf("%d",&choice);
            switch(choice)
            {
                case 1:
                    system("cls");
                    printf("Enter a value: ");
                    scanf("%d", &value);                
                    if(insert(&headone, value)==1)
                    {
                        printf("Value exists! Press any key to continue.\n");
                    }
                    else
                    {
                        insert(&headtwo, value);
                        DSWbalance(headtwo);
                        printf("Done. Press any key to continue.");
                    }
                    getchar();
                    getchar();
                    break;
    
    
                case 2:
                    system("cls");
                    printf("Heigh of a binary tree is %d and balanced one %d",height(headone),height(headtwo));
                    getchar();
                    getchar();
                    break;
    
    
                case 3:
                    system("cls");
                    printf("Enter a value: ");
                    scanf("%d", &value);
                    printf("found in a first tree with %d comparision.\n",find(headone, value));
                    printf("found in a second tree with %d comparision.",find(headtwo, value));
                    getchar();
                    getchar();
                    break;
                case 4:
                    system("cls");
                    leftrotate(headtwo);
                
                case 5:
                    system("cls");
                    rightrotate(headtwo);
    
    
                case 6:
                    system("cls");
                    DSWbalance(headtwo);
            
                default:
                    break;
            }
        }while(choice!=9);
    }
    
    
    int insert(one **p, int x)
    {
        static int d;
        d=0;
        if((*p)==NULL)
        {
            (*p)=(one*)malloc(sizeof(one));
            (*p)->val=x;
            (*p)->left=NULL;
            (*p)->right=NULL;
        }
        else
        {
            if((*p)->val>x)
                insert(&(*p)->left, x);
            else if((*p)->val<x)
                insert(&(*p)->right, x);
            else
            {
                d=1;
            }
        }
        return d;
    }
    
    
    int find(one *p, int x)
    {
        int c=0;
        while(p!=NULL)
        {
            if(p->val==x)
            {
                printf("Element %d ",x);
                c++;
                return c;
                getchar();
            }
            else if(p->val<x)
            {
                p=p->right;
                c++;
            }
            else
            {
                p=p->left;
                c++;
            }
        }
        return c;
    }
    
    
    /*AVL*/
    
    
    int height(two *p)    
    {
        if(p==0)
            return 0;
        return 1 + max(height(p->left),height(p->right));
    }
    
    
    int leftrotate(two *p) 
    {  
        struct tree *nd;
        int data;
        if(p==0 || p->right==0)
            return 0; //no right node
    
    
        nd=p->right; 
        p->right=nd->right; //move node
        nd->right=nd->left;
        nd->left=p->left;
        p->left=nd;
    
    
        data=p->val;  
        p->val=nd->val; 
        nd->val=data;
        return 1;
    }
    
    
    int rightrotate(two *p)
    {
        struct tree *nd;
        int data;
        if(p==0 || p->left==0)
            return 0; //no left node
    
    
        nd=p->left;
        p->left=nd->left;
        nd->left=nd->right;
        nd->right=p->right;
        p->right=nd;
    
    
        data=p->val;
        p->val=nd->val;
        nd->val=data;
        return 1;
    }
    
    
    void DSWbalance(two *p)
    {  
        struct tree *q;  
        int i,k,nodecount; 
        
        for(q=p,nodecount=0;q!=0;q=q->right,++nodecount) //spine
            while(rightrotate(p)==1)
    
    
        for(i=nodecount/2;i>0;i/=2)
            for(q=p,k=0;k<i;++k,q=q->right) //balance
                leftrotate(p);
    }
    The funny thing is that neither left nor right rotation works now, they did before I added balance, what's more, when I hide balance in comment /* */ rotation works again.

    Can someone point my mistakes?
    Last edited by blunt; 02-15-2012 at 10:16 AM.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Can balance() make another node the root of the tree?
    If it can, your code has no way of returning the new root.

    Two typedef's for the same thing do not make for very readable code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Two typedef's for the same thing do not make for very readable code.
    Ye, it's already changed to
    Code:
    typedef struct tree
    {    
        int val;    
        struct tree *left;   
        struct tree *right;
    }one,two;
    If it's about a first part of Your post I'm not sure.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    Code:
                case 6:
                    system("cls");
                    printf("Root before=%p\n", (void*)headtwo);
                    DSWbalance(headtwo);
                    printf("Root after=%p\n", (void*)headtwo);
    If you're expecting a different answer after balancing, it's not going to happen with the code you have.

    At the very least, you need something like
    headtwo = DSWbalance(headtwo);

    where the function returns the (possibly changed) root node.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Hmm... when I do so, new root is 0, and height of the balanced tree is 0 as well, so still something is not correct right?

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    That's not an AVL tree you're impementing there. An AVL tree stays balanced permanently and each insert involves up to two rotations, no more. Balancing can't be an afterthought for that, it needs to be an integral part of the insertion itself.
    You're doing something closer to a Scapegoat tree. That rebalances the whole tree periodically. However what you have is rather broken as it only attempts to balance the outermost level of nodes and doesn't change the head. Listen to Salem.
    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"

  7. #7
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Yes I know it's not AVL. That was my first concept (so i.e. comment You see it's what's left), but I changed my mind 'cause I'm can't manage AVL. All I want now is two simple binary trees and one of them should be balanced with DSW algorithm.

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    And by the way, when Salem complained about the typedefs he meant that one way to declare a tree would be to write this way:
    one aTree;

    Or this way: two anotherTree;

    The same type of thing has two names and that is confusing.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    The comment in your code says /*AVL*/, which is what I took notice of.
    I didn't remember hearing of the DSW algorithm before so I looked it up and found this: One-Time Binary Search Tree Balancing
    It turns out that its basically the same as what I used for my Scapegoat tree. I had unknowingly reinvented it. My version is slightly more complex than in the above link, but more efficient. Thanks for helping me put a name to it.

    Your code however does not implement the DSW algorithm. You can tell that you're trying to, but it's not right and missing several key parts. As I stated earlier, your code only attempts to balance the outermost level (recursion is missing), but worse still, before it does that it does not fully flatten the list. Your rotates also look rather suspect. You should not be messing with the val at each node at all. The only thing that it should change is the links between nodes.
    So I guess now we just need to help you understand these mistakes. Please ask further questions.
    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"

  10. #10
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    I changed rotation a bit, so it's now:
    Code:
    int leftrotate(two *p) //rotates once
    {      struct tree *tmp;    int data;
        if(p==0 || p->right==0)
            return 0; //no right node
        tmp=p->right;
         p->right=tmp->right; //move node
        tmp->left=p;
        p=tmp;
        return 1;
    }
    
    int rightrotate(two *p) //rotates once
    {
        struct tree *tmp;
        int data;
        if(p==0 || p->left==0)
            return 0; //no left node
        tmp=p->left;
         p->left=tmp->left; //move node
        tmp->right=p;
        p=tmp;
        return 1;
    }
    
    int DSWbalance(two *p)
    {
          struct tree *q;
          int i,k,nodecount;
         for(q=p,nodecount=0;q!=0;q=q->right,++nodecount) //creating a spine with rightrotate
            while(rightrotate(p)==1);
    
         for(i=nodecount/2;i>0;i/=2)
            for(q=p,k=0;kleft) //balance because of leftrotating moving back every second node
                leftrotate(p);
         return 0;
    }
    Comments say what I see and according to me it seems to be okey. But it's not. So, which part is wrong? It's hard to find a mistake when you're convinced that your attempts are done perfectly.
    Last edited by blunt; 02-16-2012 at 05:19 AM.

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    So, which part is wrong? It's hard to find a mistake when you're convinced that your attempts are done perfectly.
    You could be otherwise completely right and none of the changes will stick. In C, absolutely everything is passed by value, the only difference is with pointers you pass in a location explicitly. If you want to change a pointer from elsewhere in another function, either you pass in a pointer to that pointer, or return the new pointer to be reassigned.

  12. #12
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    I must admit pointers are my pain in the ass. In my previous assignment I had like 1000 lines of code and all I did was avoiding pointers (I had 0 of them). But this time is no way to accomplish my task without them. I ensure You I've read lots of texts about pointers but still, when You say 'pointer to a pointer', it's abstraction to me. I may need a simple example to understand this case...

  13. #13
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,438
    To change an int in a function and have that change be visible in the calling funciton, you must pass a pointer to the int, like so:
    Code:
    void foo(int x)
    {
        x = 42;
    }
    
    void bar(int *x)
    {
        *x = 42;
    }
    
    int baz(void)
    {
        return 123;
    }
    
    int main(void)
    {
        int x = 17;
        printf("x = %d\n", x);
        foo(x);    // if i just pass in x, i pass a copy of it, so the x in main doesn't change
        printf("after foo, no change: x = %d\n", x);
        bar(&x);  // pass in the address, which gives a pointer to x
        printf("after bar, x is changed: x = %d\n", x);
        x = baz();  // return a new value for x
        printf("after baz, x is changed: x = %d\n", x);
        return 0;
    }
    You've probably gone over that in class at some point. It's really no different with pointers. To change a pointer in the calling function, you must pass a pointer to that point to a function like we did with bar, or return a new value for the pointer, like we did with baz:
    Code:
    void allocate_foo(struct foo **f)  // here, f is a pointer to a pointer
    {
        *f = malloc(sizeof(struct foo));  // dereference it to get just a pointer, and assign to that pointer
    }
    
    struct foo *another_allocate_foo(void)
    {
        return malloc(sizeof(struct foo));
    }
    
    int main(void)
    {
        struct foo *f = NULL;
        // this is one way to allocate memory for f
        allocate_foo(&f);  // f is a pointer, so taking it's address with & gives a pointer to a pointer
        free(f);
        // this is another way
        f = another_allocate_foo();
        free(f);
        return 0;
    }

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,292
    You're almost there, but one mistake. Your rotation isn't quite right yet:
    Code:
         p->right=tmp->right; //move node
    The node that should change parent is the node that is between the two nodes that rotate. tmp->right is off to the right of both nodes, and in fact after that function is executed, two nodes point to tmp->right and none point to what was tmp->left.
    I suggest going through it step by step on paper.
    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"

  15. #15
    Registered User
    Join Date
    Jan 2012
    Posts
    29
    Code:
    p->right=tmp->right;
    Right my bad, obviously, there should be
    @edit: No, I'd rather kill myself than finish that project. Now rotations doesn't work...

    Code:
    p->right=tmp->left;
    anduril462, that was a great lesson! I will definitely save it to notepad but now I must figure out how does it help me PS. Excuse me for being so dumb
    Last edited by blunt; 02-16-2012 at 01:52 PM.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting From Binary Tree to Threaded Binary Trees
    By elton_fan in forum C Programming
    Replies: 15
    Last Post: 11-08-2007, 10:41 PM
  2. binary tree balance problem
    By overkill in forum C++ Programming
    Replies: 5
    Last Post: 08-17-2006, 05:52 AM
  3. Binary Trees MINI MAXING, probability trees
    By curlious in forum General AI Programming
    Replies: 3
    Last Post: 09-30-2005, 10:57 AM
  4. balance binary tree
    By xddxogm3 in forum C++ Programming
    Replies: 6
    Last Post: 12-07-2003, 04:33 PM
  5. traversing binary trees or partial trees
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-05-2001, 08:19 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21