Bonjour,
Bonjour à tous je viens de trouver le code source de la supprssion dans un AVL, mais y'a une petite instruction qui m'intrigue
/** suppression du min (recursif) <br> la variable min va contenir la valeur du min supprimé
@param P : Noeud de depart
@param PP : Noeud parent
public boolean delMin(AVLNode PP,AVLNode P)
{
if (P.getLeft()==null) //trouvé, c'est le min
{
min=P.getValue(); //la variable globale contient le min
//on supprime le min
if (PP==null)
root=P.getRight(); //racine
else if (PP.getRight()==P)
PP.setRight(P.getRight()); //droite
else
PP.setLeft(P.getRight()); //gauche
return true;
}else //on cherche (recursif)
{
if (delMin(P,P.getLeft()))
{
//doit mettre a jour son deseq : on demande au parent de modifier son deseq uniquement
//si son fils a son deseq qui vient de passer a 0
P.setDeseq(P.getDeseq()-1); //mise a jour du deseq
return (reequilibre(PP,P)==0);
}
}
return false; }
/** suppression recursive */
public boolean del(int val)
{
delete(null,root,val);
return true;
}
/** reequilibre un noeud pour la suppression
@param PP parent du noeud a rééquilibrer
@param P noeud a rééquilibrer
@return le nouveau désequilibre du noeud
*/
private int reequilibre(AVLNode PP,AVLNode P)
{
if (P.getDeseq()==2 || P.getDeseq()==-2) //on doit rééquilibrer
{
if (PP==null)
{
root=reequilibrage(P); //racine
return root.getDeseq();
}else if (PP.getRight()==P) //droite
{
PP.setRight(reequilibrage(PP.getRight()));
return PP.getRight().getDeseq();
}
else
{ //gauche
PP.setLeft(reequilibrage(PP.getLeft()));
return PP.getLeft().getDeseq();
}
}
return P.getDeseq();
}
/** suppression recursive
@param P Noeud a considerer
@param PP parent de P
@param val valeur du noeud a supprimer
@return true si le noeud doit mettre a jour son deseq (usage interne a la fonction récursive)
*/
private boolean delete(AVLNode PP,AVLNode P,int val)
{
if (P==null) return false;
if (P.getValue()==val) //noeud a supprimer trouvée
{
if (P.getRight()!=null && P.getLeft()!=null) //2 fils
{
int d=P.getRight().getDeseq(); //on retiens le déseq a droite pour voir s'il a changé
boolean s=delMin(P,P.getRight()); //supprime le min a droite
// System.out.println("min deleted="+min);
//la variable globale min contient le min trouvé
P.setValue(min);
if (s || (P.getRight()!=null && P.getRight().getDeseq()==0 && P.getRight().getDeseq()!=d))
{
P.setDeseq(P.getDeseq()+1); //mise a jour du desequilibre du noeud
return (reequilibre(PP,P)==0); //on rééquilibre
}
return false;//le noeud parent n'as pas besoin de mettre a jour son deseq }else
{
if (P.getRight()!=null) //1 fils a droite
{
//efface P
if (PP==null) //racine
root=P.getRight();
else if (PP.getRight()==P)
PP.setRight(P.getRight()); //droite
else PP.setLeft(P.getRight()); //gauche
return true; //le noeud parent doit se mettre a jour
}else //1 fils a gauche
{
//efface P
if (PP==null)
root=P.getLeft(); //racine
else if (PP.getRight()==P)
PP.setRight(P.getLeft()); //droite
else PP.setLeft(P.getLeft()); //gauche
return true; //le noeud parent doit se mettre a jour
}
}
}else //c'est pas le bon noeud, on descendre plus bas
{
//appel recursif selon la valeur du noeud a supprimer
if (val<P.getValue()) //doit aller a gauche
{
if (delete(P,P.getLeft(),val))
P.setDeseq(P.getDeseq()-1);
return (reequilibre(PP,P)==0); //rééquilibrage si necessaire
}
}
else{
if (delete(P,P.getRight(),val)) //appel recusrsif vers la droite
{
P.setDeseq(P.getDeseq()+1);
return (reequilibre(PP,P)==0); //rééquilibrage si necessaire
}
}
}
return false; }
Le return false c'est cette instruction qui mintrigue, si c'est un return false cela veut dire que je peux pas termnier l'execution du reste des appels recursif
if (delete(P,P.getLeft(),val)) //suppression à gauche
P.setDeseq(P.getDeseq()-1);
Ce qui signifie que je met pas à jour le déséquilibre du pére du noeud qui a été supprimé, mais en principe sa se passe pas comme sa on doit mettre a jour le desq du pére, et du grd pére...jusqu'a à la racine puisque ces des appel récursifs..et c'est en fonction du deséquilibre qu'il peut y'avoir réequilibrage si nécessaire
return (reequilibre(PP,P)==0);//rééquilibrage si necessaireCordialement