Comparision of binary trees, balance.

**blunt** · 02-15-2012

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?

**Salem** · 02-15-2012

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.

**blunt** · 02-15-2012

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.

**Salem** · 02-15-2012

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.

**blunt** · 02-15-2012

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?

**iMalc** · 02-15-2012

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.

**blunt** · 02-15-2012

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.

**whiteflags** · 02-15-2012

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.

**iMalc** · 02-16-2012

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.

**blunt** · 02-16-2012

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.

**whiteflags** · 02-16-2012

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.

**blunt** · 02-16-2012

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...

**anduril462** · 02-16-2012

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;
}

**iMalc** · 02-16-2012

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.

**blunt** · 02-16-2012

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

Thread: Comparision of binary trees, balance.

Thread Tools

Search Thread

Display

Comparision of binary trees, balance.

Similar Threads

Converting From Binary Tree to Threaded Binary Trees

binary tree balance problem

Binary Trees MINI MAXING, probability trees

balance binary tree

traversing binary trees or partial trees

Tags for this Thread