Discussion :

[vasto lord]

Bonjour, j'ai un travail à finir, c'est une arbre bicolore qui doit être équilibré a chaque insertion ou suppression, mon problème est dans les rotations !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
void ajout(A p, A *r){ A R=*r; // P c'est le nœud déjà créé, r la racine 
    if(*r==NULL) *r=p; // si l'arbre est vide, le sommet est noire
    else {
    p->pa=*r; // comme le précédant pour les listes !
    if((*r)->cle> p->cle)  ajout(p,&(*r)->g,t);
    else ajout(p,&(*r)->d,t);
    }
eq_racine(p); // pour l'équilibrage !
}

l'équilibrage se fait normalement, mais lorsque je cherche à faire la règle de beta ( règle d'arrêt qui contient les rotations ) les rotation ne marche pas !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void eq_beta_test1(A R){
    A G=grandpere(R);
    if((R == R->pa->d) && (R->pa == G->g)){ // si
        //
        rotation_d(R->pa);
        }
    else if ((R == R->pa->g) && (R->pa == G->d)){
        rotation_g(R->pa);
    }
    printf("cle : %d\n",R->cle);
    eq_beta_test2(R);
}
 
void eq_beta_test2(A R){
    A G=grandpere(R);
    R->pa->color='n';
    G->color='b';
    if(R==R->pa->g) rotation_d(R);
    else rotation_g(R);
}

voici les fonctions de rotations :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void rotation_g(A R){ A gg=NULL,dg=NULL;
A G=grandpere(R);
printf("\nRotation Gauche !\n");
if(G!=NULL && G->d!=NULL) {
        gg=G;//garder la racine
        if(G->d->g!=NULL) dg=G->d->g;//garder la gauche de droite de a
        G=G->d;//a devient la droite de a
        G->g=gg;
        gg->d=dg;//la droite du gauche de a devient la gauche du droite de a
}
}
//rotation_droite
void rotation_d(A R){ A dd=NULL,dg=NULL;
printf("\nRotation droite !\n");
A G=grandpere(R);
if(G!=NULL && G->g!=NULL) {
        dd=G;//garder la racine
        if(G->g->d!=NULL)dg=G->g->d;//garder la droite du gauche de a
        G=G->g;//a devien la gauche de a
        G->d=dd;//
        dd->g=dg;//la gauche du droite de a devient  la droite du gauche de a
        }
}

le programme est ci-joint si vous voulez vérifier le code en détail.
MERCI !