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.