Problème recursivité héritage
Damien P.
-
Damien P. -
Damien P. -
Bonjour,
voilà j'ai un petit soucis dans mon programme, et je ne vois vraiment pas d'où ça peut venir. Enfin, je pense voir d'où ça vient, mais je ne vois pas comme le régler.
En gros, je travaille sur des arbres binaires, et je bloque lors de la suppression d'un élément. Mon programme se présente comme cela : j'ai une classe qui concerne les arbres binaires de recherche ABR avec la fonction de suppression, et une classe concernant les arbres binaires de recherche équilibrés AVL héritant de la classe ABR, avec également une fonction de suppression qui appelle celle d'ABR.
La fonction de suppression de la classe ABR fonctionne, mais celle d'AVL me crée une boucle infinie.
Voici la fonction de suppression de ABR :
et celle d'AVL :
Celle-ci appelle donc la fonction supprimer d'ABR, et effectue d'autres exécutions ensuite. Seulement, visiblement, lors de la fin de l'appel à la fonction supprimer, il ne me reste plus qu'un arbre réduit à une feuille. De ce fait, il boucle indéfiniment dans la troisième condition de la boucle while. Ce que je ne comprend pas, c'est que la fonction supprimer d'ABR ne me pose aucun soucis...Comment faire pour ne pas me retrouver avec un arbre réduit à une feuille à la fin ?
En espérant que quelqu'un puisse m'aider :(
voilà j'ai un petit soucis dans mon programme, et je ne vois vraiment pas d'où ça peut venir. Enfin, je pense voir d'où ça vient, mais je ne vois pas comme le régler.
En gros, je travaille sur des arbres binaires, et je bloque lors de la suppression d'un élément. Mon programme se présente comme cela : j'ai une classe qui concerne les arbres binaires de recherche ABR avec la fonction de suppression, et une classe concernant les arbres binaires de recherche équilibrés AVL héritant de la classe ABR, avec également une fonction de suppression qui appelle celle d'ABR.
La fonction de suppression de la classe ABR fonctionne, mais celle d'AVL me crée une boucle infinie.
Voici la fonction de suppression de ABR :
public void supprimer(T n)
{
if(!this.estVide() && this.estDans(n))
{
if(this.getValeur() == n)
{
if(!this.getGauche().estVide())
{
T max = this.getGauche().max();
this.setValeur(max);
this.getGauche().supprimer(max);
}
else if(!this.getDroit().estVide())
{
T min = this.getDroit().min();
this.setValeur(min);
this.getDroit().supprimer(min);
}
else
{
this.setValeur(null);
}
}
else if(n.compareTo(this.getValeur()) < 0)
{
this.getGauche().supprimer(n);
}
else
{
this.getDroit().supprimer(n);
}
}
}
et celle d'AVL :
public void supprimer(T n)
{
super.supprimer(n);
while(!this.estEquilibre())
{
if(this.getGauche().hauteur() - this.getDroit().hauteur() == 2)
{
if(this.getGauche().getDroit().hauteur() <= this.getGauche().getGauche().hauteur())
{
this.rotationDroite();
}
else
{
this.getGauche().rotationGauche();
this.rotationDroite();
}
}
else if(this.getGauche().hauteur() - this.getDroit().hauteur() == -2)
{
if(this.getDroit().getDroit().hauteur() >= this.getDroit().getGauche().hauteur())
{
this.rotationGauche();
}
else
{
this.getDroit().rotationDroite();
this.rotationGauche();
}
}
else
{
if(this.getGauche().hauteur() > this.getDroit().hauteur())
{
this.rotationDroite();
}
else
{
this.rotationGauche();
}
}
}
}
Celle-ci appelle donc la fonction supprimer d'ABR, et effectue d'autres exécutions ensuite. Seulement, visiblement, lors de la fin de l'appel à la fonction supprimer, il ne me reste plus qu'un arbre réduit à une feuille. De ce fait, il boucle indéfiniment dans la troisième condition de la boucle while. Ce que je ne comprend pas, c'est que la fonction supprimer d'ABR ne me pose aucun soucis...Comment faire pour ne pas me retrouver avec un arbre réduit à une feuille à la fin ?
En espérant que quelqu'un puisse m'aider :(
9 réponses
Déjà, je pense que ton équilibrage devrait être dans une méthode à part, la méthode de suppression est uniquement là pour supprimer. En plus tu auras surement besoin d'utiliser la méthode d'équilibrage dans d'autres méthodes (l'insertion par exemple).
Cependant il me semble faux d'utiliser la méthode de suppression de ABR pour supprimer dans un AVL. Normalement dans un AVL on ne supprime que des feuilles. Il faut donc déplacer l'élément à supprimer jusqu'à une feuille, tout en conservant l'équilibre de l'arbre. Cela est donc un peu plus compliqué qu'une simple suppression d'ABR.
De plus je me permets aussi de critiquer un peu ta suppression ABR, car tu fais
Remarque plus générale : this est facultatif dans la plupart des cas, donc quand tu n'en as pas explicitement besoin, il vaut mieux l'enlever.
public void supprimer(T n)
{
super.supprimer(n);
equilibrer();
}
Cependant il me semble faux d'utiliser la méthode de suppression de ABR pour supprimer dans un AVL. Normalement dans un AVL on ne supprime que des feuilles. Il faut donc déplacer l'élément à supprimer jusqu'à une feuille, tout en conservant l'équilibre de l'arbre. Cela est donc un peu plus compliqué qu'une simple suppression d'ABR.
De plus je me permets aussi de critiquer un peu ta suppression ABR, car tu fais
getValeur() == n, or la comparaison de deux objets devrait se faire avec la méthode
getValeur().equals(n)(ou vu ton contexte avec un
getValeur().compareTo(n)==0)
Remarque plus générale : this est facultatif dans la plupart des cas, donc quand tu n'en as pas explicitement besoin, il vaut mieux l'enlever.
La méthode equilibrer() vient d'être faite à part !
Pour ce qui est de getValeur().equals(n) et getValeur() == n, je suis aussi d'accord, cependant j'avais testé de cette façon pour voir si le problème ne venait pas de là du fait que == et equals() ne retourne pas la même chose selon le contexte, mais visiblement ce n'était pas la source de l'erreur, je viens donc de rechanger celà !
Cependant pour l'utilisation de supprimer() de ABR dans AVL, ceci est correct (j'avais demandé à ma prof). De plus, je ne vois pas vraiment où serait le soucis puisque dans tous les cas si la suppression engendre un déséquilibrage de l'arbre, il passe par la fonction equilibrer() qui elle procède à des rotations.
Quoiqu'il en soit, le problème reste le même, j'aimerais savoir comment éviter la boucle infinie à cause de la réduction à une feuille de l'arbre de départ qui devrait rester l'arbre de base une fois equilibre() appelé...
Pour ce qui est de getValeur().equals(n) et getValeur() == n, je suis aussi d'accord, cependant j'avais testé de cette façon pour voir si le problème ne venait pas de là du fait que == et equals() ne retourne pas la même chose selon le contexte, mais visiblement ce n'était pas la source de l'erreur, je viens donc de rechanger celà !
Cependant pour l'utilisation de supprimer() de ABR dans AVL, ceci est correct (j'avais demandé à ma prof). De plus, je ne vois pas vraiment où serait le soucis puisque dans tous les cas si la suppression engendre un déséquilibrage de l'arbre, il passe par la fonction equilibrer() qui elle procède à des rotations.
Quoiqu'il en soit, le problème reste le même, j'aimerais savoir comment éviter la boucle infinie à cause de la réduction à une feuille de l'arbre de départ qui devrait rester l'arbre de base une fois equilibre() appelé...
"si la suppression engendre un déséquilibrage de l'arbre, il passe par la fonction equilibrer() qui elle procède à des rotations"
L'idée est en fait justement de faire la suppression sans (trop) déséquilibrer l'arbre, en procédant à des rotations préparatoires moins coûteuses qu'un rééquilibrage complet suite à une suppression quelconque.
Pour ta boucle infinie montre nous un peu plus de code. En particulier tes méthodes de rotations. Idéalement, si j'avais ton code complet je pourrais tester directement chez moi. Sinon ça restera que des conseils très théoriques...
L'idée est en fait justement de faire la suppression sans (trop) déséquilibrer l'arbre, en procédant à des rotations préparatoires moins coûteuses qu'un rééquilibrage complet suite à une suppression quelconque.
Pour ta boucle infinie montre nous un peu plus de code. En particulier tes méthodes de rotations. Idéalement, si j'avais ton code complet je pourrais tester directement chez moi. Sinon ça restera que des conseils très théoriques...
Voici les fonctions rotationGauche() et rotationDroite() de la classe AB :
http://pastebin.com/yySGwTst
Voici la classe complète ABR (qui hérite de AB) :
http://pastebin.com/qRrjqqgK
Voici la classe complète AVL (qui hérite de ABR) :
http://pastebin.com/Wd19ALuy
http://pastebin.com/yySGwTst
Voici la classe complète ABR (qui hérite de AB) :
http://pastebin.com/qRrjqqgK
Voici la classe complète AVL (qui hérite de ABR) :
http://pastebin.com/Wd19ALuy
Classe AB complète :
http://pastebin.com/71HW7Sp6
Je mets la classe AB dans son intégralité, pour éviter qu'il y ai des confusions dans le code. Après relecture, ce n'est peut-être pas évident sans le code complet...
http://pastebin.com/71HW7Sp6
Je mets la classe AB dans son intégralité, pour éviter qu'il y ai des confusions dans le code. Après relecture, ce n'est peut-être pas évident sans le code complet...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Je viens de regarder un peu le code, mais il te manque des constructeurs "simples".
Pour ma classe de test je voulais juste faire un arbre AVL mais le seul constructeur d'AVL prend en paramètre deux ABR, qui nécessitent eux même deux AB chacun, ça fait donc quatre, alors que les AB n'ont pas non plus de constructeur par défaut. J'ai donc essayé de me débrouiller avec des null mais tu n'as pas géré tous les cas d'utilisation donc je me retrouve avec un NullPointerException...
Est-ce que tu pourrais me donner aussi ton code de test, celui qui te fourni la boucle infinie, pour que je puisse progresser pas à pas ?
D'emblée il y a quelque chose qui me chiffonne, c'est ton test
Pour ma classe de test je voulais juste faire un arbre AVL mais le seul constructeur d'AVL prend en paramètre deux ABR, qui nécessitent eux même deux AB chacun, ça fait donc quatre, alors que les AB n'ont pas non plus de constructeur par défaut. J'ai donc essayé de me débrouiller avec des null mais tu n'as pas géré tous les cas d'utilisation donc je me retrouve avec un NullPointerException...
package test;
import arbres.AVL;
public class Test
{
/** @param args unused */
public static void main(String...args)
{
AVL<String> arbre = new AVL<String>(null, null, null);
arbre.ajouter("A"); // NullPointerException
}
}
Est-ce que tu pourrais me donner aussi ton code de test, celui qui te fourni la boucle infinie, pour que je puisse progresser pas à pas ?
D'emblée il y a quelque chose qui me chiffonne, c'est ton test
while(!this.estEquilibre()), normalement quand un arbre est équilibré, si on le déséquilibre un petit peu (suite à un ajout/suppression) l'opération de rééquilibrage devrait se faire une seule fois, on devrait donc plutôt avoir un
if (!this.estEquilibre())et ensuite un équilibrage en une seule étape. La garantie que l'arbre sera équilibré à la fin vient du fait qu'il était équilibré juste avant l'opération (ajout/suppression) qui l'a déséquilibré.
Classe Test :
http://pastebin.com/LZwsgGqk
Sauf que dans la fonction ajouter() figure en première ligne :
if(this.estVide())
Du coup ceci testera si le 2ème paramètre est nul ou non. Cela dit je suis d'accord qu'un problème de ce genre pourrait figurer, mais à condition de ne pas respecter la façon dont a été défini un arbre. Un arbre, même sans fils gauche/droit, possède des objets de type AB à sa gauche/droit, seulement cet arbre gauche/droit sera défini comme tu l'as fait dans ton message, avec (null, null, null). Mais le problème de vient pas de là, j'ai déjà géré ces cas-là, et si besoin je regarderai à nouveau.
"normalement quand un arbre est équilibré, si on le déséquilibre un petit peu (suite à un ajout/suppression) l'opération de rééquilibrage devrait se faire une seule fois, on devrait donc plutôt avoir un if"
---> le problème c'est que si on a un arbre de base très déséquilibré et qu'après un ajout/suppression il le soit encore beaucoup, plusieurs rééquilibrages seraient nécessaire, du coup je pense que le while() convient.
http://pastebin.com/LZwsgGqk
Sauf que dans la fonction ajouter() figure en première ligne :
if(this.estVide())
Du coup ceci testera si le 2ème paramètre est nul ou non. Cela dit je suis d'accord qu'un problème de ce genre pourrait figurer, mais à condition de ne pas respecter la façon dont a été défini un arbre. Un arbre, même sans fils gauche/droit, possède des objets de type AB à sa gauche/droit, seulement cet arbre gauche/droit sera défini comme tu l'as fait dans ton message, avec (null, null, null). Mais le problème de vient pas de là, j'ai déjà géré ces cas-là, et si besoin je regarderai à nouveau.
"normalement quand un arbre est équilibré, si on le déséquilibre un petit peu (suite à un ajout/suppression) l'opération de rééquilibrage devrait se faire une seule fois, on devrait donc plutôt avoir un if"
---> le problème c'est que si on a un arbre de base très déséquilibré et qu'après un ajout/suppression il le soit encore beaucoup, plusieurs rééquilibrages seraient nécessaire, du coup je pense que le while() convient.
Je vais regarder le code de test pour voir si je trouve le problème.
"si on a un arbre de base très déséquilibré"< ital/>
Normalement on ne devrait jamais avoir un arbre très déséquilibré.
On part d'un arbre vide (équilibré), on fait un ajout, un équilibrage, une suppression, un équilibrage. A la limite il n'y a même pas besoin de tester si l'arbre est équilibré vu qu'il devrait toujours l'être, donc pas de if et encore moins un while.
< ital>"un problème de ce genre pourrait figurer, mais à condition de ne pas respecter la façon dont a été défini un arbre."
Il faudrait peut être revoir la manière dont les arbres sont construits. Moi je suis habitué à l'interface Collection (qui définit les arbres, listes, piles etc. en Java) du coup je m'attends à avoir au minimum un constructeur vide pour un arbre vide. Et ensuite juste les méthodes d'ajouts et suppressions. Le reste (notamment les constructeurs à trois arguments) devraient être private ou protected mais certainement pas public.
"si on a un arbre de base très déséquilibré"< ital/>
Normalement on ne devrait jamais avoir un arbre très déséquilibré.
On part d'un arbre vide (équilibré), on fait un ajout, un équilibrage, une suppression, un équilibrage. A la limite il n'y a même pas besoin de tester si l'arbre est équilibré vu qu'il devrait toujours l'être, donc pas de if et encore moins un while.
< ital>"un problème de ce genre pourrait figurer, mais à condition de ne pas respecter la façon dont a été défini un arbre."
Il faudrait peut être revoir la manière dont les arbres sont construits. Moi je suis habitué à l'interface Collection (qui définit les arbres, listes, piles etc. en Java) du coup je m'attends à avoir au minimum un constructeur vide pour un arbre vide. Et ensuite juste les méthodes d'ajouts et suppressions. Le reste (notamment les constructeurs à trois arguments) devraient être private ou protected mais certainement pas public.
"Normalement on ne devrait jamais avoir un arbre très déséquilibré. "
---> Cette supposition n'existe pas selon ma prof, on peut avoir toute sorte d'arbre, donc je fais comme tel.
Pour le reste je ne peux répondre, je n'ai pas eu beaucoup de renseignements sur ce que je devais faire, ce que j'ai fait là n'est pas incorrect, je suis même sûr que je ne dois pas faire autrement...
Sinon, tiens-moi au courant si tu as des résultats ! Cela fait à peu près une semaine que je suis sur ce problème, et sans le résoudre je ne peux avancer...
---> Cette supposition n'existe pas selon ma prof, on peut avoir toute sorte d'arbre, donc je fais comme tel.
Pour le reste je ne peux répondre, je n'ai pas eu beaucoup de renseignements sur ce que je devais faire, ce que j'ai fait là n'est pas incorrect, je suis même sûr que je ne dois pas faire autrement...
Sinon, tiens-moi au courant si tu as des résultats ! Cela fait à peu près une semaine que je suis sur ce problème, et sans le résoudre je ne peux avancer...
Bonjour,
Je viens de déboguer un peu ton code et il semble que cela ne soit effectivement pas grand chose.
Dans la méthode equilibrer() à cause des rotations successives tu peux te retrouver avec un arbre this qui devient vide et ça boucle.
Essayes comme ceci :
Je viens de déboguer un peu ton code et il semble que cela ne soit effectivement pas grand chose.
Dans la méthode equilibrer() à cause des rotations successives tu peux te retrouver avec un arbre this qui devient vide et ça boucle.
Essayes comme ceci :
public void equilibrer()
{
while (!estVide() && !estEquilibre())
{
// ...
Impeccable, je viens de tester les résultats sur papier avant ceux sur ordinateur, et il semble que cela n'était que ça car c'est tout à fait correct !
En y réfléchissant, c'est vrai que c'est logique, tout comme les tests de bases dans AB sur des arbres vides... Merci beaucoup, c'est super sympa, je vais pouvoir avancer grâce à toi !
En y réfléchissant, c'est vrai que c'est logique, tout comme les tests de bases dans AB sur des arbres vides... Merci beaucoup, c'est super sympa, je vais pouvoir avancer grâce à toi !