Problème [ Arbre bicolore - Red black tree ] :

Version imprimable

1 pièce(s) jointe(s)

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:

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:

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:

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 !

07/06/2013, 09h41
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…
07/06/2013, 10h49
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 !

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

Code:

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:

rotation_d(&(R->pa));

et ça ne marche pas !