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

Posté par . Licence CC by-sa
Tags : aucun
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/01/14 à 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/01/14 à 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/01/14 à 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 à ceux qui les ont postés. Nous n'en sommes pas responsables.