Discussion: Insertion dans un arbre AVL [GNU Pascal]

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

    Informations forums :
    Inscription : octobre 2011
    Messages : 10
    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 : 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
    	(* 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 : 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
     
    	(* 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
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : octobre 2011
    Messages : 10
    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
    Inscrit en
    décembre 2011
    Messages
    1 986
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Moselle (Lorraine)

    Informations forums :
    Inscription : décembre 2011
    Messages : 1 986
    Points : 5 712
    Points
    5 712
    Billets dans le blog
    1

    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
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : octobre 2011
    Messages : 10
    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.
    Images attachées Images attachées

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

Discussions similaires

  1. Insertion dans un arbre b
    Par miloko dans le forum Oracle
    Réponses: 1
    Dernier message: 12/12/2013, 11h11
  2. Insertion dans un arbre (algo tri de l'arbre)
    Par Self-Mao dans le forum Lisp
    Réponses: 9
    Dernier message: 30/07/2013, 13h55
  3. Insertion dans un arbre binaire Rouge-Noir (Red-Black Tree)
    Par monsieurouxx dans le forum Général Algorithmique
    Réponses: 14
    Dernier message: 25/06/2010, 18h29
  4. Insertion dans un arbre binaire
    Par mikedavem dans le forum C
    Réponses: 3
    Dernier message: 08/06/2006, 07h50
  5. Insertion d'une occurence dans un arbre
    Par Gryzzly dans le forum Général Algorithmique
    Réponses: 13
    Dernier message: 19/12/2005, 15h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo