Discussion :

[Neckara]

Bonjour,

Aujourd'hui en structure de données, nous avons vu une fonction de suppression de nœuds d'un arbre trié:

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
 
typedef maillon
{
   struct maillon *d; //sous-arbre à droite du nœud
   int x
   struct maillon *g; //sous-arbre à gauche du nœud
}Nœud, *Arbre;
 
Arbre sup (Arbre a, int x) //supprime le nœud ayant la valeur x de l'arbre a
{
	if(vide(a)) return a; //si a non-vide
	if(x == r(a)) //r(Arbre a) retourne la valeur contenu dans la racine (= a->x)
	{
		if(vide(ag(a)) return ad(a);//ag(arbre a) retourne le sous-arbre à gauche de la racine
		if(vide(ad(a)) return ag(a);//ad(arbre a) retourne le sous-arbre à droite de la racine
		return e(otermax(ag(a)), r(ed(ag(a))), ad(a));
		//ed(arbre a) retourne un pointeur sur le nœud contenant la valeur maximale (=extrémité droite)
	}
	if(x < r(a))
	{
		a->g = sup(a->g, x);
		return a;
	}
	a->d = sup(a->d, x);
	return a;
}

avec :

Code :

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

1
2
3
4
5
6
7
8
 
Arbre otermax(Arbre a)
{
	if(vide(a)) return a;
	if(vide(ad(a)) return ag(a);
	a->d = otermax(a->d);
	return a;
}

Passons sur le fait qu'il n'y ai pas de free....

Mais avec un arbre a:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
Droite
                           ________ 30
    _______ 60            /
   /            ______ 25-
51-            /          \________ 21
   \_______ 20-          
               \______ 10
 
Gauche

Je souhaite supprimer le nœud ayant la valeur 51.
donc sup(a, 51);
a, n'est pas vide et 51 == r(a)
De plus la partie gauche et droite de l'arbre ne sont pas vides.
Donc je dois faire :
return e(otermax(ag(a), r(ed(ag(a)), ad(a));


ag(a) va donc retourner un arbre ie un pointeur sur le maillon contenant la valeur 20
donc j'ai : e(otermax(b), r(ed(b)), ad(a));

avec arbre b :

Code :

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

1
2
3
4
5
6
7
 
               ________ 30
              /
    ______ 25-
   /          \________ 21
20-          
   \______ 10

Or la fonction otermax va modifier le pointeur "d" (sous-arbre de droite) du Nœud contenant la valeur 25 et on va se retrouver avec :

Code :

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

1
2
3
4
5
6
 
 
    ______ 25-
   /          \________ 21
20-          
   \______ 10

Donc ed(b) va retourner un pointeur vers le maillon 25 et non vers le maillon 30!

Mais le prof persiste à dire que ed(b) retournera tout de même un pointeur vers le maillon 30.
Si j'ai bien compris ce qu'il a dit, avant de lancer la fonction e, les paramètres vont être enregistré sous forme de copie (->pile d'appel des fonctions)
Mais si ed(b) retourne bel et bien un pointeur vers le maillon contenant la valeur 30,
cela voudrait dire que ed a été exécuté avant otermax???

Pourriez-vous me donner votre avis et si possible me dire comment les fonctions sont exécutées dans e(otermax(ag(a), r(ed(ag(a)), ad(a)); ?

[souviron34]

Pourriez-vous me donner votre avis et si possible me dire comment les fonctions sont exécutées dans e(otermax(ag(a), r(ed(ag(a)), ad(a)); ?

je n'ai pas tout suivi et n'en ai pas le temmps pour l'instant, mais sur ce point c'est assez clair :

on commence par évaluer les arguments

donc ag(a), ad(a), et [ ag(a), puis ed(ag(a), puis r(ed(ag(a)))]

Ensuite on évalue otermax(arg1, arg2,arg3)

Enfin on évalue e(otermax..)

[diogene]

Si j'ai bien compris ce qu'il a dit, avant de lancer la fonction e, les paramètres vont être enregistré sous forme de copie (->pile d'appel des fonctions)

Oui, cela implique que les expressions passées en argument soient évaluées y compris dans leurs effets de bord.

cela voudrait dire que ed a été exécuté avant otermax???

Une règle générale est que l'ordre d'évaluation des arguments d'une fonction n'est pas spécifié. Si le résultat peut dépendre de l'ordre d'évaluation des arguments, alors l'expression est mal formée et le résultat est indéfini. Ceci peut arriver si l'évaluation des arguments entraine des effets de bords (ce qui est le cas ici)

[Neckara]

Merci pour vos réponses, je viens de comprendre.

Je marque donc ce sujet comme étant résolu et je me coucherais moins bête ce soir^^