Rotations doesnt work, no idea why:/ been stuck for days with this
Code:
void skirtumas(structnode *tree){
if(tree ->left){
LEFT = height(tree -> left);
printf("left\n");
}
else {LEFT = 0;}
if(tree ->right){
RIGHT = height(tree -> right);
printf("right\n");
}
else{RIGHT = 0;}
if(LEFT >RIGHT){
difference =LEFT - RIGHT;
}
else{
difference =RIGHT - LEFT;
}
}
int height(struct node*tree){
int r = 0, l = 0;
if(tree->left)l=height(tree->left);
if(tree->right)r=height(tree->right);
if(l > r){
return(l+1);
}else{
return(r+1);
}
}
struct node*balansas(struct node *tree)
{
struct node *temp;
struct node *temp2;
struct node *temp3;
skirtumas(tree);
if(difference >1)
{
if(RIGHT >LEFT)
{
skirtumas(tree -> right);
if(LEFT >RIGHT)// RIGHT subtree is LEFT heavy, double rotation
{
temp3 =tree -> right;
temp3-> left = NULL;
temp3-> left = tree -> right -> left ->right;
temp2 =tree -> right -> left;
temp2-> right = NULL;
temp2-> right = temp3;
temp =tree;
temp ->right = NULL;
temp ->right = temp2;
tree =NULL;
tree =temp;
temp =NULL;
temp =tree -> right;
temp ->left = tree;
temp->left -> right = tree -> right ->left;
tree ->right = NULL;
tree =temp;
}
else //single RIGHT rotation
{
temp =NULL;
temp =tree -> right;
temp ->left = tree;
temp ->left -> right = tree -> right ->left;
tree ->right = NULL;
tree =temp;
}
}
else if(RIGHT <LEFT)
{
skirtumas(tree -> left);
if(LEFT <RIGHT)// LEFT subtree is RIGHT heavy, double rotation
{
temp3 =tree -> left;
temp3-> right = NULL;
temp3-> right = tree -> left -> right ->left;
printf("aaaaaaaa\n");
temp2 =tree -> left -> right;
temp2-> left = NULL;
temp2-> left = temp3;
temp =tree;
temp ->left = NULL;
temp ->left = temp2;
tree =NULL;
tree =temp;
temp =NULL;
temp =tree -> left;
temp ->right = tree;
temp ->right ->left = tree -> left -> right;
tree ->right = NULL;
tree =temp;
}
else //single LEFT rotation
{
temp =NULL;
temp =tree -> left;
temp ->right = tree;
temp ->right ->left = tree -> left -> right;
tree ->right = NULL;
tree =temp;
}
}
skirtumas(tree);
}
temp3 = NULL;
temp2 = NULL;
temp = NULL;
return(tree) ;
}