INFO3 – TD Algorithmique avancée
Travaux Pratiques :
Implémentation d’arbres binaires, ABR et AVL en Java
Partie I : Arbre binaire
Compléter la classe Arbre avec les méthodes suivantes :
Méthodes récursives
Question I.1 :
Calcul de la hauteur d’un arbre (en récursif).
public static <E extends Comparable<E>> int calculeHauteurRec(Arbre<E> a) ;
Question I.2 :
Calcul du nombre de clés stockées dans un arbre (en récursif).
public static <E extends Comparable<E>> int tailleRec(Arbre<E> a) ;
Question I.3 :
On appelle arbre binaire plein un arbre binaire tel que chaque sommet interne a
exactement 2 fils.
Tester si un arbre binaire est plein (en récursif).
public static <E extends Comparable<E>> boolean estPleinRec(Arbre<E> a) ;
Méthodes itératives
Question I.4 :
Affichage de l’arbre par un parcours en largeur en utilisant une file.
public static <E extends Comparable<E>> void affichageLargeur(Arbre<E> a) ;
Question I.5 :
Calcul de la hauteur d’un arbre par un parcours en largeur en utilisant une file.
public static <E extends Comparable<E>> int calculeHauteurIter(Arbre<E> a) ;
Page 1 sur 6
INFO3 – TD Algorithmique avancée
Question I.6 :
Calcul du nombre de clés stockées dans un arbre par un parcours en profondeur en
utilisant une pile.
public static <E extends Comparable<E>> int tailleIter(Arbre<E> a) ;
Question I.7 :
Affichage des clés stockées dans l’arbre par un parcours infixe en utilisant une pile
(cf algorithme de parcours en profondeur à main gauche vu au TD1).
public static <E extends Comparable<E>> void affichageInfixeIter(Arbre<E> a) ;
Question I.8 :
On appelle arbre binaire parfait un arbre binaire un arbre binaire complet dans
lequel toutes les feuilles sont à la même hauteur dans l’arbre.
Tester si un arbre binaire est parfait par un parcours en largeur en utilisant une file.
Lors du parcours, il faut stocker le niveau de l’arbre que l’on est en train de
traverser et si l’on rencontre pour la première fois une feuille, on mémorise le
niveau où l’on l’a rencontrée. Pour toutes les autres feuilles rencontrées pendant le
parcours en largeur, on vérifierasi son niveau est le même que celui de la première
feuille rencontrée.
public static <E extends Comparable<E>> boolean estParfait(Arbre<E> a) ;
Page 2 sur 6
INFO3 – TD Algorithmique avancée
Partie II : Arbre ABR
On suppose que vous manipulez un arbre binaire qui est un ABR. Compléter la
classe Arbre avec les méthodes suivantes :
Méthodes récursives
Question II.1 :
Rechercher dans un ABR si une clé est présente (en récursif).
public static <E extends Comparable<E>>
boolean estPresentABRRec(E cle, Arbre<E> a);
Question II.2 :
Insérer une clé dans un ABR aux feuilles tout en conservant la propriété ABR (en
récursif).
public static <E extends Comparable<E>>
Arbre<E> insertionFeuilleABR(E e, Arbre<E> a) ;
Question II.3 :
Insérer dans un ABR à la racine une clé tout en conservant sa propriété d’ABR (voir
Cours 1).
public static <E extends Comparable<E>>
Arbre<E> coupure(E e, Arbre<E> a) ;
public static <E extends Comparable<E>>
Arbre<E> insertionRacineABR(E e, Arbre<E> a) ;
Question II.4 :
Tester si un arbre binaire est un ABR avec mémorisation dans ses paramètres de sa
clé minimale et de sa clé maximale (voir Cours 1).
public static <E extends Comparable<E>>
boolean estABR(Arbre<E> a, Arbre<E> min, Arbre<E> max) ;
Page 3 sur 6
INFO3 – TD Algorithmique avancée
Question II.5 :
Supprimer une clé dans un ABR tout en conservant sa propriété d’ABR (vu au
Cours 2 avec les AVL, pour les ABR le rééquilibrage n’est pas à faire).
public static <E extends Comparable<E>>
Arbre<E> sortirMaxABR(Arbre<E> a, Arbre<E> max) ;
public static <E extends Comparable<E>>
Arbre<E> supprimerRacineABR(Arbre<E> a) ;
public static <E extends Comparable<E>>
Arbre<E> supprimerABR(E e, Arbre<E> a) ;
Méthodes itératives
Question II.6 :
Rechercher dans un ABR une clé immédiatement inférieure à une clé donnée.
public static <E extends Comparable<E>>
E rechercher_cle_inf_ABR(E cle, Arbre<E> a) ;
Question II.7 :
Tester si un arbre binaire est un ABR par un parcours itératif en profondeur main
gauche avec mise à jour de des attributs min, max, abr et sens (TD1 Exercice 1).
public static <E extends Comparable<E>> boolean estABRIter(Arbre<E> a) ;
Page 4 sur 6
INFO3 – TD Algorithmique avancée
Partie III : Arbre AVL
Compléter la classe ArbreAVL avec les méthodes suivantes :
Question III.1 :
Rotation gauche d’un arbre AVL.
public static <E extends Comparable<E>>
ArbreAVL<E> rotGauche(ArbreAVL<E> p) ;
Question III.2 :
Rotation droite d’un arbre AVL.
public static <E extends Comparable<E>>
ArbreAVL<E> rotDroite(ArbreAVL<E> q) ;
Question III.3 :
Rotation gauche-droite d’un arbre AVL.
public static <E extends Comparable<E>>
ArbreAVL<E> rotGaucheDroite(ArbreAVL<E> r) ;
Question III.4 :
Rotation droite-gauche d’un arbre AVL.
public static <E extends Comparable<E>>
ArbreAVL<E> rotDroiteGauche(ArbreAVL<E> r) ;
Question III.5 :
Rééquilibrage d’un arbre AVL.
public static <E extends Comparable<E>>
ArbreAVL<E> equilibrerAVL(ArbreAVL<E> a) ;
Question III.6 :
Insertion aux feuilles dans un AVL en récursif.
public static <E extends Comparable<E>>
ArbreAVL<E> insertionFeuilleAVLRec(E e, ArbreAVL<E> a) ;
Page 5 sur 6
INFO3 – TD Algorithmique avancée
Question III.7 :
Affichage de l’arbre par un parcours infixe en récursif. L’affichage de l’arbre sera
parenthésé et la balance de chaque nœud sera affiché à coté de la valeur de sa clé.
public static <E extends Comparable<E>>
void affichageInfixeRec(ArbreAVL<E> a) ;
Question III.8 :
Supprimer une clé dans un ABR tout en conservant sa propriété d’ABR.
public static <E extends Comparable<E>> E dernierDescendant(ArbreAVL<E> a) ;
public static <E extends Comparable<E>>
ArbreAVL<E> supprimerRacineAVL(ArbreAVL<E> a);
public static <E extends Comparable<E>>
ArbreAVL<E> supprimerAVL(E e, ArbreAVL<E> a);
Question III.9 :
Insertion aux feuilles dans un AVL en itératif (TD1 Exercice 2).
public static <E extends Comparable<E>>
ArbreAVL<E> insertionFeuilleAVLIter(E e, ArbreAVL<E> a) ;
Page 6 sur 6