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?

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.

Quote:

---

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.

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.

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?

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.

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.

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.

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.

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

Quote:

---

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.

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

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

---

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.

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 :tongue:

Quote:

---

Originally Posted by blunt

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

---

That edit is correct. With that one line change, your left rotation is 100% correct. You need to make the corresponding change for the right rotation as well.
Of course neither of these will appear to work correctly until you have a way of modifying the head. E.g. you need to pass your pointers by pointer, so that you can modify them.

If this were C++ then you'd use references in which case you could add an "&" and you'd be done.

Code:

---

int leftrotate(two **p) { 
        struct tree *tmp;
        int data;
        if(*p==0 || (*p)->right==0)
                return 0; //no right node


        tmp=(*p)->right;
        (*p)->right=tmp->left; //move node
        tmp->left=(*p);
        (*p)=tmp;
        return 1;
}

---

Seem to be okey, not sure of it.

Nailed it! :D you can remove the unused variable too though

How's the rest of it coming? Did you check out that link I posted earlier? It had an implementation of exactly the algorithm you wanted.

Yes I did, and it's confusing. All I need now from that article is vine_to_tree and tree_to_vine functions right? It's probably because of C/C++ differences, but there are some things I don't get. So:

Code:

---

void DSW::tree_to_vine ( BasePtr root, int &size )
{
    BasePtr vineTail, remainder, tempPtr;
    vineTail = root;
    remainder = vineTail->Right;
    size = 0;
    while ( remainder != NULL )
    {//If no leftward subtree, move rightward
        if ( remainder->Left == NULL )
        {
            vineTail = remainder;
            remainder = remainder->Right;
            size++;
        }    //else eliminate the leftward subtree by rotations
        else  // Rightward rotation
      {
            tempPtr = remainder->Left;
            remainder->Left = tempPtr->Right;
            tempPtr->Right = remainder;
            remainder = tempPtr;
            vineTail->Right = tempPtr;
        }
  }
}

---

RED: 'Size' just counts nodes right? Like in my balance function variable 'nodecount'. So why does the function take &size, then sets it to NULL?
GREEN: It's rightward rotation so I could use here 'rightrotate()' right?T here are also 2 opposite functions, vine_to_tree, but maybe I will fully understand them when I understand this one above.

But let's back to my balance function. It works (it should at least :)) similarly.

Code:

---

int 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;kleft) //balance
            leftrotate(&p);}

---

But effect is the same like in case of rotation before I've straighten up pointers problem. But why? Rotations do all damn job.

Firstly the size variable is not set to null, it is set to zero. NULL is a pointer constant. Or at least it should be, which is why in later editions of the C++ standard they introduced the type strict nullptr. Anyway, from now on, say zero when you are talking about the number zero and not a pointer constant. To get to your actual question, size plays a huge role in the other function, vine_to_tree. The size variable is basically the height of the tree that the function makes. size is a reference because in this implementation, the function needs to give size back to the caller.

Yes you can use rightrotate(). The code that you are referencing follows the original description of the algorithm in the paper. Yours is only differently implemented.

You have to keep in mind that rebalancing changes the entire tree and this means that the root node can change too. So you should return the whole tree back to the caller. (Go back to your pointers lesson.)

I'm beginning to think I might have been wrong about your spine part not flattening the list fully, and the balance part might not be that far off also.

Currently it wont even compile though because the for-loop is missing one of its semicolons and I have no idea where kleft comes from.

Ah that's my bad, I must have missclicked something: that's what I have:

Code:

---

int DSWbalance(two *p){ 
    struct tree *q;
    int i,k=0,nodecount;
   
    for(q=p,nodecount=0;q!=0;q=q->right) //spine
    {
        while(rightrotate(&p)==1)
            nodecount++;
    }
    for(i=nodecount/2;i>0;i/=2)
        for(q=p,k;k<i;++k,q=q->left) //balance
            leftrotate(&p);
}

---

This part is in 'constant motion' so I don't even remember the first concept, having new ideas makes me confused about what's what now, what's wrong etc

Well if you don't know what to ask it's really hard to help you. Did you understand what I said in my last post?

Understood but my mind cannot convert it into C. I think I'm to sure what's mine. My balance function should contain return balance()?

I need you to look from a birds eye.

Imagine I want to use your binary trees because they are the best trees ever. I need to balance my tree, so I call DSWbalance.

Code:

---

struct tree* mytree;
/* I build my tree after this line and need to balance it
 * before I start searching for nodes, based on human input.
 */
DSWbalance(mytree);

---

If DSWbalance changes what mytree points to, how are you going to return the changes to me? You should know two ways because we showed them to you before. Plus we already explained that pointers are passed by value. The mytree that I gave you gives you access to the nodes it points to - so you balance mytree - but you have to give me a way to update my pointer's value, too. (That is the pointer I use when I use your implementation of trees.)

This would let you verify if the algorithm you implemented works, since you can inspect the same tree you just balanced from the new root.

Quote:

---

If DSWbalance changes what mytree points to, how are you going to return the changes to me?

---

What I have in mind is this: x=x+y (x is from now old x plus change)

My line of thought goes like this:
1. My tree points to sth, DSW changes what my tree point to -> DSW changes sth.
2. Now I need to return it to You. So I do sth like root=DSW(root) (x-root, y-change is function on x). If I'm correct, that was 1st way.
3. Second way was using extra pointer?

Sorry for being so unaware what's going on, but it's probably of my deadline or language barrier, I'll buy more patience.

Good. You need to pick one of the ways and make it that way.

Now imagine that you just want to confirm that DSWbalance works. You create a tree and pass it to DSWbalance, and the function gives you back the changes to the tree. To confirm that DSWbalance works correctly, you could then follow all the links and notice the shape of the tree. If the shape of the tree is not what it is supposed to be, there are more mistakes in DSWbalance and you need to investigate. Picking a way to return the changes in the tree makes this all possible.

I'm thinking of something like:

Code:

---

struct tree *mytree;
/*code code*/
head=DSWbalance(head);

int DSWbalance(struct tree *root)
{
/*algorithm*/
return x;
}

---

What should be x? Root?

It should be the root of the balanced tree. Also notice that the return type is not int.

So, in this example it will be?

Code:

---

intDSWbalance(structtree *root)

{
/*algorithm*/
return root;
}

---

Return type should/must be int?

No, the return type should be struct tree *:

Code:

---

struct tree *DSWbalance(struct tree *root)
{
    /* algorithm */

    return root;  // this is the "new" root, since rotations may alter the root of the tree
}

---

Ohhh god, I'm so stupid. I've never considered that function can be something else than void or int :o

Although not everything is okey.

Code:

---

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");
                    getchar();
                    getchar();
                }
                else
                {
                    insert(&headtwo, value);
                    headtwo=DSWbalance(headtwo); //when this part is 'on' program doesn't give my errors, but it looks like algorithm is wrong, when I print a result of it I have only one element in a tree
                }
                break;

---

If red part is off, and I put into my tree 5 values, ie 5, 4, 3, 2, 1, then I perform balancing I have error of access violation. I checked step-by-step what's going on inside of it. First part (creating a spine) looks okey. Not so sure of second part. Problem occurs when 'k' reaches 'i'.

Code:

---

struct tree *DSWbalance(struct tree *root){ 
    struct tree *p;
    int nodecount;
    int i;
   
    for(p=root,nodecount=0;p!=0;p=p->right,++nodecount) //spine
        {
            while(rightrotate(&p)==1) { }
        }
   
    for(i=nodecount/2; i>0; i/=2 ) //balance
        {
            int k;
            for(p=root,k=0;k<i;++k,p=p->right)
                leftrotate(&p);
        }
    return root;
   
}

---