Forum Clubic

Ré-équilibrage d'un arbre AVL

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;
				}
			}
		}		
	}		
}

Qu’est-ce qu’une structure de type AVL ?

ça : fr.wikipedia.org…