Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 4 sur 4
  1. #1
    Invité régulier
    Homme Profil pro
    Inscrit en
    octobre 2011
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : octobre 2011
    Messages : 9
    Points : 7
    Points
    7

    Par défaut Insertion dans un arbre AVL

    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 !

  2. #2
    Invité régulier
    Homme Profil pro
    Inscrit en
    octobre 2011
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : octobre 2011
    Messages : 9
    Points : 7
    Points
    7

    Par défaut

    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.
    Fichiers attachés Fichiers attachés

  3. #3
    Rédacteur/Modérateur
    Avatar de Roland Chastain
    Homme Profil pro Roland Chastain
    Inscrit en
    décembre 2011
    Messages
    1 414
    Détails du profil
    Informations personnelles :
    Nom : Homme Roland Chastain
    Âge : 41
    Localisation : France, Moselle (Lorraine)

    Informations forums :
    Inscription : décembre 2011
    Messages : 1 414
    Points : 3 907
    Points
    3 907

    Par défaut

    Citation Envoyé par dorian100 Voir le message
    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".
    L'Art est long et le Temps est court.

  4. #4
    Invité régulier
    Homme Profil pro
    Inscrit en
    octobre 2011
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : octobre 2011
    Messages : 9
    Points : 7
    Points
    7

    Par défaut

    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.
    Fichiers attachés Fichiers attachés

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •