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

Bonjour,

sais-tu utiliser un debuger ?

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.

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.

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.

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

ligne 130

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 !

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