TP6 - Arbres AVL

Durée : 1h30

Inès de Courchelle, Elisabeth Ranisavljevic

Objectifs :

  • Rééquilibrer des arbres
  • Améliorer la complexité de recherche d’un arbre binaire
  • Manipuler un arbre AVL

Attention :

À chaque étape de programmation, vous devez vérifier si le programme :

  • Compile sans warning
  • Obtient les résultats attendus
  • Avant de coder, il faut écrire un algo avec un papier et un stylo !

    logo

Exercice 1 : La préparation

  1. Créer les fichiers suivants :
  • AVL.h
  • AVL.c
  • main.c
  1. Créer le squelette du programme

AVL.h

#ifndef AVL_H
#define AVL_H

/* Le prototype/signature de toutes mes fonctions/procédures */

#endif

AVL.c

#include "AVL.h"
/* corps des différentes fonctions/procédures */

main.c

#include <stdio.h>
#include "AVL.h"

int main(){
    printf("C'est l'arbre !");
    return 0;

}

Exercice 2 : Let’s go

  1. Spécifier la structure d’un arbre AVL dans fichier .h

  2. Coder les fonctions suivantes :


/* Auteur : xxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne l'écart de hauteur entre un filsG et un FilsD *
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : un entier  */
int ecart(avl a);



/* Auteur : xxxxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne la hauteur d'un arbre passé en paramètre  */
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : un entier  */
int recupererHauteur(avl a);


/* Auteur : xxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne un arbre après une rotation à gauche  */
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : l'arbre AVL  */
avl rotationGauche(avl a);


/* Auteur : xxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne un arbre après une rotation à droite  */
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : l'arbre AVL  */
avl rotationDroite(avl a);

/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne un arbre après une rotation à gauche  et à droite (double)*/
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : l'arbre AVL  */
avl rotationGaucheDroite(avl a);

/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne un arbre après une rotation à droite et à gauche (double)*/
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : l'arbre AVL  */
avl rotationDroiteGauche(avl a);



/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne un arbre ré-équilibré*/
/* Entrée(s) : l'arbre AVL */
/* Sortie(s) : l'arbre AVL */
avl equilibrer(avl a);

/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : affiche un avl*/
/* Entrée(s) : l'arbre AVL et la hauteur (attention au premier appel elle est à ZERO */
/* Sortie(s) : - */
void afficher_(avl a, int h);



/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : insére un entier dans un AVL*/
/* Entrée(s) : un entier et l'avl*/
/* Sortie(s) : l'avl */
avl inserer (int n, avl a);


/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : retourne le noeud maximal dans un AVL*/
/* Entrée(s) : l'avl*/
/* Sortie(s) : un entier */
int maxValue(avl a);



/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : supprime le noeud maximal dans un AVL*/
/* Entrée(s) : l'avl*/
/* Sortie(s) : l'avl */
avl supprMax(avl a);

/* Auteur : xxxxxxxxx */
/* Date :  xxxxxx */
/* Résumé : supprime une valeur dans un AVL*/
/* Entrée(s) : l'avl et la valeur à supprimer*/
/* Sortie(s) : l'avl */
avl supprimer(int n,avl a);