Bonjour,

Mon opération de suppression dans un arbre AVL ne fonctionne pas correctement. Dans ma classe ArbreAVL on a un attribut equilibre pour maintenir l'équilibre après insertions/suppressions. L'équilibre est défini tel que equilibre = hauteur(fils gauche) - hauteur(fils droit).

Dans ma fonction suppression, en essayant de la debuger, je m'apperçois qu' íl arrive des fois où l'équilibre d'un noeud est à -2 (resp. 2) alors que celui ci n'a pas de fils droit (resp. gauche). Je ne voit pas ce qui conduit à cet évènement...

Merci d'avance pour votre aide.

template <class T>
class ArbreAVL {
	public:
		void inserer(const T&);
		void enlever(const T&);
	private:
		struct Noeud{
			Noeud(const T&);
			T contenu;
			int equilibre;
			Noeud *gauche;
			Noeud *droite;
		};
		Noeud* racine;
		bool inserer(Noeud*&, const T&);
		void rotationGaucheDroite(Noeud*&);
		void rotationDroiteGauche(Noeud*&);
		const T& max(Noeud*) const;
		bool enlever(Noeud*&, const T& e);
};

template <class T>
void ArbreAVL<T>::inserer(const T& element) {
	this->inserer(racine, element);
}

template <class T>
bool ArbreAVL<T>::inserer(Noeud*& noeud, const T& element) {
	if (noeud == nullptr) {
		noeud = new Noeud(element);
		return true;
	}
	if (element < noeud->contenu){
		if(this->inserer(noeud->gauche, element)) {
			noeud->equilibre++;
			if(noeud->equilibre == 0)
				return false;
			if(noeud->equilibre == 1)
				return true;
			if(noeud->gauche->equilibre == -1)
				this->rotationDroiteGauche(noeud->gauche);
			this->rotationGaucheDroite(noeud);
		}
		return false;
	}
	if (element > noeud->contenu){
		if (this->inserer(noeud->droite, element)) {
			noeud->equilibre--;
			if (noeud->equilibre == 0)
				return false;
			if (noeud->equilibre == -1)
				return true;
			if (noeud->droite->equilibre == 1)
				this->rotationGaucheDroite(noeud->droite);
			this->rotationDroiteGauche(noeud);
		}
		return false;
	}
	noeud->contenu = element;
	return false;
}

template <class T>
void ArbreAVL<T>::rotationGaucheDroite(Noeud*& racinesousarbre) {
	Noeud *temp = racinesousarbre->gauche;
	int  ea = temp->equilibre;
	int  eb = racinesousarbre->equilibre;
	int  neb = -(ea>0 ? ea : 0) - 1 + eb;
	int  nea = ea + (neb < 0 ? neb : 0) - 1;

	temp->equilibre = nea;
	racinesousarbre->equilibre = neb;
	racinesousarbre->gauche = temp->droite;
	temp->droite = racinesousarbre;
	racinesousarbre = temp;
}

template <class T>
void ArbreAVL<T>::rotationDroiteGauche(Noeud*& racinesousarbre) {
	Noeud *temp = racinesousarbre->droite;
	int  eb = temp->equilibre;
	int  ea = racinesousarbre->equilibre;
	int  nea = -(eb<0 ? eb : 0) + 1 + ea;
	int  neb = eb + (nea > 0 ? nea : 0) + 1;

	temp->equilibre = neb;
	racinesousarbre->equilibre = nea;
	racinesousarbre->droite = temp->gauche;
	temp->gauche = racinesousarbre;
	racinesousarbre = temp;
}


template <class T>
const T& ArbreAVL<T>::max(Noeud* n) const {
	assert(n != nullptr);
	if (n->droite == nullptr)
		return n->contenu;
	return this->max(n->droite);
}

template <class T>
void ArbreAVL<T>::enlever(const T& element) {
	this->enlever(racine, element);
}

template <class T>
bool ArbreAVL<T>::enlever(Noeud*& noeud, const T& element) {
	if(element < noeud->contenu) {
		if(this->enlever(noeud->gauche, element)) {
			noeud->equilibre--;
			if (noeud->equilibre == 0)
				return false;
			if (noeud->equilibre == -1)
				return true;
// ici il arrive que noeud->droite == nulptr alors que noeud->equilibre == -2
			 if (noeud->droite->equilibre == -1) {
				this->rotationDroiteGauche(noeud);
				return false;
			}
			else if (noeud->droite->equilibre == 0) {
				this->rotationDroiteGauche(noeud);
				return true;
			}
			else if (noeud->droite->equilibre == 1) {
				this->rotationGaucheDroite(noeud->droite);
				this->rotationDroiteGauche(noeud);
				return false;
			}
			return true;
		}
	}
	else if (element > noeud->contenu) {
		if(this->enlever(noeud->droite, element)) {
			noeud->equilibre++;
			if (noeud->equilibre == 0)
				return false;
			if (noeud->equilibre == 1)
				return true;
			if (noeud->gauche->equilibre == 1) {
				this->rotationGaucheDroite(noeud);
				return false;
			}
			else if (noeud->gauche->equilibre == 0) {
				this->rotationGaucheDroite(noeud);
				return true;
			}
			else if (noeud->gauche->equilibre == -1) {
				this->rotationDroiteGauche(noeud->gauche);
				this->rotationGaucheDroite(noeud);
				return false;
			}
			return true;
		}
	}
	else {
		if (noeud->gauche == nullptr && noeud->droite == nullptr) {
			delete noeud;
			noeud = nullptr;
			return true;
		}
		else {
			if (noeud->gauche == nullptr) {
				Noeud* tmp = noeud->droite;
				delete noeud;
				noeud = tmp;
				return true;
			}
			else if (noeud->droite == nullptr) {
				Noeud* tmp = noeud->gauche;
				delete noeud;
				noeud = tmp;
				return true;
			}
			else {
				T tmp = this->max(noeud->gauche);
				this->enlever(tmp);
				noeud->contenu = tmp;
				return false;
			}
		}
	}
	return true;
}

-
Edité par Sevla 14 novembre 2019 à 22:36:32