Partage
  • Partager sur Facebook
  • Partager sur Twitter

Problème avec un arbre avl

Perte de pointeurs !

Sujet résolu
    31 décembre 2021 à 16:25:54

    Je souhaite stocker des couleurs dans un arbre Avl cependant à la fin du programme certaines couleurs disparaissent de mon arbre. J'ai cherché le problème et cela vient de mes fonctions rotation que j'utilise dans insertion, durant leur fonctionnement je perds certains pointeurs mais je ne vois pas comment je les perds. Est-ce que vous savez d'où vient le problème ? 

    Je vous remercie d'avance pour votre aide. 

    Voici mon code : 

    struct avl {
      unsigned char* racine;
      struct avl *gauche;
      struct avl *droite;
      int hauteur;
      int element;
      int histogramme;
    };
    
    
    struct avl * nouvelarbreAVL(unsigned char r, unsigned char g, unsigned char b, unsigned char a) {
      struct avl *arbre;
      arbre = malloc(sizeof(struct avl));
      if (arbre == NULL)
        return NULL;
      arbre->racine = malloc(4*sizeof(unsigned char));
      if(arbre->racine == NULL)
        return NULL;
      arbre->racine[0]   = r;
      arbre->racine[1]   = g;
      arbre->racine[2]   = b;
      arbre->racine[3]   = a;
      arbre->hauteur     = 1;
      arbre->element     = 1;
      arbre->histogramme = 1;
      arbre->gauche      = NULL;
      arbre->droite      = NULL;
      return arbre;
    }
    int max_2(int a, int b) {
      if(a < b) {
        return b;
      } else {
        return a;
      }
    }
    int hauteur_arbre(struct avl *arbre) {
      if(arbre == NULL)
        return 0;
      return arbre->hauteur;
    }
    
    int nombre_element(struct avl *arbre) {
      if(arbre == NULL)
        return 0;
      return arbre->element;
    }
    
    int diff_hauteur(struct avl *arbre) {
      if( arbre == NULL)
        return 0;
      return hauteur_arbre(arbre->droite) - hauteur_arbre(arbre->gauche);
    }
    void miseajour_element(struct avl *arbre) {
      arbre->element = 1 + nombre_element(arbre->droite) + nombre_element(arbre->gauche);
    }
     
    void miseajour_hauteur(struct avl *arbre) {
      arbre->hauteur = 1 + max_2(hauteur_arbre(arbre->droite), hauteur_arbre(arbre->gauche));
    }
    
    struct avl *rotation_droite(struct avl *arbre) {
      if(arbre == NULL)
        return NULL;
      struct avl *arbre_bis  = arbre->gauche;
      arbre->gauche = arbre->gauche->droite;
      miseajour_hauteur(arbre);
      arbre_bis->droite = arbre;
      miseajour_hauteur(arbre_bis);
      return arbre_bis;
    }
    
    
    struct avl *rotation_gauche(struct avl *arbre) {
      if(arbre == NULL)
        return NULL;
      struct avl *arbre_bis = arbre->droite;
      arbre->droite = arbre->droite->gauche;
      miseajour_hauteur(arbre);
      arbre_bis->gauche = arbre;
      miseajour_hauteur(arbre_bis);
      return arbre_bis;
    }
    
    
    struct avl *insertion(unsigned char *v, struct avl *arbre) {
      if(arbre == NULL) {
        arbre = nouvelarbreAVL(v[0], v[1], v[2], v[3]);
        return arbre;
      }
      
      if(v[0] != arbre->racine[0]) {
        if(v[0] < arbre->racine[0]){
          arbre->gauche = insertion(v, arbre->gauche);
        } else {
          arbre->droite = insertion(v, arbre->droite);
        }
      } else if (v[1] != arbre->racine[1]) {
        if(v[1] < arbre->racine[1]){
          arbre->gauche = insertion(v, arbre->gauche);
        } else {
          arbre->droite = insertion(v, arbre->droite);
        }
      } else if (v[2] != arbre->racine[2]) {
        if(v[2] < arbre->racine[2]){
          arbre->gauche = insertion(v, arbre->gauche);
        } else {
          arbre->droite = insertion(v, arbre->droite);
        }
      } else {
        arbre->histogramme++;
        return arbre;
      }
      /* Après l'insertion de l'élément dans l'arbre, on doit mettre à jour la hauteur de chaque arbre. */
      
      miseajour_hauteur(arbre);
      miseajour_element(arbre);
      
      /* On vérifie si ce sont toujours des arbres AVL, si ce n'est pas le cas on effectue les rotations nécessaire.*/
      
      if(diff_hauteur(arbre) > 1) {
        if(diff_hauteur(arbre->droite) == 1) {
          arbre = rotation_gauche(arbre);
        } else if (diff_hauteur(arbre->droite) == -1) {
          arbre->droite = rotation_droite(arbre->droite);
          arbre = rotation_gauche(arbre);
        }
      } else if(diff_hauteur(arbre) < -1) {
        if(diff_hauteur(arbre->gauche) == -1){
          rotation_droite(arbre);
        } else if(diff_hauteur(arbre->gauche) == 1) {
          arbre->gauche = rotation_gauche(arbre->gauche);
          arbre = rotation_droite(arbre);
        }
      }
      return arbre;
    }
    
    void parcours(struct avl *arbre) {
      if(arbre == NULL)
        return;
      parcours(arbre->gauche);
      printf("%d , %d , %d \n", arbre->racine[0],arbre->racine[1], arbre->racine[2]);
      parcours(arbre->droite);
    }
    void free_avl(struct avl *arbre) {
      if(arbre == NULL)
        return;
      free_avl(arbre->gauche);
      free_avl(arbre->droite);
      free(arbre->racine);
      free(arbre);
    }



    -
    Edité par Dovakiine 31 décembre 2021 à 16:26:56

    • Partager sur Facebook
    • Partager sur Twitter
      31 décembre 2021 à 17:33:20

      Bonjour,

      sais-tu utiliser un debuger ?

      • Partager sur Facebook
      • Partager sur Twitter
        31 décembre 2021 à 17:40:06

        White Crow a écrit:

        Bonjour,

        sais-tu utiliser un debuger ?


        Non je ne sais pas. J'utilise seulement valgrind (je ne sais pas si c'est cela un debuger) et il renvoie aucune erreur. J'ai commencé la programmation il y a moins de 4 mois.
        • Partager sur Facebook
        • Partager sur Twitter
          31 décembre 2021 à 17:50:25

          valgrind est un memory profiler ; il te sera très utile pour détecter les erreurs de gestion de mémoire.

          La première chose à faire est de compiler ton projet en ajoutant ce qu'il faut pour avoir un peu plus de warnings que le défaut. Cela signifie compiler en rajoutant les options -Wall et -Wextra. Il va falloir faire attention aux éventuels messages …

          Il va aussi falloir compiler en ajoutant les informations de débogage, pour cela il faut rajouter l'option -g.

          Une fois que tu as fais cela tu peux dans un premier temps lancer ton exécutable avec valgrind enl'utilisant ainsi :

          valgrind --leak-check=full --track-origins=yes --show-reachable=yes ./ton_executable

          En ce qui concerne le débogage à proprement parler, tu as le choix entre un gdb en interface textuelle ou des GUI comme nemiver ou DDD. L'idée est de placer un point d'arrêt dans ton programme puis de l'exécuter pas à pas en inspectant la valeur des variables …

          Je suppose que tu es sous linux si tu utilises valgrind … mais peut-être pourrais-tu en dire plus sur ton environnement.

          Tu sais, c'est indispensable de savoir utiliser ces outils … parce que débuguer par forum c'est vraiment très lent.

          • Partager sur Facebook
          • Partager sur Twitter
            31 décembre 2021 à 18:32:22

            Je n'ai pas regardé en détail, mais tu devras sauver un pointeur.
            Et fais bien attention de l'ordre dans lequel tu fais les opérations. C'est facile de se tromper.
            et testes si les fils et le grand-père sont non NULL.
            Petit essai:
            sauver = noeud.pere
            noeud.pere = sauver.pere
            noeud.pere.gauche = noeud
            sauver.pere = noeud
            sauver.gauche = noeud.droit
            noeud.droit.pere = sauver
            noeud.droit = sauver
            Et inversement pour l'autre rotation.
            • Partager sur Facebook
            • Partager sur Twitter

            Le Tout est souvent plus grand que la somme de ses parties.

              31 décembre 2021 à 18:34:24

              Dovakiine a écrit:

              White Crow a écrit:

              valgrind est un memory profiler ; il te sera très utile pour détecter les erreurs de gestion de mémoire.

              La première chose à faire est de compiler ton projet en ajoutant ce qu'il faut pour avoir un peu plus de warnings que le défaut. Cela signifie compiler en rajoutant les options -Wall et -Wextra. Il va falloir faire attention aux éventuels messages …

              Il va aussi falloir compiler en ajoutant les informations de débogage, pour cela il faut rajouter l'option -g.

              Une fois que tu as fais cela tu peux dans un premier temps lancer ton exécutable avec valgrind enl'utilisant ainsi :

              valgrind --leak-check=full --track-origins=yes --show-reachable=yes ./ton_executable

              En ce qui concerne le débogage à proprement parler, tu as le choix entre un gdb en interface textuelle ou des GUI comme nemiver ou DDD. L'idée est de placer un point d'arrêt dans ton programme puis de l'exécuter pas à pas en inspectant la valeur des variables …

              Je suppose que tu es sous linux si tu utilises valgrind … mais peut-être pourrais-tu en dire plus sur ton environnement.

              Tu sais, c'est indispensable de savoir utiliser ces outils … parce que débuguer par forum c'est vraiment très lent.

              e suis sur linux. Je suis entrain de voir le débuguer de gdb. En fait, je sais que le problème vient de mes fonctions rotation car lorsque je ne les utilise pas tout fonctionne bien. Lorsque j'utilise votre ligne de commande pour valgrind, il me dit que je perd des malloc. Donc j'en conclu que mes fonctions rotations me font perdre des pointeurs et que je peux plus atteindre l'espace de ces pointeurs. Mais je ne vois pas à quel moment je les perds. 

              Veuillez bien m'excuser du manque de précision de mes paroles sur ce sujet. Je n'avais jamais fait de programmation avant. 

              PierrotLeFou a écrit:

              Je n'ai pas regardé en détail, mais tu devras sauver un pointeur.
              Et fais bien attention de l'ordre dans lequel tu fais les opérations. C'est facile de se tromper.
              et testes si les fils et le grand-père sont non NULL.
              Petit essai:
              sauver = noeud.pere
              noeud.pere = sauver.pere
              noeud.pere.gauche = noeud
              sauver.pere = noeud
              sauver.gauche = noeud.droit
              noeud.droit.pere = sauver
              noeud.droit = sauver
              Et inversement pour l'autre rotation.

              Oui le problème est la je n'arrive pas à sauver mon pointeur, c'est surement l'ordre de mes opérations qui doit provoquer ce problème. Je n'ai pas très bien compris ton petit essai, dans mon arbre je n'ai pas de père, j'ai seulement le fils gauche et droite. 



              -
              Edité par Dovakiine 31 décembre 2021 à 19:10:59

              • Partager sur Facebook
              • Partager sur Twitter
                31 décembre 2021 à 19:13:03

                ligne 130
                • Partager sur Facebook
                • Partager sur Twitter

                En recherche d'emploi.

                  31 décembre 2021 à 19:38:33

                  Dalfab a écrit:

                  ligne 130




                  Merci beaucoup de ton aide, c'est incroyable j'ai lu des dizaines de fois ce passage et je ne l'ai jamais vu. Normalement le problème est réglé. 

                  Merci beaucoup White Crow et PierrotLeFou pour votre aide !

                  • Partager sur Facebook
                  • Partager sur Twitter
                    31 décembre 2021 à 22:17:10

                    Normalement, en tant que débutant, ça devrait te prendre environ 1H avec un debuger …
                    • Partager sur Facebook
                    • Partager sur Twitter

                    Problème avec un arbre avl

                    × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                    • Editeur
                    • Markdown