# Thread: Comparision of binary trees, balance.

1. 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. 2. 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. 3. Nailed it! 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. 4. 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. 5. 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.) 6. 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. 7. 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 8. 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? 9. 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()? 10. 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. 11. 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. 12. 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. 13. I'm thinking of something like:

Code:
```struct tree *mytree;
/*code code*/

int DSWbalance(struct tree *root)
{
/*algorithm*/
return x;
}```
What should be x? Root? 14. It should be the root of the balanced tree. Also notice that the return type is not int. 15. So, in this example it will be?

Code:
```intDSWbalance(structtree *root){
/*algorithm*/
return root;
}
```

Return type should/must be int? Popular pages Recent additions balance, bst, rotation, tree 