Salut,
Je dois créer une structure de type AVL et pouvoir ajouter des éléments sans le déséquilibrer.
Le truc c’est que quand je dois effectuer des rotations gauche_droite ou droite_gauche, un léger problème se pose (à mon avis il me manque une condition lorsque le sous-sous-arbre (qui après rotation se retrouve à la racine) est équilibré avant roation), mais je n’arrive pas à trouver laquelle :@
Le code vérifie l’ordre alphabétique, place le mot, et ré-équilibre si nécéssaire.
void ajout_synonyme_h (T_Syn *S, T_Mot m, int *hauteur_augmente)
{
int i = 0;
/*Si l'arbre S pointe vers NULL, alors on peut placer la feuille ici*/
if (*S==NULL)
{
*S = creer_feuille(m);
*hauteur_augmente = 1; //La hauteur du sous-arbre est modifiée
}
else
{
/*Le choix du sous-abre se fait selon l'ordre aphabétique*/
//Recherche de la première lettre différente entre les deux mots
/*Vérifie les lettres unes par unes, puis vérifie si un mot est plus court qu'un autre*/
while ((i<32) && (m[i]==(*S)->mot[i]) && (m[i]!='\0') && ((*S)->mot[i]!='\0'))
i++;
//Comparaison de la lettre
//Vérifie si le mot à ajouter est situé avant dans l'ordre alphabétique, ou s'il contient moins de caractères que le mot présent à ce noeud
if ((m[i] < (*S)->mot[i]) || (m[i]=='\0')) //Ajout dans le sous-arbre gauche
{
ajout_synonyme_h(&((*S)->sag), m, hauteur_augmente);
/*L'élément est maintenant ajouté */
/*La hauteur du sous-arbre à pu être augmentée au cours de cet ajout*/
if (hauteur_augmente)
{
switch ((*S)->equilibre)
{
case -1 :
(*S)->equilibre = 0;
*hauteur_augmente = 0; //Le sous-arbre gauche était plus petit que le sous-arbre droit
break;
case 0 :
(*S)->equilibre = 1;
*hauteur_augmente = 1; //Les sous-arbre étaient de même taille avant ajout
break;
case 1 : /*Il faut ré-équilibrer l'arbre à l'aide d'une rotation droite*/
/*Dans certains cas, une double rotation est nécessaire*/
/*Le ré-équilibrage à effectuer dépend de l'équilibre du sous-arbre gauche */
if ( ((*S)->sag)->equilibre == 1 )
{
Rotation_Droite_syn(S); //Ré-équilibrage
/*Rétablissement de l'équilibre*/
(*S)->sad->equilibre =0;
}
else
{
Rotation_Gauche_Droite_syn(S);
/*Les nouvelles valeurs d'équilibre dépendent du sous-arbre droit du sous-arbre gauche*/
/*qui se retrouve à la racine après rotation*/
switch ((*S)->equilibre)
{
case -1 :
(*S)->sag->equilibre = 1;
(*S)->sad->equilibre = 0;
break;
case 0 :
(*S)->sag->equilibre = 0;
(*S)->sad->equilibre = 0;
break;
case 1 :
(*S)->sag->equilibre = 0;
(*S)->sad->equilibre = -1;
break;
}
}
(*S)->equilibre = 0; //Après ré-équilibrage, l'arbre est parfaitement équilibré
*hauteur_augmente = 0; //La hauteur n'est pas modifiée
break;
}
}
}
else //Ajout dans le sous-arbre droit
{
ajout_synonyme_h(&((*S)->sad), m, hauteur_augmente);
/*L'élément est maintenant ajouté */
/*La hauteur du sous-arbre à pu être augmentée au cours de cet ajout*/
if (hauteur_augmente)
{
switch ((*S)->equilibre)
{
case 1 : //Le sous-arbre gauche était plus grand
(*S)->equilibre = 0;
*hauteur_augmente = 0;
break;
case 0 : //Les sous-arbres étaient de même hauteur
(*S)->equilibre = -1;
*hauteur_augmente = 1;
break;
case -1 : /*Il faut ré-équilibrer l'arbre*/
/*Le ré-équilibrage à effectuer dépend de l'équilibre du sous-arbre droit */
if ((*S)->sad->equilibre == -1)
{
Rotation_Gauche_syn(S);
/*Rétablissement de l'équilibre*/
(*S)->sag->equilibre =0;
}
else
{
Rotation_Droite_Gauche_syn(S); //Ré-équilibrage
/*Rétablissement de l'équilibre*/
/*Les nouvelles valeurs d'équilibre dépendent du sous-arbre gauche du sous-arbre droit*/
/*qui se retrouve à la racine après rotation*/
switch ((*S)->equilibre)
{
case -1 :
(*S)->sag->equilibre = 0;
(*S)->sad->equilibre = -1;
break;
case 0 : //a séparer en plusieurs cas?
(*S)->sag->equilibre = 0;
(*S)->sad->equilibre = 0;
break;
case 1 :
(*S)->sag->equilibre = 1;
(*S)->sad->equilibre = 0;
break;
}
}
(*S)->equilibre = 0;
*hauteur_augmente = 0; //La hauteur de l'arbre n'est pas modifiée après ré-équilibrage
break;
}
}
}
}
}