[GNU Pascal] Insertion dans un arbre AVL [Résolu]

[dorian100]

Bonjour,
Je suis étudiant en science informatique et dans le cadre d'un projet nous sommes amenés à créer des procédures de gestion capable d'insérer / supprimer des éléments contenus dans un arbre binaire de type AVL.

Je viens de taper mon code mais j'obtiens des erreurs de segmentation, je crois que le passage de pointeurs avec la récursivité ne fait pas bon ménage...

En fait, ce qui me pose problème ce n'est qu'une seule procédure : celle qui permet de calculer le nombre d'équilibre d'un élément. Il s'agit de déterminer la différence entre la hauteur de son fils droit et de sont fils gauche .

Je vous joint ici bas le code nécessaire à la compréhension du problème :

1. Procédure atomique utilisées dans la procédure principale :

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
	(* Ensemble des procedures / fonctions  atomiques *)
		FUNCTION is_empty (head : tree) : boolean;
			BEGIN
			IF head = NIL THEN
				is_empty := true
			ELSE
				is_empty := false;
			END;
 
		FUNCTION is_a_leaf (head : tree) : boolean;
			BEGIN
			IF (head^.r_s = NIL) AND (head^.l_s = NIL)  THEN
				is_a_leaf := true
			ELSE
				is_a_leaf := false;
			END;
 
		FUNCTION left_son (head : tree) : tree;
			BEGIN
				IF is_empty (head) THEN
					left_son := NIL
			        ELSE
				        left_son := head^.l_s;
			END;
 
		FUNCTION right_son (head : tree) : tree;
			BEGIN
				IF is_empty (head) THEN
					right_son := NIL
				ELSE
					right_son := head^.r_s;
			END;
 
	(* *)

2. Code de la procédure proprement dite :

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
 
	(* Nombre d'équilibre *)
		FUNCTION balanced_nbr (head : tree) : integer;
			VAR jumper : tree;
 
			(* Hauteur d'un arbre *)
				FUNCTION height (head : tree) : integer;
					VAR jumper : tree;
 
						FUNCTION max (a, b : integer) : integer;
							BEGIN
							IF a > b THEN
								max := a
							ELSE
								max := b;
							END;
					BEGIN
					new (jumper);
					jumper := head;
					IF is_a_leaf (jumper) OR is_empty (jumper) THEN
						height := 0
					ELSE
						height := 1 + max ( height (left_son (jumper)) , height (right_son (jumper)));
 
					END;			
			BEGIN
			new (jumper);
			jumper := head;
			balanced_nbr := height (right_son (jumper)) - height (left_son (jumper));
 
			END;
 
	(* *)

Le code posant problème se situe aux ligne 23 et 29 je pense. mais je ne vois pas comment résoudre cette impasse.

Vous remarquerez aussi qu'il s'agit d'un code structuré en langage impératif, il n'est pas encore question de POO.
Merci d'avance.

PS : Je suis preneur de commentaires et suggestions constructives : N'hésitez pas !

[dorian100]

Après quelques mois d’inactivité, je dépoussière le topique pour donner les sources fonctionnelles que j'ai pondu sur ce problème pour ceux qui en aurait besoin.

Si vous avez besoin du rapport explicatif qui va avec ce code, merci de me le faire savoir, je le mettrai alors en ligne.

Bonne journée,
Dorian.

[Roland Chastain]

Envoyé par dorian100

Si vous avez besoin du rapport explicatif qui va avec ce code, merci de me le faire savoir, je le mettrai alors en ligne.

Oui, c'est une bonne idée. Pour ma part je ne sais ni ce qu'est une "procédure atomique" ni un arbre "de type AVL".

[dorian100]

Pour définir simplement ce qu'est un arbre AVL, le plus simple est de consulter la page wikipedia à ce sujet :
ICI
ou encore ceci :
ICI
Et ensuite, pour bien comprendre le mode de fonctionnement du programme, voici la documentation qui va avec.
Je tiens à préciser qu'il s'agissait d'un de mes premiers projet de programmation, les choses ayant quelque peu changées depuis.

Voilà donc les liens vers la doc en pièce jointe.