Forum Programmation.java [JAVA] Suppression dans un arbre binaire ordonné

Posté par . Licence CC By‐SA.
Étiquettes : aucune
0
4
jan.
2014

Bonjour a tous,

Je travaille sur un projet avec des arbres binaires et je suis bloqué a un endroit : pour supprimer dans un arbre binaire.
J'ai beau avoir cherché sur Wikipédia et autre, aucun des codes que j'ai pu voir ne fonctionnait dans mon cas.

Voici ce que j'appelle mon arbre binaire :

 public class GenericBinaryTree<V> {
 // ATTRIBUTS
 private Comparable value;
 private GenericBinaryTree SAD;
 private GenericBinaryTree SAG;
 // CONSTRUCTEUR
 public GenericBinaryTree(Comparable val) {
 this.value = val;
 this.SAD = null;
 this.SAG = null;
 }

Toutes ses méthodes fonctionnent sauf supprimer que voici :

 // Supprime un noeud a partir de sa valeur 
 public void remove(Comparable val) {
 GenericBinaryTree noeudConcerne, pereNoeud;
 // Le noeud concerné est celui qu'on veut supprimer
 noeudConcerne = this.trouverNoeur(val);
 // On regarde d'abord du coté du SAG du noeud concerné, si il n'est pas nul
 if (noeudConcerne.SAG != null) {
 // pereNoeud est le pere du maximum du SAG du noeud
 pereNoeud = this.SAG.perMax();
 // Si il est nul alors
 if (pereNoeud == null) {
 this.value = this.SAG.value;
 this.SAG = this.SAG.SAG;
 } else {
 this.value = pereNoeud.SAD.value;
 pereNoeud.SAD = pereNoeud.SAD.SAG;
 }
 }
 // Faire pareil avec sous arbre droit et perMin
 }

Qui utilise les fonctions suivantes (qui fonctionnent) :

 // Renvoie le noeud associé a une valeur
 public GenericBinaryTree trouverNoeur(Comparable val) {
 // Si on est au niveau de la valeur recherchée on la selectionne
 if ((this.value).compareTo(val) == 0) {
 return this;
 } else {
 // Sinon on regarde dans le SAG si la valeur est inférieure
 if ((this.value.compareTo(val)) < 0) {
 if (this.SAG != null) {
 return this.SAG.trouverNoeur(val);
 } else {
 // Si pas de sous arbre gauche, la valeur n'est pas la
 return null;
 }
 } else {
 // Idem SAD si la valeur est supérieure
 if (this.SAD != null) {
 return this.SAD.trouverNoeur(val);
 } else {
 return null;
 }
 }
 }
 }
 // Retourne le pere de l'arbre avec la valeur maximale
 public GenericBinaryTree perMax() {
 // On initialise la variable résultat
 GenericBinaryTree res = new GenericBinaryTree("error");
 /* On va chercher quand le SAD s'arrête, quand c'est le cas, on choisit
 * le noeud "grand pere" de cet arbre pour obtenir le pere du max
 */
 if (this.SAD != null) {
 if (this.SAD.SAD == null) {
 res = this;
 } else {
 res = this.SAD.perMax();
 }
 } else {
 // Si l'arbre est trop petit on retourne null
 res = null;
 }
 return res;
 }
 // Retourne le pere de l'arbre avec la valeur minimale
 public GenericBinaryTree perMin() {
 // On initialise la variable résultat
 GenericBinaryTree res = new GenericBinaryTree("error");
 /* On va chercher quand le SAG s'arrête, quand c'est le cas, on choisit
 * le noeud "grand pere" de cet arbre pour obtenir le pere du min
 */
 if (this.SAG != null) {
 if (this.SAG.SAG == null) {
 res = this;
 } else {
 res = this.SAG.perMin();
 }
 } else {
 // Si l'arbre est trop petit on retourne null
 res = null;
 }
 return res;
 }

Quelqu'un comprend t-il mon problème ? Ce que je devrais faire pour que ça fonctionne ?
Le code ci-dessus de supprimer est celui de mon cours que le prof nous a donné sauf que je n'ai pas eu le temps de le recopier intégralement et il est semblerait-il faux.. J'ai essayé de le triturer dans tous les sens ca n'a pas marché c'est pourquoi je vous donne ici 'l'original'..
Ce serait bien sympa je n'en peux plus je suis dessus depuis plusieures heures

  • # je ne suis pas un pro en java

    Posté par . Évalué à 2.

    mais visiblement deja il manque des accolades fermantes }

    ensuite l'idée de l'algo c'est de trouver le "noeud" qu'on cherche
    de regarder s'il a des "enfants"
    puis de rattacher ces "enfants" au "grand-pere" puisqu'on va supprimer le pere.

    • [^] # Re: je ne suis pas un pro en java

      Posté par . Évalué à 1. Dernière modification le 04 janvier 2014 à 20:04.

      Merci pour ta réponse.
      Tu es sûr pour les accolades fermantes ? Je n'ai pas d'erreur de compilation pourtant...

      En fait je suis censé gérer 3 cas avec mon algo (cf wikipédia) :

      1) Suppression d'une feuille : Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
      2) Suppression d'un nœud avec un enfant : Il faut l'enlever de l'arbre en le remplaçant par son fils.
      3) Suppression d'un nœud avec deux enfants : Supposons que le nœud à supprimer soit appelé N. On échange le nœud N avec son successeur le plus proche (le nœud le plus à gauche du sous-arbre droit) ou son plus proche prédécesseur (le nœud le plus à droite du sous-arbre gauche).
      Puis on applique à nouveau la procédure de suppression à N, qui est maintenant une feuille ou un nœud avec un seul fils.

      Mon code ressemble a ceci actuellement et ne marche toujours pas :

       // Supprime un noeud a partir de sa valeur 
 public void remove(V val) {
 GenericBinaryTree<V> noeudConcerne, pereNoeud;
 // Le noeud concerné est celui qu'on veut supprimer
 noeudConcerne = this.trouverNoeud(val);
 // Si le noeud concerné a un sous arbre gauche
 if (noeudConcerne.SAG != null) {
 // pereNoeud est le pere du maximum du SAG du noeud
 pereNoeud = this.SAG.perMax();
 System.out.println("coucou1");
 // Si il est nul alors
 if (pereNoeud == null) {
 this.value = this.SAG.value;
 this.SAG = this.SAG.SAG;
 System.out.println("coucou2");
 } else {
 this.value = pereNoeud.SAD.value;
 pereNoeud.SAD = pereNoeud.SAD.SAG;
 System.out.println("coucou3");
 }
 }
 if (noeudConcerne.SAD != null) {
 // pereNoeud est le pere du minimum du SAD du noeud
 pereNoeud = this.SAD.perMin();
 System.out.println("coucou4");
 // Si il est nul alors
 if (pereNoeud == null) {
 System.out.println("coucou5");
 this.value = this.SAD.value;
 this.SAD = this.SAD.SAD;
 } else {
 System.out.println("coucou6");
 this.value = pereNoeud.SAG.value;
 pereNoeud.SAG = pereNoeud.SAG.SAD;
 }
 }
 }

      En algo la réponse me va très bien je la retranscrirai en java, mais c'est vraiment dur a trouver j'ai du mal avec la récursivité

      • [^] # Re: je ne suis pas un pro en java

        Posté par . Évalué à 2.

        En algo la réponse me va très bien je la retranscrirai en java, mais c'est vraiment dur a trouver j'ai du mal avec la récursivité

        en fait il faut pas se prendre la tete,
        la recursivité, c'est juste le fait d'appeler une fonction à l'interieur d'elle meme.

        dans ton cas, descendre dans le sous arbre de l'element que tu veux supprimer
        et pour chaque noeud, faire la recherche min/max
        pour repositionner chacun des enfants apres la suppression

        • [^] # Re: je ne suis pas un pro en java

          Posté par . Évalué à 1.

          dans ton cas, descendre dans le sous arbre de l'element que tu veux supprimer
          et pour chaque noeud, faire la recherche min/max
          pour repositionner chacun des enfants apres la suppression

          En fait quand je suis dans le sous arbre qui a pour racine le noeud a supprimer, que dois-je faire ? C'est a ce niveau que je bloque..
          Comment gérer le cas ou c'est une feuille aussi (on le supprime direct) ou encore qu'il a un seul sous-arbre sur les deux (ce qui fait que ce dernier doit remplacer le noeud a supprimer)...
          J'arrive pas a construire mon algo :s

          • [^] # Re: je ne suis pas un pro en java

            Posté par . Évalué à 2. Dernière modification le 05 janvier 2014 à 13:11.

            La programmation pour les "nuls" expliquée par NeoX

            A :
            fais toi un dessin avec tes etats (la racine en haut, comme pour les arbres genealogiques, on parle de descendre dans l'arbre pour atteindre les feuilles)

            • un arbre, 2 niveaux (1 racine, 2 feuilles) => tu supprimes la feuille
            • un arbre 3 niveaux (1 racines, 2 branches, 4 feuilles) => tu veux supprimer un noeud de niveau 2, comment tu ranges les noeuds sous le noeud que tu viens de supprimer.
            • un arbre avec N niveaux, c'est juste repeter les deux actions precedentes sur les sous arbres, chaque fois que tu deplaces (effaces) un noeud

            B :
            ecrit l'algo en francais.

            si c'est une feuille 
alors 
 // suppression du noeud
 action pour supprimer le noeud
sinon
 // c'est une branche qui a des feuilles ou un sous arbre
 action pour reclasser les feuilles ou le sous arbres
 rappel eventuel de la fonction ou je suis pour traiter le noeud en dessous.
finsi

            C :
            convertir l'algo dans le langage qui t'interesse, ici java

            • [^] # Re: je ne suis pas un pro en java

              Posté par . Évalué à 1.

              Merci NeoX je crois voir mieux comment construire mon algo !! Je m'y attèle demain des que j'ai un résultat je le poste :)

              • [^] # Re: je ne suis pas un pro en java

                Posté par . Évalué à 1. Dernière modification le 08 janvier 2014 à 20:49.

                Bon bein je n'ai rien trouvé de mieux que ca :'( , projet rendu :

                 // Cette méthode n'est pas la meilleure, mais faute de temps nous l'avons choisie... On recrée un arbre et on modifie les sous arbres 
 public V remove(V val) {
 // La premiere valeur de l'arbre qu'on recrée
 V premiereValeur = this.value;
 // Si la valeur a supprimer est la racine on change la racine
 if ((this.value).equals(val)) {
 // Si il y a un sous arbre gauche on prend sa valeur
 if (this.SAG != null) {
 premiereValeur = this.SAG.value;
 } // Sinon le sous arbre droit
 else {
 premiereValeur = this.SAD.value;
 }
 }
 // On stocke les valeurs actuelles de l'arbre
 ArrayList<V> listeValeurs = (ArrayList) this.values();
 // On crée notre arbre résultat
 GenericBinaryTree res = new GenericBinaryTree(premiereValeur);
 // Et on le remplit sans prendre la premiere valeur et celle a exclure
 for (V e : listeValeurs) {
 if (e != val && e != premiereValeur) {
 res.put(e);
 }
 }
 // Puis on recrée notre arbre
 this.value = premiereValeur;
 this.SAG = res.SAG;
 this.SAD = res.SAD;
 // Et on retourne la valeur sortie
 return val;
 }

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.