Algorithmique Avancée (ALG)
• 8 CM (1h30/séance), 2 séances TD (2h/séance), + 3 séances TP (3h/séance)
– Enseignant :
• Eric GASCARD [Link]@[Link]
• Évaluation (3h) :
– 2 DS écrit (45 min) (40%)
– Examen final écrit (1h30) (60%)
• Contenu de la matière :
– Approfondissement des algorithmes sur les arbres : arbres équilibrés
– Introduction à l’algorithmique sur les graphes
– Implémentation des algorithmes en Java
Eric Gascard Polytech Grenoble ALG - 1
CM 1 : Manipulations des Arbres Binaires de Recherche
Plan :
• Rappels sur les arbres binaires
• Implémentation en Java des arbres binaires
• Rappel sur les arbres binaires de recherche
• Tester si un arbre binaire est un arbre binaire de recherche
• Insérer un élément à la racine d’un arbre binaire de recherche
Eric Gascard Polytech Grenoble ALG - 2
Rappel sur les arbres binaires
• Arbre binaire étiqueté (définition inductive) :
− l’arbre vide (null pour nous) est un arbre binaire
− Si filsG et filsD sont des arbres binaires et cle une étiquette Alors
<filsG,cle,filsD> est un arbre binaire étiqueté
cle : Arbre Element
setCle(Element, Arbre) void
Type Abstrait de Donnée Arbre(Element)
Utilise Element filsGauche : Arbre Arbre
setFilsG(Arbre, Arbre) void
Opérateurs de base :
estVide : Arbre boolean filsDroit : Arbre Arbre
setFilsD(Arbre, Arbre) void
Eric Gascard Polytech Grenoble ALG - 3
Modélisation des arbres binaires en Java (1/2)
public class Arbre<Element extends Comparable<Element>> {
// attributs
private Element cle;
private Arbre<Element> filsG;
private Arbre<Element> filsD;
// Constucteurs
public Arbre() {
cle = filsG = filsD = null;}
public Arbre(Element cle) {
[Link] = cle;
filsG = filsD = null;
public Arbre(Arbre<Element> g, Element v, Arbre<Element> d) {
filsG = g;
cle = v;
filsD = d;}
Eric Gascard Polytech Grenoble ALG - 4
Modélisation des arbres binaires en Java (2/2)
public class Arbre<Element extends Comparable<Element>> {
…
// Tester arbre vide
public static<E extends Comparable<E>> boolean estVide(Arbre<E> a) {
return a == null;
}
// Accesseurs, Modificateurs
public static<E extends Comparable<E>> E cle(Arbre<E> a) {
if (estVide(a)) {
return null;
}
return [Link];
}
public static<E extends Comparable<E>> void setCle(E cle, Arbre<E> a) {
if (!estVide(a)) {
[Link] = cle;
}
}
Eric Gascard Polytech Grenoble ALG - 5
Modélisation des arbres binaires en Java (3/2)
public class Arbre<Element extends Comparable<Element>> {
…
// Accesseurs, Modificateurs
public static<E extends Comparable<E>> Arbre<E> filsGauche(Arbre<E> a) {
if (estVide(a)) {return null;}
return [Link];
}
public static<E extends Comparable<E>> void setFilsG(Arbre<E> fG, Arbre<E> a){
if (!estVide(a)) {
[Link] = fG;
}
}
public static<E extends Comparable<E>> Arbre<E> filsDroit(Arbre<E> a){
if (estVide(a)) {return null;}
return [Link];
}
public static<E extends Comparable<E>> void setFilsD(Arbre<E> fD, Arbre<E> a){
if (!estVide(a)) {
[Link] = fD;
}
}
Eric Gascard Polytech Grenoble ALG - 6
Arbre Binaire de Recherche (ABR)
• Arbre binaire de recherche ABR (définition inductive) :
– l’arbre vide est un ABR
– <filsG, cle, filsD> est un ABR ssi :
• la clé de la racine est >= à tous les éléments de filsG
• la clé de la racine est < à tous les éléments de filsD
• filsG et filsD sont des ABR
• Un arbre qui est un ABR :
Eric Gascard Polytech Grenoble ALG - 7
Opérations sur les arbres binaires de recherche
Vus en cours d’API :
- rechercherABR : Element × Arbre boolean
- insertionFeuilleABR : Element × Arbre Arbre
- minABR : Arbre Element
- maxABR : Arbre Element
- supprimerABR : Element × Arbre Arbre
- supprimerMinABR : Arbre Arbre
- supprimerMaxABR : Arbre Arbre
- supprimerRacineABR : Arbre Arbre
Non étudié en cours d’API :
- estABR : Arbre boolean
- insertionRacineABR : Element × Arbre void
- coupureABR : Element × Arbre × Arbre × Arbre void
Eric Gascard Polytech Grenoble ALG - 8
Tester si un arbre binaire est un ABR (1/4)
Opération estABR : Arbre boolean
• Pour vérifier si un arbre binaire a est un ABR, on peut raisonner par
récursivité :
public static<E extends Comparable<E>> boolean estABR(Arbre<E> a) {
if (estVide(a)) {
return true;
}
if (!estVide(filsGauche(a)) &&
cle(a).compareTo(maxABR(filsGauche(a))) < 0) {
return false;
}
if (!estVide(filsDroit(a)) &&
cle(a).compareTo(minABR(filsDroit(a))) > 0) {
return false;
}
return estABR(filsGauche(a)) && estABR(filsDroit(a));
}
Eric Gascard Polytech Grenoble ALG - 9
Tester si un arbre binaire est un ABR (2/4)
• Analyse de la complexité de cette fonction estABR dans le pire cas :
– Soit n le nombre de nœud de l’arbre
– Soit T(n) la complexité en comparaison
– Dans le pire cas, la complexité de trouver le min ou le max dans un ABR
est O(n) (arbre filiforme)
– Définition inductive de T(n) :
• T(0)=T(1)=1
• T(n)=T(n-1)+O(n)
– T(n) peut s’exprimer par T(n)=O(n) + O(n-1) + … O(1) = O(n^2)
Eric Gascard Polytech Grenoble ALG - 10
Tester si un arbre binaire est un ABR (3/4)
• On peut tester de manière plus efficace si un arbre est un ABR :
– Solution 1 : Par un parcours en profondeur infixe en vérifiant que les
valeurs rencontrées sont dans l’ordre croissant : utilisation d’une liste pour
la mémorisation les éléments par ordre de visite
• a) initialisation d’une liste vide.
• b) lors du parcours en profondeur infixe, on ajoute en fin de liste les
valeurs rencontrées O(n).
• c) A la fin du parcours en profondeur infixe, on vérifie que la liste est
triée O(n).
– Solution 2 : En calculant les maximum et minimum en même temps que la
vérification afin de ne visiter un nœud qu’une seule fois complexité en
O(n)
Eric Gascard Polytech Grenoble ALG - 11
Tester si un arbre binaire est un ABR (4/4)
public static<E extends Comparable<E>>
boolean estABR(Arbre<E> a, Arbre<E> min, Arbre<E> max) {
if (estVide(a)) {
return true;
}
setCle(cle(a), min);
setCle(cle(a), max);
Arbre<E> seuil = new Arbre();
if (!estVide(filsGauche(a))) {
if (!estABR(filsGauche(a), min, seuil) ||
(cle(seuil).compareTo(cle(a)) > 0) )
return false;
}
if (!estVide(filsDroit(a))) {
if (!estABR(filsDroit(a), seuil, max) ||
(cle(a).compareTo(cle(seuil)) >= 0) )
return false;
}
return true;
}
Eric Gascard Polytech Grenoble ALG - 12
Insertion à la racine dans un ABR (1/9)
• On veut insérer une nouvelle clé dans un ABR en le plaçant à la racine la
structure d’ordre doit être conservée !
• Pour cela on va couper l’arbre en deux parties regroupant les nœuds inférieurs
à la nouvelle clé (fg_new) et ceux qui sont supérieurs (fd_new).
• 1ère étape : produire les deux arbres séparés par la clé de l’élément que l’on
veut ajouter le découpage et la reconstitution se font en même temps,
récursivement.
• Cas où la clé de la valeur est strictement inférieure à celle de la racine :
– On découpe le fils gauche avec la clé de la valeur à ajouter.
– On obtient deux arbres : fg_inf, l’arbre formé des nœuds du fils gauche de clé
inférieure à la coupure et, symétriquement, fg_sup.
– L’arbre des nœuds inférieurs à la coupure fg_new est alors fg_inf et l’arbre des
nœuds supérieurs à la coupure fd_new est formé en remplaçant le fils gauche initial
par fg_sup
• On fait les opérations symétriques si la clé de la valeur est supérieure ou égale
à la racine.
• 2ème étape : Création de l’ABR <fg_new, clé, fd_new>
Eric Gascard Polytech Grenoble ALG - 13
Insertion à la racine dans un ABR (2/9)
fg_inf fg_sup
Séparation de l’arbre par la clé 17 Reconstitution du fils gauche
fg_new fd_new
Reconstruction des deux arbres Ajout de 17 à la racine
Eric Gascard Polytech Grenoble ALG - 14
Insertion à la racine dans un ABR (3/9)
Fonction coupure(x,a,G,D) : Element×Arbre×Arbre×Arbre void
if (estVide(a)) {
G = null
D = null }
else {
if (x < cle(a)) {
D = a
coupure(x,filsGauche(a), G, filsGauche(D))}
else {
G = a
coupure(x,filsDroit(a), filsDroit(G), D)} }
Fonction insertionRacineABR(x,a) : Element×Arbre Arbre
coupure(x,a,G,D)
nouv = Arbre(G,x,D)
return nouv
Eric Gascard Polytech Grenoble ALG - 15
Insertion à la racine dans un ABR (4/9)
Ajout de 11 à l’arbre suivant :
15
8 30
5 12 21 35
6 10 25
Eric Gascard Polytech Grenoble ALG - 16
Insertion à la racine dans un ABR (5/9)
11
15
G D
8 30
5 12 21 35
6 10 25
11
G 15
D 30
21 35
25
Eric Gascard Polytech Grenoble ALG - 17
Insertion à la racine dans un ABR (6/9)
8
11
5 12
G 15
D 30
6 10
21 35
25
11
8 15
D 30
5 G
21 35
6
25
Eric Gascard Polytech Grenoble ALG - 18
Insertion à la racine dans un ABR (7/9)
11
12
8 15
10 D 30
5 G
21 35
6
25
11
8 15
12 30
5 G
21 35
6 D
25
Eric Gascard Polytech Grenoble ALG - 19
Insertion à la racine dans un ABR (8/9)
11
8 15
10
12 30
5 G
21 35
6 D
25
11
8 15
12 30
5 10
21 35
6
25
Eric Gascard Polytech Grenoble ALG - 20
Insertion à la racine dans un ABR (9/9)
??? Implémentation de coupure et insertionRacineABR en Java ???
• En Java, les valeurs des paramètres d’une fonction sont :
– soit des valeurs de types primitifs (boolean, char, int, float …)
– Soit des valeurs de type référence, càd des adresses d’instances d’objets
• Lors d’un passage de paramètres de fonction, on manipule que des copies :
– de la valeur du paramètre de type primitif
– de l’adresse de l’instance d’objet passé en paramètre
• Conséquences :
– On ne peut pas modifier la valeur du paramètre effectif de type primitif
Il faut passer en paramètre un objet contenant la valeur primitive à modifier, cf estABR
avec min et max
– On ne peut pas modifier la référence du paramètre effectif de type référence
Il faut retourner un objet par la fonction, est l’utiliser ainsi : a = fct(a)
On doit prendre les prototypes suivantes pour coupure et insertionRacineABR :
public static<E extends Comparable<E>>
Arbre<E> coupure(E e, Arbre<E> a);
L’arbre retourné possèdera G et D dans ses fils gauche et droit
public static<E extends Comparable<E>>
Arbre<E> insertionRacineABR(E e, Arbre<E> a)
Eric Gascard Polytech Grenoble ALG - 21
Le besoin d’équilibrer les ABR
• Rappel : hauteur = long. max d’un chemin de la racine à une feuille.
• Une « mauvaise » succession d’insertions et de suppressions peut
« déséquilibrer » l’arbre et rendre les recherches moins efficaces
• Arbre binaire équilibré
– intuitivement : branches de taille voisine
– définition : pour tout noeud n de l’arbre :
| hauteur(filsGauche(n)) - hauteur(filsDroit(n)) | <= 1
• Les opérations de recherche, insertion, suppression sont en O(h(n)) où h(n)
est la hauteur de l’arbre avec n noeuds.
𝑙𝑙𝑙𝑙𝑙𝑙2 (𝑛𝑛) ≤ ℎ 𝑛𝑛 ≤ 𝑛𝑛 − 1
• Si n éléments ont été insérés dans l’arbre :
– Au pire, ℎ = 𝑛𝑛 − 1 = 𝑂𝑂(𝑛𝑛)
– Au mieux, ℎ = 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑛𝑛 + 1 − 1 = 𝑙𝑙𝑙𝑙𝑙𝑙2 (𝑛𝑛) = 𝑂𝑂(log 𝑛𝑛 )
– En moyenne, est 𝑂𝑂(log 𝑛𝑛 )
Eric Gascard Polytech Grenoble ALG - 22
À propos des sources utilisés dans ce document ©
• Programmation et Algorithmique : Ecole Polytechnique (X)
– Jean-Eric Pin, Gilles Dowek,Philippe Baptiste, Luc Maranget, Olivier
Bournez, …
• POO : Alain Giorgetti (Université de Franche-Comté)
• Intro à la Prog avec Java : Frédéric MALLET (Université Nice)
• Algorithmique Avancée : Imad HAFIDI (ENSA-Khouribga)
• Introduction à l’Algo : Lélia Blin (Université D’Evry)
• Structures de données : Alexandre Guitton (ISIMA Clermont
Auvergne INP)
• Algorithmique et structures des données : CNAM
• Guillaume Hutzler (Université Evry-Val d’Essonne)
• Jérôme GENSEL, Jean-Michel Adam (Université Grenoble Alpes)
• Nicolas Loménie (Université Paris Cité)
• A. DJEBAL (ESIEE Paris)
Eric Gascard Polytech Grenoble ALG - 23
