[JAVA] Suppression dans un arbre binaire ordonné

Suppression dans un arbre binaire ordonné [JAVA] - Java - Programmation

Marsh Posté le 04-01-2014 à 13:24:56    

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 :
 

Code :
  1. public class GenericBinaryTree<V> {
  3.     // ATTRIBUTS
  4.     private Comparable value;
  5.     private GenericBinaryTree SAD;
  6.     private GenericBinaryTree SAG;
  8.     // CONSTRUCTEUR
  9.     public GenericBinaryTree(Comparable val) {
  10.         this.value = val;
  11.         this.SAD = null;
  12.         this.SAG = null;
  13.     }


 
Toutes ses méthodes fonctionnent sauf supprimer que voici :

Code :
  1. // Supprime un noeud a partir de sa valeur  
  2.     public void remove(Comparable val) {
  4.         GenericBinaryTree noeudConcerne, pereNoeud;
  7.         // Le noeud concerné est celui qu'on veut supprimer
  8.         noeudConcerne = this.trouverNoeur(val);
  11.         // On regarde d'abord du coté du SAG du noeud concerné, si il n'est pas nul
  12.         if (noeudConcerne.SAG != null) {
  13.             // pereNoeud est le pere du maximum du SAG du noeud
  14.             pereNoeud = this.SAG.perMax();
  15.             // Si il est nul alors
  16.             if (pereNoeud == null) {
  17.                 this.value = this.SAG.value;
  18.                 this.SAG = this.SAG.SAG;
  19.             } else {
  20.                 this.value = pereNoeud.SAD.value;
  21.                 pereNoeud.SAD = pereNoeud.SAD.SAG;
  22.             }
  24.         }
  25.         // Faire pareil avec sous arbre droit et perMin
  26.     }


 
 
Qui utilise les fonctions suivantes (qui fonctionnent) :
 
 

Code :
  1. // Renvoie le noeud associé a une valeur
  2.     public GenericBinaryTree trouverNoeur(Comparable val) {
  4.         // Si on est au niveau de la valeur recherchée on la selectionne
  5.         if ((this.value).compareTo(val) == 0) {
  6.             return this;
  7.         } else {
  8.             // Sinon on regarde dans le SAG si la valeur est inférieure
  9.             if ((this.value.compareTo(val)) < 0) {
  10.                 if (this.SAG != null) {
  11.                     return this.SAG.trouverNoeur(val);
  12.                 } else {
  13.                     // Si pas de sous arbre gauche, la valeur n'est pas la
  14.                     return null;
  15.                 }
  16.             } else {
  17.                 // Idem SAD si la valeur est supérieure
  18.                 if (this.SAD != null) {
  19.                     return this.SAD.trouverNoeur(val);
  20.                 } else {
  21.                     return null;
  22.                 }
  23.             }
  24.         }
  25.     }
  27.     // Retourne le pere de l'arbre avec la valeur maximale
  28.     public GenericBinaryTree perMax() {
  29.        
  30.         // On initialise la variable résultat
  31.         GenericBinaryTree res = new GenericBinaryTree("error" );
  32.         /* On va chercher quand le SAD s'arrête, quand c'est le cas, on choisit
  33.          * le noeud "grand pere" de cet arbre pour obtenir le pere du max
  34.          */
  35.         if (this.SAD != null) {
  36.             if (this.SAD.SAD == null) {
  37.                 res = this;
  38.             } else {
  39.                 res = this.SAD.perMax();
  40.             }
  41.         } else {
  42.             // Si l'arbre est trop petit on retourne null
  43.             res = null;
  44.         }
  45.         return res;
  46.     }
  48.     // Retourne le pere de l'arbre avec la valeur minimale
  49.     public GenericBinaryTree perMin() {
  50.         // On initialise la variable résultat
  51.         GenericBinaryTree res = new GenericBinaryTree("error" );
  52.         /* On va chercher quand le SAG s'arrête, quand c'est le cas, on choisit
  53.          * le noeud "grand pere" de cet arbre pour obtenir le pere du min
  54.          */
  55.         if (this.SAG != null) {
  56.             if (this.SAG.SAG == null) {
  57.                 res = this;
  58.             } else {
  59.                 res = this.SAG.perMin();
  60.             }
  61.         } else {
  62.             // Si l'arbre est trop petit on retourne null
  63.             res = null;
  64.         }
  65.         return res;
  66.     }


 
 
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


Message édité par Odenelle le 04-01-2014 à 14:11:46
Reply

Marsh Posté le 04-01-2014 à 13:24:56   

Reply

Marsh Posté le 04-01-2014 à 13:44:00    

Il me semble que la ligne 59 du dernier extrait de code soit fautive, et donc que cela impacte la partie (qui ne nous est pas montrée) à partir de la ligne 25 du deuxième extrait.
 [:mrdoug]

Reply

Marsh Posté le 04-01-2014 à 14:08:45    

Merci pour ta réponse olivthill en effet j'ai utilisé perMax au lieu de perMin ! je le corrige.
Cependant la partie qui n'est pas montrée, c'est parce qu'elle n'existe pas et je ne vois d'ailleurs pas comment la construire :s, il s'agit de notes que j'ai prises en cours


Message édité par Odenelle le 04-01-2014 à 14:16:14
Reply

Marsh Posté le 04-01-2014 à 14:43:21    

On peut imaginer que la partie manquante serait :

       if (noeudConcerne.SAD != null) {
            // pereNoeud est le pere du minimum du SAD du noeud
            pereNoeud = this.SAD.perMin();
            // Si il est nul alors
            if (pereNoeud == null) {
                this.value = this.SAD.value;
                this.SAD = this.SAD.SAD;
            } else {
                this.value = pereNoeud.SAG.value;
                pereNoeud.SAG = pereNoeud.SAG.SAD;
            }
        }

Reply

Marsh Posté le 04-01-2014 à 15:01:55    

J'avais essayé ça mais ça m'a donné quelque chose de très bizarre, la suppression ne se fessait pas comme prévu (au lieu de supprimer un nœud cela me le mettait en racine de l'arbre par exemple)..  
 
D'autre part je ne sais pas comment gérer la suppression d'un nœud s'il s'agit d'une feuille car faire

Code :
  1. leNoeudaSupprimer = null

ou encore

Code :
  1. leNoeudaSupprimer.value = null

est interdit  (cela génère des erreurs au niveau de la mise a jour de l'interface par la suite..).


Message édité par Odenelle le 04-01-2014 à 15:03:16
Reply

Marsh Posté le 04-01-2014 à 15:18:40    

Remove est comme ceci actuellement :

Code :
  1. // Supprime un noeud a partir de sa valeur  
  2.     public void remove(Comparable val) {
  4.         GenericBinaryTree noeudConcerne, pereNoeud;
  7.         // Le noeud concerné est celui qu'on veut supprimer
  8.         noeudConcerne = this.trouverNoeud(val);
  11.         // Si le noeud concerné a un sous arbre gauche
  12.         if (noeudConcerne.SAG != null) {
  13.             // pereNoeud est le pere du maximum du SAG du noeud
  14.             pereNoeud = this.SAG.perMax();
  15.             System.out.println("coucou1" );
  16.             // Si il est nul alors
  17.             if (pereNoeud == null) {
  18.                 this.value = this.SAG.value;
  19.                 this.SAG = this.SAG.SAG;
  20.                 System.out.println("coucou2" );
  21.             } else {
  22.                 this.value = pereNoeud.SAD.value;
  23.                 pereNoeud.SAD = pereNoeud.SAD.SAG;
  24.                 System.out.println("coucou3" );
  25.             }
  27.         }
  28.        
  29.         if (noeudConcerne.SAD != null) {
  30.             // pereNoeud est le pere du minimum du SAD du noeud
  31.             pereNoeud = this.SAD.perMin();
  32.             System.out.println("coucou4" );
  33.             // Si il est nul alors
  34.             if (pereNoeud == null) {
  35.                 System.out.println("coucou5" );
  36.                 this.value = this.SAD.value;
  37.                 this.SAD = this.SAD.SAD;
  38.             } else {
  39.                 System.out.println("coucou6" );
  40.                 this.value = pereNoeud.SAG.value;
  41.                 pereNoeud.SAG = pereNoeud.SAG.SAD;
  42.             }
  43.         }
  44.     }

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed