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 !

[ternel]

Tes noms de types et variables sont monstrueux... "A, a, R, r, G, D, p, pa"

Pourquoi se priver d'informations limpides, telles que "arbre", "?", "gauche", "droit", "pointeur"?

je dirai que la clé de ton problème est que ta fonction de rotation ne prends pas l'arbre par pointeur/référence, mais une simple valeur, donc une copie de l'arbre ou faire la rotation.

Sauf si A est un typedef de pointeur de structure d'arbre, mais dans ce cas, ce n'est pas convenable…

[vasto lord]

oui, lorsque je passe la tête de la l'arbre commoe para avec passage par adresse la rotation se fait normalement ( avec rotation_d(&r) ) avec r c'est la racine mais la il faut que je passe comme paramètre le nœud ajouté et pas la tête ! et lorsque je fait ça, avec ( rotation_d(&G) ) avec G=grandpere(R); et R c'est le nœud ajouté .
l'arbre s'écrase et rien n'a changé sa place !

[vasto lord]

après modification voici les rotations avec un passage par adresse.

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
void rotation_g(A *R){ A gg=NULL,dg=NULL;
printf("\nRotation Gauche !\n");
if(*R!=NULL && (*R)->d!=NULL) {
        gg=*R;//garder la racine
        if((*R)->d->g!=NULL) dg=(*R)->d->g;//garder la gauche de droite de a
        *R=(*R)->d;//a devien la droite de a
        (*R)->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");
if(*R!=NULL && (*R)->g!=NULL) {
        dd=*R;//garder la racine
        if((*R)->g->d!=NULL)dg=(*R)->g->d;//garder la droite du gauche de a
        (*R)=(*R)->g;//a devien la gauche de a
        (*R)->d=dd;//
        dd->g=dg;//la gauche du droite de a devient  la droite du gauche de a
        }
}

il faut que je passe comme paramètre R ( le nœud ajouté )

Code :

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

        rotation_d(&(R->pa));

et ça ne marche pas !