TD06 AVL
Télécharger le TD06 AVL en pdf
Page 1 : Pré-ING2Informatique 3Semestre 1 - 2022/2023TD 04 : Arbres AVLConsignes générales : N’oubliez pas pour ce TD comme pour les suivants de vous créer un répertoire consacré au TD etd’enregistrer vos codes dedans.On rappelle que les commandes à taper dans le terminal pour compiler puis éxécuter votre programme C :— Pour compiler : gcc -o nomexecutable nomprogramme.c— Pour exécuter : ./nomexecutableExercice 1 Question de cours 1. Construire un AVL en insérant les éléments dans cet ordre ; 10, 3, 5, 15, 20, 12, 7, 9.2. Construire un second AVL en insérant les éléments dans l’ordre inverse que précédement.3. Effectuer un parcours infixe sur ces deux arbres. Que remarque-t-on ?4. Supprimer l’élément 5 puis 12 du premier arbre. Redessiner l’arbre obtenu après chacune des suppressionsExercice 2 Construction d’un AVLLes versions "pseudo-code" des fonctions demandées sont dans le cours.1. On rappelle que pour construire un AVL, chaque noeud de l’arbre doit être associé à un facteur d’équilibrage dont lavaleur est :equilibre = hauteur sous arbre droit - hauteur sous arbre gaucheModifier la structure Arbre pour inclure ce nouveau champs.2. Réécrire la fonction creerArbrex : Element pour inclure également ce nouveau champ et l’initialiser à la créationd’un nouveau nœud de l’arbre.3. Les opérations de rééquilibrage s’effectuent à l’aide de « rotations » des sous-arbres cf cours. Écrire les fonctionsRotationGauche A : Arbre permettant de faire la rotation du sous-arbre A avec son fils droit et RotationDroiteA : Arbre permettant de faire la rotation du sous-arbre A avec son fils gauche.4. Tester ces deux fonctions sur les deux arbres suivants que vous aurez construit manuellement avec les fonctionsajouterFilsDroit et ajouterFilsGauche en prennant soin d’indiquer les bonnes valeurs d’élément ET d’équilibrepour chaque noeud :5. À partir des fonctions précédentes, écrire les fonctions permettant d’effectuer les doubles rotations : DoubleRotationDroiteA: Arbre et DoubleRotationGaucheA : Arbre.6. Tester une de ces fonctions celle la plus adaptée ! sur l’ arbre suivant que vous aurez construit manuellement avecles fonctions ajouterFilsDroit et ajouterFilsGaucheen prennant soin d’indiquer les bonnes valeurs d’élément ETd’équilibre pour chaque noeud :1
Page 2 : 7. Écrire la fonction equilibrerAVL A : Arbre qui permet d’effectuer la bonne rotation de l’arbre en fonction dufacteur d’équilibrage de A et de ses fils.8. Écrire la fonction insertionAVL A : arbre , e : Element, h: pointeur sur entier qui insère dans l’arbre unnouveau nœud contenant l’élément e. L’insertion de l’élément est basée sur le même principe que l’insertion dans unABR. Il faut cependant veiller à mettre à jour le facteur d’équilibrage de chaque nœud dont l’évolution est gérée parle paramètre h et à rééquilibrer l’arbre si besoin à l’aide de la fonction equilibrerAVL.9. Écrire la fonction suppAVLA: Arbre, e: Element, h: pointeur sur entier permettant de supprimer un nœudcontenant l’élément e de l’arbre A. Le raisonnement est le même que pour la question précédente.Exercice 3 Test d’un AVLReprendre les questions de l’exercice 1 et construire les AVL demandés grâce aux fonctions écrites dans le TD. A chaqueétape ajout ou suppression, afficher l’arbre avec la fonction affArbreGraphique qui a été fournie.2
