Supprimer tous les éléments inférieurs à une valeur dans un ABR

Version imprimable

Bonjour à tous (et Joyeuses Fetes)!
Je réalise un programme gérant un certain nombre d'opérations dans un arbre binaire de recherche.
Mon arbre stocke des heures et mon probleme ici se trouve sur une fonction chargée de supprimer toutes les heures inférieures à une certaine heure (ici le temps actuel, mais le problème n'est pas là).
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 void clear(t_arbre * arbre, float currenttime){ if (arbre!=NULL) { float tmp; while (min(arbre)<currenttime) { t_arbre *courant=arbre; while (courant->g!=NULL) { courant=courant->g; tmp=courant->aterrissage; } if (tmp<currenttime) suppress(&courant,tmp); } } }
La fonction suppress (void suppress(t_arbre **root, float arrivee) ) est une fonction qui supprime le noeud de l'arbre dont la valeur est entrée en paramètre (et elle marche). Quelqu'un sait pourquoi ma fonction ne marche pas? (la 1ere fois que je l'appelle elle ne fait rien (ne supprime pas la valeur pourtant inférieure au temps courant, la 2e fois elle segfault alors que rien n'a changé)

26/12/2014, 20h41
Sve@r

Salut

Je t'avais déjà donné des conseils sur ta liste chainée (http://www.developpez.net/forums/d14...ainee-ordonnee). Si tu les avais appliqués aussi pour ton arbre et créé une structure pour l'arbre lui-même, jamais t'aurais eu à manipuler des doubles étoiles comme avec ton suppress(t_arbre **root) et peut-être que la fonction min() disparaitra (vu que le min pourra être stocké dans la structure de l'arbre). Accessoirement ton type "t_arbre" ressemblerait plutôt à un type "t_noeud".

Maintenant ta fonction clear() semble correcte (même si on ne sait pas trop pourquoi elle ne s'occupe que de la branche gauche) mais je ne suis pas certain du reste surtout quand tu appelles suppress() en lui passant l'adresse d'une variable locale. Quoi qu'il en soit il faudrait aussi avoir le code de cette fonction ainsi que la façon dont tu appelles la fonction clear()...

Salut
Je suis d'accord pour le type t_arbre, dans les quelques programmes que j'avais vu en cours C, c'était "arbre *" donc j'ai mis t_arbre, mais effectivement c'est un abus de langage. Pour les ** au début je pensais pas en avoir besoin, mais finalement si, c'est vrai que j'aurais du créer un type, mais je pensais peut etre naivement savoir ce que je faisais :lol:.
Pour ma fonction, je ne m'occupe que de la branche gauche parce que je supprime toujours l'élément minimum, qui est toujours à gauche (si ce n'est pas la racine)... La fonction suppress() se charge de gérer la suppression pour que l'arbre soit toujours un ABR, du coup si on supprime toujours le minimum, jamais il pourra être à droite, au plus ça sera la racine. (Ai-je faux?).
Quant à ladite fonction (qui prise individuellement marche très bien) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void suppress(t_arbre **root, float arrivee) {
   t_arbre *tmp;
   float tampon;
   if (root==NULL) return;                              //arbre vide
   if (arrivee<(*root)->aterrissage)                    /*on cherche où serait suceptible de se trouver l'arrivee entrée en faisant une récursion sur les fils en comparant arrivee et la valeur du noeud actuel*/
      suppress(&((*root)->g), arrivee);
   else if( (*root)->aterrissage < arrivee )
                suppress( &((*root)->d), arrivee);
   else {       //ie on a trouvé le noeud à supprimer
        if (((*root)->d == NULL) && ((*root)->g==NULL)) {
//1er cas : il s'agit d'une feuille : il suffit de la supprimer
            free(*root);
            *root = NULL;
        }
/*2e cas : le noeud à supprimer a un seul fils : on remplace le noeud par son fils on le supprime*/
        else if( (*root)->g != NULL && (*root)->d==NULL) {
            tmp = (*root)->g;
            free(*root);
            *root = tmp;
        }
        else if((*root)->g==NULL && (*root)->d!=NULL) {
            tmp = (*root)->d;
            free(*root);
            *root=tmp;
        }
        else {
/*3e cas : le noeud à supprimer possède 2 fils : on remplace ce noeud par la plus grande valeur de son  sous arbre gauche (on peut aussi prendre la plus petite du sous arbre droit) et on fait la récursion à nouveau sur ce noeud, qui est maintenant une feuille ou un noeud ne possédant qu'un fils*/
            tampon = max((*root)->g);
            suppress(root, tampon);
            (*root)->aterrissage = tampon;
        }
    }
}

27/12/2014, 12h07
Sve@r

Ok, c'est exact. Dans un ABR si t'as l'élément le plus petit à gauche tu ne t'occupes que de la branche gauche.
Ta fonction suppress() a l'air correcte (il faudrait une simulation papier pour vérifier que tout est géré mais à priori ça a l'air bon). Accessoirement tu as des parenthèses en trop => suppress(&(*root)->g, arrivee).

Ce qui me chagrine, c'est que ta fonction suppress() qui est sensée modifier l'arbre reçoit donc l'adresse d'un noeud (qui étant lui-même une adresse implique que ce paramètre reçu soit stocké dans un t_arbre **) mais pas ta fonction clear() ? Pourtant cette fonction est aussi sensée modifier l'arbre reçu non ??? C'est un petit peu pour ça que dans mon post précédent je te demandais la façon dont tu l'appelles...
27/12/2014, 15h36
Ryzen

Ah oui je vois ce que tu veux dire... Pourtant quand je passe l'adresse de courant, c'est bien celle du nœud en question, l'autre fonction devrait la comprendre non?
Par contre le fait que clear devrait prendre un ** je suis d'accord (je l'ai modifié en clear(t_arbre **root, float arrivee) avec courant=(*root) (mais ça segfault quand même)).

Du coup je suis censé faire comment pour que la fonction suppress comprenne l'adresse que je lui passe? (j'ai naïvement tenté des trucs comme t_arbre **courant, *courant=(*courant)->suivant ou t_arbre **rootcur=&courant, mais la réponse du programme n'est pas très amicale!)

Citation:

Envoyé par Ryzen

Du coup je suis censé faire comment pour que la fonction suppress comprenne l'adresse que je lui passe? (j'ai naivement tenté des trucs comme "t_arbre **courant, (*courant=(*courant)->suivant) ou t_arbre **rootcur=&courant, mais la réponse du programme n'est pas très amicale!)

Sans avoir le reste du code c'est pas évident mais à mon avis, c'est comme ça que tu devrais l'écrire
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 void clear(t_arbre ** arbre, float currenttime){ if (*arbre == NULL) return; float tmp; while (min(*arbre)<currenttime) { t_arbre **courant=arbre; while ((*courant)->g != NULL) { *courant=(*courant)->g; tmp=(*courant)->aterrissage; } if (tmp<currenttime) suppress(courant,tmp); } }
Et appeler clear() exactement de la même façon que tu appelles suppress()...

27/12/2014, 17h33
Ryzen

Ah oui j'avais la même chose, mais en fait je crois que l'erreur ne vient pas de là...
Par contre j'ai remarqué une erreur (et je ne vois pas vraiment d'où elle vient) dans la fonction suppress : si j'essaye de supprimer une valeur qui n'est pas dans l'arbre, j'ai une segfault. C'est peut-être lié au fait que la fonction clear() plante (mais je ne vois vraisemblablement pas pourquoi), gdb ne veut pas m'en dire plus!
27/12/2014, 19h42
Sve@r

Citation:

Envoyé par Ryzen

gdb ne veut pas m'en dire plus!

Oui ben avant gdb t'as printf(). Si tu regardes mon exemple de liste chainée, tu verras que je ne m'en prive pas !!!

Tu dis que ta fonction suppress() ne fonctionne pas quand on lui passe une valeur "arrivee" qui n'est pas dans l'arbre. Mais nulle part tu testes l'égalité entre "arrivee" et les valeurs stockées dans les noeuds. T'as un test inférieur, un test supérieur et c'est tout (tu devrais d'ailleurs les mettre dans le même sens pour qu'on les lise plus facilement).

Ce qu'il te faut, c'est afficher un petit arbre témoin (avec 7 ou 15 noeuds) depuis le départ (affichage complet, avec les adresses des noeuds ainsi que les valeurs stockées dans les fils g/d) puis après que tu lui ai appliqué une suppression...
27/12/2014, 21h41
Ryzen

En fait dans la fonction suppress, il manquait simplement un condition (on ne peut pas envoyer l'adresse du fils si celui-ci n'existe pas) quant à clear(), il y avait une boucle infinie (assez bizarre) quelque part, j'ai préféré faire autrement, il suffit d'aller suppress sur root tant que le minimum est inférieur au temps courant!
28/12/2014, 13h48
Sve@r

Citation:

Envoyé par Ryzen

quant à clear(), il y avait une boucle infinie (assez bizarre) quelque part

Ouais super. "quelque part". Punaise, faut vraiment que tu poses de vraies bases avant de te mettre à coder...