Problème suppression dans un arbre

Version imprimable

Bonjour,
Je révisais mon cours sur les arbres et il y a quelquechose que je n'arrive pas à comprendre.
Voici la structure d'arbre :

Code:

1
2
3
4
5
6
7
8
9
 
typedef struct Noeud Noeud;
struct Noeud
{
    int info;
    struct Noeud* sag;
    struct Noeud* sad;
};
typedef struct Noeud* Ptr_noeud;

Et voila l'algo de suppression d'un élément :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
int supprimer(Ptr_noeud *tete, int x)
{
    Ptr_noeud tmp = NULL, max = NULL;
    Ptr_noeud *pp = NULL;
    int ok = 0;
 
    if ((*tete) != NULL)
    {
        if ((*tete)->info < x)
        {
            supprimer(&((*tete)->sad), x);
        }
        else if ((*tete)->info > x)
        {
            supprimer(&((*tete)->sag), x);
        }
        else
        {
            ok = 1;
 
            if ((*tete)->sag == NULL)
            {
                tmp = (*tete);
                (*tete) = (*tete)->sad;
                free(tmp);
            }
            else if ((*tete)->sad == NULL)
            {
                tmp = (*tete);
                (*tete) = (*tete)->sag;
                free(tmp);
            }
            else
            {
				pp = &((*tete)->sag);
 
				while ((*pp)->sad != NULL)
				{
                    pp = &((*pp)->sad);
                }
 
                max = *pp;
 
                //A partir de la je comprends pas!
                *pp = max->sag; 
 
                (*tete)->info = max->info;
 
                supprimer(pp, max->info);
            }
        }
    }
 
    return ok;
}

Donc en gros on commence par chercher l'élément et après on le supprime en fonction du nombre de fils qu'il a. Le problème c'est quand il en a deux, on est obligé de chercher le plus grand élément de son sous arbre gauche et de remplacer les deux éléments. Ce que je comprends pas c'est cette ligne : *pp = max->sag; En gros on met dans pp l'adresse de max->sag et après fait : supprimer(pp, max->info); Mais lors de la suppression, max->info se trouve 'au desus', donc il va jamais le trouver, donc jamais le supprimer ?

Merci de votre aide.

PS : Cet algo fonctionne, c'est juste que je comprends pas pourquoi !

25/01/2009, 13h28
krieg
Bonjour, en effet ton programme est astucieux,
pas tres complexe une fois bien compris mais faut le comprendre.
explication :
on s'intéresse que à la fin de ton code :
Code:

1 2 3 4 5 6 7 pp = &((*tete)->sag); while ((*pp)->sad != NULL) { pp = &((*pp)->sad); }
On a trouvé le noeud le plus petit du sous arbre gauche, il a la bonne propriété pour remplacer tete, sans changer les caractéristique de ton arbre (de recherche).

Maintenant on place ça valeur dans le noeud tete. Ainsi, on a supprimé
tete.
Code:

1 2 3 4 5 6 7 max = *pp; //A partir de la je comprends pas! *pp = max->sag; (*tete)->info = max->info;
Maintenant on supprime le noeud qui a remplacé tete.
[oupps] petite modification on a deja supprimé pp avec *pp = max->sag;
[oupps] je pense que la partie de code la ne sert à rien mais à vérifier.
[oupps] en effet un free(max) serai plus approprié ici.
Code:

1 2 supprimer(pp, max->info);
bye bonnes révisions
25/01/2009, 14h35
TrexXx

Je te remercie pour ton aide, en effet la dernière ligne supprimer ne sert à rien!