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

Posté par Odenelle le 04 janvier 2014 à 13:31. Licence CC By‑SA.

Étiquettes : aucune

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 NeoX le 04 janvier 2014 à 19:13. É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 Odenelle le 04 janvier 2014 à 19:36. É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 NeoX le 04 janvier 2014 à 20:09. É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 Odenelle le 05 janvier 2014 à 00:41. É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 NeoX le 05 janvier 2014 à 13:09. É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 Odenelle le 05 janvier 2014 à 15:34. É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 Odenelle le 08 janvier 2014 à 17:21. É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; }
        
        [^] # Re: je ne suis pas un pro en java
        
        Posté par NeoX le 08 janvier 2014 à 20:48. Évalué à 2.
        
        c'est quand meme bien bourrin
        et c'est pas recursif,
        
        j'imagine meme pas la note du TP :p

Suivre le flux des commentaires

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