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?

Recommended Answers

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-

instead of this:

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

why? the root of the tree is setted to -4-, but it doesn't shows it. I have checked that all the pointers are ok, in the place that I want, but they don't appear. why?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.