I´m trying to develop an avl tree in C++, but I have problems with my rotation algorithm. I have try ALL the algorithms I could find on the web, but none of they works and I can´t see where is the problem.
Here is my structure:

``````typedef struct node{
int data;
int fe;
struct node *left;
struct node *right;
struct node *father;
}node;
typedef struct node *avl;``````

This is my implementation of the simple rigth rotation, which recieves a pointer of the node where is the unbalance (*fot), and I create three pointers:
*a if the fot node recieved is not the father of the tree.
*p will be replacing *fot in the rotation
*q will be the left child of *fot, replacing *p

``````void SRR(avl *fot){
avl *a;  a=new avl;  *a=NULL;
avl *p;  p=new avl;  *p=NULL;
avl *q;  q=new avl;  *q=NULL;

&*a= &(*fot);
*p= (*fot)->left;
*q= (*p)->right;

(*fot)->left= *q;

if (q)
(*q)->father= *fot;

(*p)->right= (*fot);
(*fot)->father= *p;

if ((*a)->father->data==(*a)->data)
(*p)->father=*p;
else
(*p)->father=(*a)->father;

(*fot) = *p;
*p = (*fot)->rigth;
*q = (*p)->left;
}``````

No matter how hard I try, I can´t see where is the problem, my program freezes and I don't know where. Please, can anyone help me to find the problem? :'( What's wrong in my algorithm?

## All 5 Replies

What is the purpose of this line ?

``&*a= &(*fot);``

The code fragment that you have posted does not contain any loops or recursion . Please put some cout statements to get a better idea of the region where the code is freezing

I need to save the pointer to the unbalanced node inorder to make the switch.

Dont & and * cancel each other out ?

``````int main() {

int x = 10;
int *p1 = &x;

printf("p1  %p\n",p1);
printf("*p1 %d\n",*p1);
printf("*&p1 %p\n",*&p1);
printf("&*p1 %p\n",&*p1);

return 0;
};``````

Dont & and * cancel each other out ?

``````int main() {

int x = 10;
int *p1 = &x;

printf("p1  %p\n",p1);
printf("*p1 %d\n",*p1);
printf("*&p1 %p\n",*&p1);
printf("&*p1 %p\n",&*p1);

return 0;
};``````

No because x is not a pointer you need the address of operator when assigning it to an int pointer.

OP, why do you assign memory to each variable then set it to NULL? I see that you dereference them first but.... it's still wierd...

``````avl *a;  a=new avl;  *a=NULL;
avl *p;  p=new avl;  *p=NULL;
avl *q;  q=new avl;  *q=NULL;``````

please don't crucify me, I'm new in programming
I do this:

``avl *a;  a=new avl;  *a=NULL;``

because otherwise, I get a warning which says that I'm using a variable before reference it

I have this code now:

``````void SRR(avl *fot){
avl *a; a=new avl; *a=NULL;
avl *p; p=new avl; *p=NULL;
avl *q; q=new avl; *q=NULL;

*a= *fot;
*p= (*fot)->left;
*q= (*p)->right;

(*a)->left= *q;

if (q)
(*q)->father= *a;

(*p)->right= (*a);
(*a)->father= *p;

if ((*a)->father->data!=(*a)->data)
(*p)->father=(*a)->father;
else
(*p)->father=*p;

*fot = *a;
*p = (*fot)->rigth;
*q = (*p)->left;
}``````

it runs perfectly, but when I have a tree like this:

``````-6-
-4-        -8-
-2-   -5-
-1- -3-``````

and then I call SRR(), it returns me this tree:

``````-6-
-5-      -8-
-1-``````

``````-4-