Arbre binaire de recherche

**todor** · 04/06/2008, 00h01

Bonsoir,

Je dois faire une bibliothèque de manipulation d'arbres binaires de recherche. Tout se passe bien (test effectués) sauf au moment de la suppression d'une feuille. En effet la fonction free ne libère pas l'objet pointé retourné par la fonction de recherche dans l'arbre. Je suis vraiment coincé et j'apprécirai toute aide. De plus si vous avez d'autres idées pour cette fonction ou mêmes les autres, elles sont les bienvenues.

Le fichier d'en-tête abr.h :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifndef ABR_H
#define ABR_H
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef struct abr *abr;
 
abr creer_abr(int cle, void *objet);
 
bool abr_vide(abr a);
 
void inserer_abr(abr a, void *objet, int cle);
 
void *chercher_abr_obj(int cle, abr a);
 
bool supprimer_abr(int cle, abr a);
 
#endif /*ABR_H*/

Et le fichier abr.c sans la fonction suppression :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "abr.h"
 
struct abr
{
  void *objet;
  int cle;
  abr gauche;
  abr droit;
};
 
abr
creer_abr(int cle, void *objet)
{
  abr a = malloc(sizeof(struct abr));
  a->objet = objet;
  a->gauche = NULL;
  a->droit = NULL;
  a->cle = cle;
 
  return a;
}
 
bool
abr_vide(abr a)
{
  return (a == NULL);
}
 
static void
inserer_abr_aux(abr noeud, abr a)
{
  if(abr_vide(a))
    a = noeud;
  if(noeud->cle <= a->cle)
    {
      if(a->gauche == NULL)
	a->gauche = noeud;
      else
	inserer_abr_aux(noeud, a->gauche);
    }
  else
    {
      if(a->droit == NULL)
	a->droit = noeud;
      else
	inserer_abr_aux(noeud, a->droit);
    }
}
 
void
inserer_abr(abr a, void *objet, int cle)
{
  abr noeud = creer_abr(cle, objet);
  inserer_abr_aux(noeud, a);
}
 
static abr
chercher_abr(int cle, abr a)
{
  if(abr_vide(a))
    return NULL;
  if(a->cle == cle)
    return a;
  if(cle <= a->cle)
    {
      if(a->gauche != NULL)
	return chercher_abr(cle, a->gauche);
      else
	return NULL;
    }
  else
    {
      if(a->droit != NULL)
	return chercher_abr(cle, a->droit);
      else
	return NULL;
    }
}
 
void *chercher_abr_obj(int cle, abr a)
{
     abr tmp = chercher_abr(cle, a);
     if(tmp != NULL)
       return tmp->objet;
     return NULL;
}
 
static abr
max_abr(abr a)
{
  assert(!abr_vide(a));
  if(a->gauche == NULL && a->droit == NULL)
    return a;
  else if(a->droit == NULL)
    return a->gauche;
  else
    return max_abr(a->droit);
}

Et voici la dernière fonction qui pose problème (la ligne de l'erreur est suivie d'un commentaire)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool
supprimer_abr(int cle, abr a)
{
  if(abr_vide(a))
    return false;
  abr tmp3 = chercher_abr(cle, a);
  assert(tmp3 != NULL);
  if(tmp3->gauche == NULL && tmp3->droit == NULL)
    {
      free(tmp3->objet); //ceci est bien libéré
      tmp3->objet = NULL;
      free(tmp3);    //LE PROBLEME EST ICI, LE NOEUD POINTÉ PAR tmp3 N'EST PAS LIBERE, assert
      tmp3 = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }  
  if(tmp3->gauche == NULL)
    {
      abr tmp = tmp3->droit;
      free(tmp3->objet);
      tmp3->objet = tmp->objet;
      tmp3->cle = tmp->cle;
      tmp3->gauche = tmp->gauche;
      tmp3->droit = tmp->droit;
      free(tmp);
      tmp = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }
  else if(tmp3->droit == NULL)
    {
      abr tmp = tmp3->gauche;
      free(tmp3->objet);
      tmp3->objet = tmp->objet;
      tmp3->cle = tmp->cle;
      tmp3->gauche = tmp->gauche;
      tmp3->droit = tmp->droit;
      free(tmp);
      tmp = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }
  else
    {
      abr tmp = max_abr(tmp3);
      free(tmp3->objet);
      tmp3->objet = tmp->objet;
      tmp3->cle = tmp->cle;
      if(tmp->gauche != NULL)
	tmp3->gauche = tmp->gauche;
      free(tmp);
      tmp = NULL;
      assert(chercher_abr(cle, a) == NULL);
      return true;
    }
}

**Médinoc** · 04/06/2008, 09h09

Sur le coup, je ne vois pas trop d'où vient l'erreur.
Mais je pense que tu devrais suivre une autre approche pour la suppression:

D'abord retirer le nœud de l'arbre (c'est là que tu fais tes décalages de pointeurs etc.)
Puis le détruire, sans dupliquer le code de destruction.

PS: Ce typedef est très mauvais:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

typedef struct abr *abr;

Tu ne dois pas donner à un type pointeur le même nom que la structure, ça apporte trop de confusion. Par contre, tu peux faire ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

typedef struct abr abr, *pabr;

Ou mieux, le mettre en majuscules:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

typedef struct abr ABR, *PABR;

**Médinoc** · 04/06/2008, 09h10

Ah, j'ai trouvé!
Ton assert foire justement parce que tu n'as pas retiré le noeud de l'arbre avant de faire ton free: Tu as vérifié que le noeud n'avait pas de fils, mais tu ne l'as pas séparé de son père...

**todor** · 04/06/2008, 13h40

Justement, j'ai pensé à cela. Mais ce qui m'étonne c'est que je le mets à NULL ce pointeur. Du coup son papa pointe vers NULL. Puis tous les autres assert marchent.

Merci pour le conseil pour le typedef.

J'essayrai une autre approche, notamment en ayant un pointeur sur le père ce qui me permettra de libérer son fils. Mais j'aimerais bien comprendre pourquoi ce pointeur ne se libère pas...

**Médinoc** · 04/06/2008, 14h17

Je ne vois pas où tu mets à NULL ce pointeur. Ta fonction ne touche absolument pas au père...

Si tu veux séparer le fils, tu peux faire ça:

Code C99 :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static abr
chercher_abr(int cle, abr a, bool detach, abr *pDetach)
{
	if(abr_vide(a))
		return NULL;
	if(a->cle == cle)
	{
		if(detach && pDetach!=NULL)
			*pDetach = NULL;
		return a;
	}
 
	if(cle <= a->cle)
	{
		/*Le test if(a->gauche != NULL) n'est pas indispensable,
		  car testé par arbre_vide() */
		return chercher_abr(cle, a->gauche, detach, &a->gauche);
	}
	else
	{
		return chercher_abr(cle, a->droit, detach, &a->droit);
	}
}

Cette version modifiée de la fonction reçoit l'adresse du pointeur qu'elle teste.
Ainsi, elle peut mettre ledit pointeur à NULL si demandé.

**todor** · 04/06/2008, 14h53

Merci beaucoup. Cela m'aide énormément. Je revoie mon code, modifie tout ça et te donnerai des nouvelles.

Arbre binaire de recherche

C

Vue hybride

Discussions similaires

Partager

Partager