Algorithmique avancée &

Programmation
[1ère année Master SID, Semestre 1]
Faculté des sciences de Rabat

Par
Prof. B. AHIOD
(ahiod@[Link])
2021-2022
 Objectifs
• Consolider les fondements de l’algorithmique
de base au niveau :
– des structures de données
– des paradigmes de conception d’algorithmes
• Utiliser le langage de programmation C pour
implémenter :
– les structures de données
– les algorithmes qui les manipulent

Master SID – Algorithmique avancée &

2
Programmation 2021-2022
 Prérequis
• Notions de base d’algorithmique et de structures de
données :
– Conception d’algorithmes itératifs et récursifs
– Analyse de complexité d’algorithmes
– Structures de données élémentaires
– …
• Programmation en langage C :
– Programmation structurée et modulaire (compilation
séparée)
– Notions de tableaux, d’enregistrements, …
– Manipulation des pointeurs et allocation dynamique
–…

Master SID – Algorithmique avancée &

3
Programmation 2021-2022
 Contenu
• Structures de données élémentaires (Rappels) :
– Listes
– Arbres binaires
• Structures de données avancées :
– Arbres équilibrés (AVL, Rouge/Noir, B-Arbres)
– Tables de hachage
– Tas et files de priorités
– Graphes
• Paradigmes de conception d’algorithmes :
– Algorithmes « diviser pour régner »
– Algorithmes gloutons
– Programmation dynamique
– Algorithmes de recherche exhaustive (retour arrière et/ou séparation &
évaluation)

Master SID – Algorithmique avancée &

4
Programmation 2021-2022
Structures de données
élémentaires
Rappels
 Notion de programme
Algorithmes + structures de données
=
Programme
[Wirth]

• Un programme informatique est constitué

d’algorithmes et de structures de données
manipulées par des algorithmes

Master SID – Algorithmique avancée &

6
Programmation 2021-2022
De l’Analyse à l’Exécution

Master SID – Algorithmique avancée &

7
Programmation 2021-2022
 Notion d’Algorithme
• Origine :
– Le terme algorithme vient du nom du mathématicien Al-
Khawarizmi (820 après J.C.)

• Définition :
– Un algorithme est une suite finie de règles à appliquer dans un
ordre déterminé à un nombre fini de données pour arriver, en
un nombre fini d'étapes, à un certain résultat, et cela
indépendamment des données

• Rôle fondamental :
– Sans algorithme il n'y aurait pas de programme

• Un algorithme est indépendant :

– de l'ordinateur qui l'exécute
– du langage dans lequel il est énoncé et traduit

Master SID – Algorithmique avancée &

8
Programmation 2021-2022
 Spécifier/Exprimer/Implémenter
un algorithme
• Spécification d ’un algorithme :
– ce que fait l’algorithme
– cahier des charges du problème à résoudre

• Expression d ’un algorithme :

– comment il le fait
– texte dans un pseudo langage

• Implémentation d ’un algorithme :

– traduction du texte précédent
– dans un langage de programmation

Master SID – Algorithmique avancée &

9
Programmation 2021-2022
 Programmation Procédurale vs
Programmation Orientée-Objet
• Programmation Procédurale :
– Centrée sur les procédures (ou opérations)
– Décomposition des fonctionnalités d'un programme en
procédures qui vont s'exécuter séquentiellement
– Les données à traiter sont passées en arguments aux
procédures
– Des langages procéduraux : C, Pascal, …
• Programmation Orientée-Objet :
– Centrée sur les données
– Tout tourne autour des "objets" qui sont des petits
ensembles de données représentants leurs propriétés
– Des langages orientés-objets : C++, Java, …

Master SID – Algorithmique avancée &

10
Programmation 2021-2022
Phases de programmation en C

Master SID – Algorithmique avancée &

11
Programmation 2021-2022
 Notion de Type Abstrait de Données
• Un type abstrait de données (TAD) :
– est un ensemble de valeurs muni d’opérations
sur ces valeurs
– sans faire référence à une implémentation
particulière
• Un TAD est caractérisé par :
– sa signature : définit la syntaxe du type et des
opérations
– sa sémantique : définit les propriétés des
opérations
Master SID – Algorithmique avancée &
12
Programmation 2021-2022
 Notion de Structure de Données
• On dit aussi :
– structure de données concrète

• Correspond à :
– l’implémentation d’un TAD

• Composée :
– d’un algorithme pour chaque opération
– des données spécifiques à la structure pour sa gestion

• Remarque :
– Un même TAD peut donner lieu à plusieurs structures de
données, avec des performances différentes

Master SID – Algorithmique avancée &

13
Programmation 2021-2022
 Implémentation d’un TAD
• Pour implémenter un TAD :
– Déclarer la structure de données retenue pour représenter le TAD :
L’interface
– Définir les opérations primitives dans un langage particulier : La
réalisation
• Exigences :
– Conforme à la spécification du TAD ;
– Efficace en terme de complexité d’algorithme.
• Pour implémenter, on utilise :
– Les types élémentaires (entiers, caractères, ...)
– Les pointeurs ;
– Les tableaux et les enregistrements ;
– Les types prédéfinis.
• Plusieurs implémentations possibles pour un même TAD

Master SID – Algorithmique avancée &

14
Programmation 2021-2022
 Implémentation d’un TAD en C
• Utiliser la programmation modulaire :
– Programme découpé en plusieurs fichiers, même de petites tailles (réutilisabilité,
lisibilité, etc.)
– Chaque composante logique (un module) regroupe les fonctions et types autour
d'un même thème.

• Pour chaque module truc, créer deux fichiers :

– fichier truc.h : l'interface (la partie publique) ; contient la spécification de la
structure ;
– fichier truc.c : la définition (la partie privée) ; contient la réalisation des opérations
fournies par la structure. Il contient au début l'inclusion du fichier truc.h

• Tout module ou programme principal qui a besoin d'utiliser les fonctions

du module truc, devra juste inclure le truc.h
• Un module C implémente un TAD :
– L'encapsulation : détails d'implémentation cachés ; l'interface est la partie visible à
un utilisateur
– La réutilisation : placer les deux fichiers du module dans le répertoire où l'on
développe l'application.

Master SID – Algorithmique avancée &

15
Programmation 2021-2022
 Structures de données linéaires
• Structure linéaire :
– C’est un arrangement linéaire d'éléments liés par
la relation successeur
• Exemples :
– Tableaux (la relation successeur est implicite)
– Piles
– Files
– listes

Master SID – Algorithmique avancée &

16
Programmation 2021-2022
 Notion de Pile (Stack)
• Une pile est :
– une structure linéaire permettant de stocker et de restaurer des données
selon un ordre LIFO (Last In, First Out ou « dernier entré, premier sorti »)

• Dans une pile :

– Les insertions (empilements) et les suppressions (dépilements) sont
restreintes à une extrémité appelée sommet de la pile.

• Applications :
– Vérification du bon équilibrage d’une expression avec parenthèses
– Evaluation des expressions arithmétiques postfixées
– Gestion par le compilateur des appels de fonctions
– Parcours « en profondeur » d'arbres (voir arbres)
– …

Master SID – Algorithmique avancée &

17
Programmation 2021-2022
 Type Abstrait Pile
Type Pile
Utilise Elément, Booléen
Opérations
pile_vide : → Pile
est_vide : Pile → Booléen
empiler : Pile x Elément → Pile
dépiler : Pile → Pile
sommet : Pile → Elément
Préconditions
dépiler(p) est-défini-ssi est_vide(p) = faux
sommet(p) est-défini-ssi est_vide(p) = faux
Axiomes
Soit, e : Element, p : Pile
est_vide(pile_vide) = vrai
est_vide(empiler(p,e)) = faux
dépiler(empiler(p,e)) = p
sommet(empiler(p,e)) = e

Master SID – Algorithmique avancée &

18
Programmation 2021-2022
 Représentations d'une Pile
• Représentation contiguë (par tableau) :
– Les éléments de la pile sont rangés dans un tableau
– Un entier représente la position du sommet de la pile

• Représentation chaînée (par pointeurs) :

– Les éléments de la pile sont chaînés entre eux
– Un pointeur sur le premier élément désigne la pile et
représente le sommet de cette pile
– Une pile vide est représentée par le pointeur NULL

Master SID – Algorithmique avancée &

19
Programmation 2021-2022
 Spécification d'une Pile Contiguë
/* fichier "Tpile.h" */
#ifndef _PILE_TABLEAU
#define _PILE_TABLEAU

#include "Booleen.h"

// Définition du type Pile (implémentée par un tableau)

#define MAX_PILE 7 /* taille maximale d'une pile */
typedef int Element; /* les éléments sont des int */

typedef struct {
Element elements[MAX_PILE]; /* les éléments de la pile */
int sommet; /* position du sommet */
} Pile;

// Déclaration des fonctions gérant la pile

Pile pile_vide ();
Pile empiler ( Pile p, Element e );
Pile depiler ( Pile p );
Element sommet ( Pile p );
Booleen est_vide ( Pile p );

#endif

Master SID – Algorithmique avancée &

20
Programmation 2021-2022
 Réalisation d'une Pile Contiguë
/* fichier "Tpile.c" */
// ajout d'un élément
#include "Tpile.h"
Pile empiler(Pile p, Element e) {
// Définition des fonctions gérant la pile if ([Link] >= MAX_PILE-1) {
printf("Erreur : pile pleine !\n");
// initialiser une nouvelle pile exit(-1);
Pile pile_vide() { }
Pile p;
[Link] = -1; ([Link])++;
return p; ([Link])[[Link]] = e;
} return p;
}
// tester si la pile est vide
Booleen est_vide(Pile p) {
if ([Link] == -1) return vrai; // enlever un élément
return faux; Pile depiler(Pile p) {
} /* pré-condition : pile non vide !*/
if (est_vide(p)) {
// Valeur du sommet de pile
Element sommet(Pile p) {
printf("Erreur: pile vide !\n");
/* pré-condition : pile non vide ! */ exit(-1);
if (est_vide(p)) { }
printf("Erreur: pile vide !\n"); [Link]--;
exit(-1); return p;
}
return ([Link])[[Link]]; }
}

Master SID – Algorithmique avancée &

21
Programmation 2021-2022
 Utilisation d'une Pile Contiguë
/* fichier "UTpile.c" */
#include <stdio.h>
#include "Tpile.h"

int main () {
Pile p = pile_vide();

p = empiler(p,50);
p = empiler(p,5);
p = empiler(p,20);
p = empiler(p,10);
printf("%d au sommet après empilement de 50, 5, 20 et"
" 10\n", sommet(p));
p = depiler(p);
p = depiler(p);
printf("%d au sommet après dépilement de 10 et 20\n",
sommet(p));
return 0;
}

Master SID – Algorithmique avancée &

22
Programmation 2021-2022
 Notion de File (Queue)
• Une file est :
– une structure linéaire permettant de stocker et de restaurer des données
selon un ordre FIFO (First In, First Out ou « premier entré, premier sorti »)

• Dans une file :

– Les insertions (enfilements) se font à une extrémité appelée queue de la file
et les suppressions (défilements) se font à l'autre extrémité appelée tête de la
file

• Applications :
– Gestion travaux d’impression d’une imprimante
– Ordonnanceur (dans les systèmes d’exploitation)
– Parcours « en largeur » d’un arbre (voir arbres)
– …

Master SID – Algorithmique avancée &

23
Programmation 2021-2022
 Type Abstrait File
Type File
Utilise Elément, Booléen
Opérations
file_vide : → File
est_vide : File → Booléen
enfiler : File x Elément → File
défiler : File → File
tête : File → Elément
Préconditions
défiler(f) est-défini-ssi est_vide(f) = faux
tête(f) est-défini-ssi est_vide(f) = faux
Axiomes
Soit, e : Element, f : File
est_vide(pile_vide) = vrai
est_vide(enfiler(f,e)) = faux
si est_vide(f) = vrai alors tête(enfiler(f,e)) = e
si est_vide(f) = faux alors tête(enfiler(f,e)) = tête(f)
si est_vide(f) = vrai alors défiler(enfiler(f,e)) = file_vide
si est_vide(f) = faux
alors défiler(enfiler(f,e)) = enfiler(défiler(f),e)

Master SID – Algorithmique avancée &

24
Programmation 2021-2022
 Représentations d’une File
• Représentation contiguë (par tableau) :
– Les éléments de la file sont rangés dans un tableau
– Deux entiers représentent respectivement les positions de
la tête et de la queue de la file

• Représentation chaînée (par pointeurs) :

– Les éléments de la file sont chaînés entre eux
– Un pointeur sur le premier élément désigne la file et
représente la tête de cette file
– Un pointeur sur le dernier élément représente la queue de
file
– Une file vide est représentée par le pointeur NULL

Master SID – Algorithmique avancée &

25
Programmation 2021-2022
 Notion de Liste
• Généralisation des piles et des files
– Structure linéaire dans laquelle les éléments peuvent être traités les uns à la suite des
autres
– Ajout ou retrait d'éléments n’importe où dans la liste
– Accès à n'importe quel élément

• Une liste est :

– une suite finie, éventuellement vide, d'éléments de même type repérés par leur rang
dans la liste

• Dans une liste :

– Chaque élément de la liste est rangé à une certaine place
– Les éléments d'une liste sont donc ordonnés en fonction de leur place

• Remarques :
– Il existe une fonction notée succ qui, appliquée à toute place sauf la dernière, fournit la
place suivante
– Le nombre total d'éléments, et par conséquent de places, est appelé longueur de la liste

• Applications :
– Codage des polynômes, des matrices creuses, des grands nombres, …

Master SID – Algorithmique avancée &

26
Programmation 2021-2022
 Type Abstrait Liste
Type Liste
Utilise Elément, Booléen, Place
Opérations
liste_vide : → Liste
longueur : Liste → Entier
insérer : Liste x Entier x Elément → Liste
supprimer : Liste x Entier → Liste
kème : Liste x Entier → Elément
accès : Liste x Entier → Place
contenu : Liste x Place → Elément
succ : Liste x Place → Place
Préconditions
insérer(l,k,e) est-défini-ssi 1 ≤ k ≤ longueur(l)+1
supprimer(l,k) est-défini-ssi 1 ≤ k ≤ longueur(l)
kème(l,k) est-défini-ssi 1 ≤ k ≤ longueur(l)
accès(l,k) est-défini-ssi 1 ≤ k ≤ longueur(l)
succ(l,p) est-défini-ssi p ≠ accès(l,longueur(l))

Master SID – Algorithmique avancée &

27
Programmation 2021-2022
 Représentation contigüe d’une Liste
• Les éléments sont rangés les uns à côté des autres dans un
tableau
– La ième case du tableau contient le ième élément de la liste
– Le rang est donc égal à la place ; ce sont des entiers

• La liste est représentée par une structure en langage C :

– Un tableau représente les éléments
– Un entier représente le nombre d'éléments dans la liste
– La longueur maximale, MAX_LISTE, de la liste doit être connue

Master SID – Algorithmique avancée &

28
Programmation 2021-2022
 Représentation chaînée d’une Liste
• Les éléments ne sont pas rangés les uns à côté des autres
– La place d'un élément est l'adresse d'une structure qui contient
l'élément ainsi que la place de l'élément suivant
– Utilisation de pointeurs pour chaîner entre eux les éléments
successifs

• La liste est représentée par un pointeur sur une structure en

langage C
– Une structure contient un élément de la liste et un pointeur sur
l'élément suivant
– La liste est déterminée par un pointeur sur son premier élément
– La liste vide est représentée par la constante prédéfinie NULL

Master SID – Algorithmique avancée &

29
Programmation 2021-2022
Spécification d'une Liste Chaînée
/* fichier "CListe.h" */
#ifndef _LISTE_CHAINEE
#define _LISTE_CHAINEE
// Définition du type liste (implémentée par pointeurs)
typedef int element; /* les éléments sont des int */
typedef struct cellule *Place; /* la place = adresse cellule */
typedef struct cellule {
element valeur; // un éléments de la liste
struct cellule *suivant; // adresse cellule suivante
} Cellule;
typedef Cellule *Liste; type Liste : un
// Déclaration des fonctions gérant la liste pointeur de Cellule
Liste liste_vide (void);
int longueur (Liste l);
Liste inserer (Liste l, int i, element e);
Liste supprimer (Liste l, int i);
element keme (Liste l, int k);
Place acces (Liste l, int i);
element contenu (Liste l, Place i);
Place succ (Liste l, Place i);
#endif

Master SID – Algorithmique avancée &

30
Programmation 2021-2022
Réalisation d'une Liste Chaînée (1)
Liste liste_vide(void) { else {
return NULL; int j;
} Liste p=l;
for (j=0; j<i-1; j++)
int longueur(Liste l) { p=p->suivant;
int taille=0; pc->suivant=p->suivant;
Liste p=l; p->suivant=p;
while (p) { }
taille++; return l;
p=p->suivant; }
}
return taille; Place acces(Liste l, int k) {
} // pas de sens que si 0 ≤ k ≤ longueur(l)-1
int i;
Liste inserer(Liste l, int i, element e) { Place p;
// précondition :0 ≤ i < longueur(l)+1 if (k<0 || k>=longueur(l)) {
if (i<0 || i>longueur(l)) { printf("Erreur: rang invalide !\n");
printf("Erreur : rang non valide !\n"); exit(-1);
exit(-1); }
} if (k == 0)
Liste pc = (Liste)malloc(sizeof(Cellule)); return l;
pc->valeur=e; else {
pc->suivant=NULL; p=l;
if (i==0){ for(i=0; i<k; k++)
pc->suivant=l; p=p->suivant;
l=pc; return p;
} }
}

Master SID – Algorithmique avancée &

31
Programmation 2021-2022
Réalisation d'une Liste Chaînée (2)
element contenu(Liste l, Place p) {
// pas de sens si longueur(l)=0 (liste vide) Liste supprimer(Liste l, int i) {
if (longueur(l) == 0) {
printf("Erreur: liste vide !\n"); // précondition : 0 ≤ i < longueur(l)
exit(-1); int j;
} Liste p;
return p->valeur; if (i<0 || i>longueur(l)+1) {
} printf("Erreur: rang non valide!\n");
Place succ(Liste l, Place p) { exit(-1);
// pas de sens si p dernière place de liste }
if (p->suivant == NULL) { if (i == 0) {
printf("Erreur: suivant dernière p=l;
place!\n");
exit(-1); l=l->suivant;
} }
return p->suivant; else {
} Place q;
element keme(Liste l, int k) { q=acces(l,i-1);
// pas de sens que si 0 <= k <= longueur(l)-1 p=succ(l,q);
if (k<0 || k>longueur(l)-1) { q->suivant=p->suivant;
printf("Erreur : rang non valide !\n"); }
exit(-1); free(p);
}
return contenu(l, acces(l,k)); return l;
} }

Master SID – Algorithmique avancée &

32
Programmation 2021-2022
 Variantes de Listes Chaînées
• Liste avec tête fictive
– Eviter d'avoir un traitement particulier pour le cas de la tête de liste (opérations d'insertion et de
suppression)

• Liste chaînée circulaire

– Le suivant du dernier élément de la liste est le pointeur de tête

• Liste doublement chaînée

– Faciliter le parcours de la liste dans les deux sens (utilisation de deux pointeurs…)

• Liste doublement chaînée circulaire

• Liste triée
– L’ordre des enregistrements dans la liste respecte l’ordre sur les clés

Master SID – Algorithmique avancée &

33
Programmation 2021-2022
 Opérations sur les Listes
• Soit n le nombre d’éléments d’une liste :

Master SID – Algorithmique avancée &

34
Programmation 2021-2022
Structures de Données
Non-Linéaires
Arbres (Trees)
 Notion d’Arbre (Tree)
• Un arbre est :
– Une structure non linéaire qui permet d’obtenir des algorithmes plus
performants que lorsqu’on utilise des structures de données linéaires

• Il permet :
– une organisation naturelle des données

• Exemples :
– Organisation des fichiers dans les systèmes d'exploitation
– Table des matières d’un livre
– Représentation de la structure syntaxique des programmes sources
dans les compilateurs
– Représentation d'un arbre généalogique
– …

Master SID – Algorithmique avancée &

36
Programmation 2021-2022
 Notion d’Arbre Binaire (Binary Tree)
• Un arbre binaire A est :
– soit vide (A = ( ) ou A = ø),
– soit de la forme A = <r, A1, A2>, c-à-d composé :
• d'un nœud r appelé racine contenant un élément
• et de deux arbres binaires disjoints A1 et A2, appelés respectivement sous
arbre gauche (ou fils gauche) et sous arbre droit (ou fils droit)

• Exemple :

Master SID – Algorithmique avancée &

37
Programmation 2021-2022
Représenter un Arbre Général par un
Arbre Binaire
• Un arbre binaire peut être utilisé :
– pour représenter un arbre général où les nœuds peuvent
avoir un nombre quelconque de fils
– Dans cet arbre binaire, le fils gauche sera le fils aîné du
nœud courant et le fils droit le frère cadet du noeud
courant.
– la racine de l'arbre binaire n'a pas de fils droit.
• Exemple :

Un arbre général Arbre binaire

correspondant
(3-aire)

Master SID – Algorithmique avancée &

38
Programmation 2021-2022
 Arbres Binaires Particuliers
• Arbre binaire complet :

• Arbre binaire parfait :

Master SID – Algorithmique avancée &

39
Programmation 2021-2022
 Propriétés des arbres binaires

• Pour tout arbre binaire de taille n et de hauteur h :

Master SID – Algorithmique avancée &

40
Programmation 2021-2022
 Type Abstrait Arbre_Binaire
Type Arbre_Binaire
Utilise Noeud, Elément, Booléen
Opérations
arbre_vide : → Arbre_Binaire
est_vide : Arbre_Binaire → Booléen
cons : Noeud x Arbre_Binaire x Arbre_Binaire → Arbre_Binaire
racine : Arbre_Binaire → Noeud
gauche : Arbre_Binaire → Arbre_Binaire
droite : Arbre_Binaire → Arbre_Binaire
contenu : Noeud → Elément
Préconditions
racine(A) est-défini-ssi est_vide(A) = faux
gauche(A) est-défini-ssi est_vide(A) = faux
droite(A) est-défini-ssi est_vide(A) = faux
Axiomes
Soit, r : Nœud, A1, A2 : Arbre_Binaire
racine(<r, A1, A2>) = r
gauche(<r, A1, A2>) = A1
droite(<r, A1, A2>) = A2

Master SID – Algorithmique avancée &

41
Programmation 2021-2022
 Parcours d‘Arbre Binaire
(Affichage du contenu des nœuds)

• Le parcours préfixe affiche les nœuds dans l'ordre : 1, 2, 4, 5, 3, 6, 8, 9, 12, 13, 7, 10, 11
• Le parcours infixe affiche les nœuds dans l'ordre : 4, 2, 5, 1, 8, 6, 12, 9, 13, 3, 10, 7, 11
• Le parcours postfixe affiche les nœuds dans l'ordre : 4, 5, 2, 8, 12, 13, 9, 6, 10, 11, 7, 3, 1

• Le parcours en largeur affiche les nœuds dans l’ordre : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

Master SID – Algorithmique avancée &

42
Programmation 2021-2022
 Représentations d'un Arbre Binaire
• Représentation par tableau (par contiguïté)
– Idéale pour les arbres binaires parfaits…

• Représentation par pointeurs (par chaînage)

– Chaque nœud a trois champs :
• val (l'élément stocké dans le noeud) ;
• fg (pointeur sur fils gauche) ;
• fd (pointeur sur fils droit).

– Un arbre est désigné par un pointeur sur sa racine

– Un arbre vide est représenté par le pointeur NULL

Master SID – Algorithmique avancée &

43
Programmation 2021-2022
 Représentation par Contiguïté
(Exemple)
• Un arbre binaire parfait :

• Sa représentation par tableau compact :

Master SID – Algorithmique avancée &

44
Programmation 2021-2022
 Représentation Chaînée d’un Arbre
Binaire
En langage C : Exemple :

typedef int Element;

typedef struct noeud *Pnoeud;
typedef struct noeud {
Element val;
Pnoeud fg;
Pnoeud fd;
} Noeud;
typedef Noeud *Arbre_Binaire;

Master SID – Algorithmique avancée &

45
Programmation 2021-2022
 Réalisation Chaînée
d'un Arbre Binaire (1)
Arbre_Binaire arbre_vide() {
return NULL;
} Arbre_Binaire cons(Noeud *r,
Arbre_Binaire G,
Booleen est_vide(Arbre_Binaire A) { Arbre_Binaire D) {
return A == NULL ; r->fg = G ;
} r->fd = D ;
return r ;
Pnoeud nouveau_noeud(Element e) { }
// faire une allocation mémoire et placer
l'élément e
// en cas d'erreur d'allocation, le pointeur Noeud racine(Arbre_Binaire A) {
renvoyé est NULL // précondition : A est non vide !
Pnoeud p = (Pnoeud) malloc(sizeof(Noeud)); if (estvide(A)) {
if (p != NULL) { printf("Erreur : Arbre vide !\n");
exit(-1);
p->val = e;
}
p->fg = NULL; return (*A) ;
p->fd = NULL; }
}
return (p);
}

Master SID – Algorithmique avancée &

46
Programmation 2021-2022
 Réalisation Chaînée
d'un Arbre Binaire (2)
Arbre_Binaire gauche(Arbre_Binaire A) {
// précondition : A est non vide !
if (estvide(A)) {
printf("Erreur : Arbre vide !\n");
exit(-1);
}
return A->fg ; /* ou bien (*A).fg; */
}

Arbre_Binaire droite(Arbre_Binaire A) {
// précondition : A est non vide !
if (estvide(A)) {
printf("Erreur : Arbre vide !\n");
exit(-1);
}
return A->fd ; /* ou bien (*A).fd; */
}

Element contenu(Noeud n) {
return [Link];
}

Master SID – Algorithmique avancée &

47
Programmation 2021-2022
 Applications d’Arbre Binaire
• Recherche dans un ensemble de valeurs :
– Les arbres binaires de recherche ;

• Tri d’un ensemble de valeurs :

– Le parcours GRD d’un arbre binaire de recherche ;
– Un algorithme de tri efficace utilisant une structure de tas ;

• Représentation d’une expression arithmétique :

– Un parcours GDR pour avoir une notation postfixée ;

• Méthodes de compression :
– Le codage de Huffman utilisant des arbres binaires ;
– La compression d’images utilisant des quadtrees (arbres quaternaires, ou
chaque nœud non feuille a exactement quatre fils) ;

• …
Master SID – Algorithmique avancée &
48
Programmation 2021-2022
 Notion d’Arbre Binaire de recherche
(Binary Search Tree)
• Un arbre binaire de recherche (ABR), est un arbre binaire tel
que pour tout nœud :
– les clés de tous les noeuds du sous-arbre gauche sont inférieures ou
égales à la clé du nœud,
– les clés de tous les noeuds du sous-arbre droit sont supérieures à la
clé du nœud.

• Chaque nœud d'un arbre binaire de recherche désigne :

– un élément qui est caractérisé par une clé (prise dans un ensemble
totalement ordonné) et des informations associées à cette clé.

• Exemple :
– Un ABR qui représente E = {a, d, e, g, i, l, q, t}

Master SID – Algorithmique avancée &

49
Programmation 2021-2022
 Opérations sur un ABR
• Le type abstrait arbre binaire de recherche :
– noté Arbre_Rech
– décrit de la même manière que le type Arbre_Binaire

• On reprend les opérations de base des arbres binaires :

– on suppose l'existence de l'opération clé sur le type abstrait Element

• En tenant compte du critère d'ordre, les opérations

spécifiques de ce type d'arbre concernent :
– la recherche d'un élément dans l'arbre ;
– l'insertion d'un élément dans l'arbre ;
– la suppression d'un élément de l'arbre.

Master SID – Algorithmique avancée &

50
Programmation 2021-2022
 Recherche dans un ABR
(Exemples)
• Recherche avec succès :
– Recherche de 76

• Recherche sans succès :

– Recherche de 25

Master SID – Algorithmique avancée &

51
Programmation 2021-2022
 Recherche d'un élément
(Spécification)
Extension Type Arbre_Rech
Utilise Elément, Booléen
Opérations
Rechercher : Elément x Arbre_Rech → Booléen
Axiomes
Soit, x : Elément, r : Nœud, G, D : Arbre_Rech

Rechercher(x, arbre_vide) = faux

si clé(x) = clé(contenu(r))
alors Rechercher(x, <r, G, D>) = vrai
si clé(x) < clé(contenu(r))
alors Rechercher(x, <r, G, D>) = Rechercher(x, G)
si clé(x) > clé(contenu(r))
alors Rechercher(x, <r, G, D>) = Rechercher(x, D)

Master SID – Algorithmique avancée &

52
Programmation 2021-2022
 Ajout "en feuille" d'un élément
(Spécification)
Extension Type Arbre_Rech
Utilise Elément
Opérations
Ajouter_feuille : Elément x Arbre_Rech → Arbre_Rech
Axiomes
Soit, x : Elément, r : Nœud, G, D : Arbre_Rech

Ajouter_feuille(x, arbre_vide) = <x, arbre_vide, arbre_vide>

si clé(x) ≤ clé(contenu(r))
alors
Ajouter_feuille(x, <r, G, D>) = <r, Ajouter_feuille(x, G),
D>
sinon
Ajouter_feuille(x, <r, G, D>) = <r, G, Ajouter_feuille(x, D)>

Master SID – Algorithmique avancée &

53
Programmation 2021-2022
 Ajout en Feuille d’un ABR
(Exemples)
• Ajout de l’élément 14 :

• Ajout successif des éléments :

– e, i, a, t, d, g, q et l dans un ABR, initialement vide.

Master SID – Algorithmique avancée &

54
Programmation 2021-2022
 Suppression d'un élément
(Spécification)
Extension Type Arbre_Rech
Utilise Elément
Opérations
Max : Arbre_Rech → Elément
SupprimerMax : Arbre_Rech → Arbre_Rech
Supprimer : Elément x Arbre_Rech → Arbre_Rech
Pré-conditions
Max(A) est_défini_ssi est_vide(A) = faux
SupprimerMax(A) est_défini_ssi est_vide(A) = faux
Axiomes
Soit, x : Elément, r : Nœud, G, D : Arbre_Rech
si est_vide(D) = vrai alors Max(<r, G, D>) = r
sinon Max(<r, G, D>) = Max(D)
si est_vide(D) = vrai alors SupprimerMax(<r, G, D>) = G
sinon SupprimerMax(<r, G, D>) = <r, G, SupprimerMax(D)>
Supprimer(x, arbre_vide) = arbre_vide
si clé(x) = clé(contenu(r)) et est_vide(D) = vrai
alors Supprimer(x, <r, G, D>) = G
sinon si clé(x) = clé(contenu(r)) et est_vide(G) = vrai
alors Supprimer(x, <r, arbre_vide, D>) = D
sinon si clé(x) = clé(contenu(r))
alors Supprimer(x, <r, G, D>) = <Max(G),SupprimerMax(G), D>
si clé(x) < clé(contenu(r))
alors Supprimer(x, <r, G, D>) = <r, Supprimer(x, G), D>
si clé(x) > clé(contenu(r))
alors Supprimer(x, <r, G, D>) = <r, G, Supprimer(x, D)>

Master SID – Algorithmique avancée &

55
Programmation 2021-2022
 Suppression dans un ABR
(Exemples)
• 1er cas :
– Nœud sans fils

• 2ème cas :
– Nœud ayant un fils

• 3ème cas :
– Nœud ayant deux fils
Master SID – Algorithmique avancée &
56
Programmation 2021-2022
 Suppression dans un ABR
(Réalisation)
fonction Supprimer(x: Elément, A: Arbre_Rech): Arbre_Rech
fonction Max(A: Arbre_Rech): Pnoeud
si est_vide(A) alors retourner A (* ou <erreur> *)
(* A doit être non vide ! *)
sinon
si est_vide(droite(A))
si x > contenu(racine(A)) alors
alors retourner A
sinon retourner Max(droite(A)) retourner cons(A, gauche(A), Supprimer(x ,droite(A)))
fsi sinon
Ffonction si x < contenu(racine(A)) alors
retourner cons(A, Supprimer(x, gauche(A)), droite(A))
sinon
fonction SupprimerMax(A: Arbre_Rech): Arbre_Rech si est_vide(droite(A)) alors retourner gauche(A)
(* A doit être non vide ! *) sinon
si est_vide(droite(A)) alors si est_vide(gauche(A)) alors retourner droite(A)
retourner gauche(A) sinon
sinon retourner cons(Max(gauche(A)),
retourner cons(A, gauche(A), SupprimerMax(gauche(A)), droite(A))
SupprimerMax(droite(A))) fsi
fsi fsi
ffonction fsi
fsi
fsi
ffonction

Master SID – Algorithmique avancée &

57
Programmation 2021-2022
 Opérations sur un ABR
(Complexité)
• Toutes les opérations sont en O(h), où h est la
hauteur de l’ABR

• Si n éléments ont été insérés dans l'arbre :

– Au pire, h = n - 1 →O(n)
• éléments insérés en ordre
– Au mieux, h = log2 n → O(log n)
• pour un arbre binaire complet
– En moyenne, on peut montrer que h = O(log n)
• en supposant que les éléments ont été insérés en ordre aléatoire

Master SID – Algorithmique avancée &

58
Programmation 2021-2022
Structures de Données Avancées
✓ Arbres équilibrés (AVL, Rouge/Noir, B-Arbres)
✓ Tables de hachage
✓ Tas et files de priorités
✓ Graphes
 Notion d'Arbre Maximier (ou Tas)
• Un tas (Heap, en anglais) est :
– un arbre binaire parfait tel que la clé de chaque noeud est supérieure ou égale aux clés
de tous ses fils
– L'élément maximum de l'arbre se trouve donc à la racine

• Un tas est un arbre binaire partiellement ordonné :

– Les nœuds sur chaque branche sont ordonnés sur celle-ci ;
– Ceux d'un même niveau ne le sont pas nécessairement.
• Un arbre maximier (resp. minimier) est :
– Un tas dans lequel chaque nœud enfant a une clé inférieure (resp., supérieure) ou
égale à la clé de son père

• Exemple :

Master SID – Algorithmique avancée &

60
Programmation 2021-2022
 Type Abstrait Tas
Type Tas
Utilise Booléen, Elément
Opérations
tas_vide : → Tas
est_vide : Tas → Booléen
max : Tas → Elément
ajouter : Tas x Elément → Tas
supprimerMax : Tas → Tas
appartient : Tas x Elément → Booléen
Préconditions
max(T) est_défini_ssi est_vide(T) = faux
supprimerMax(T) est_défini_ssi est_vide(T) = faux
ajouter(T,e) est_défini_ssi appartient(T,e) = faux
Axiomes
Soit, T, T1 : Tas, e, e1 : Elément

si est_vide(T) = vrai alors appartient(T,e) = faux

sinon si T = ajouter(T1,e1)
alors appartient(T,e) = (e = e1) ou appartient(T1,e)
sinon si T = supprimerMax(T1)
alors appartient(T,e) = (e ≠ max(T1)) et appartient(T1,e)
appartient(T,max(T)) = vrai
si appartient(T,e) = vrai alors max(T) ≥ e

Master SID – Algorithmique avancée &

61
Programmation 2021-2022
 Représentation d'un Tas
• Exemple : Un tas avec sa numérotation
hiérarchique

Le tableau
représentant le tas
• En C :
#define MAX_ELEMENTS 200 // taille maximum du tas
typedef int Element; // un élément est un int
typedef struct {
int taille; // nombre d'éléments dans le tas
Element tableau[MAX]; // les éléments du tas
} Tas;
Master SID – Algorithmique avancée &
62
Programmation 2021-2022
 Opération d’Ajout
(Exemple)
• Insérer la valeur 21 :
b
a

c d

Master SID – Algorithmique avancée &

63
Programmation 2021-2022
Opération de Suppression du
Maximum (Exemple)
c
b

e
d

Master SID – Algorithmique avancée &

64
Programmation 2021-2022
 Opérations sur un Tas
(Complexité)
• On considère un Tas :
– comportant n éléments

• Ajout et Suppression du maximum :

– en O(log(n))

• Recherche du maximum :
– en O(1)

Master SID – Algorithmique avancée &

65
Programmation 2021-2022
Arbres de Recherche Equilibrés

(Balanced Trees)
 Notion d'Arbres
de Recherche Equilibrés
• La définition des arbres équilibrés:
– Impose que la différence entre les hauteurs des fils gauche et des fils droit de tout
nœud ne peut excéder 1
– Il faut donc maintenir l'équilibre de tous les nœuds au fur et à mesure des
opérations d'insertion ou de suppression d'un nœud
• ce serait très coûteux
• Il faut donc établir des conditions plus faibles, qui nous assurent des gains en performance

• En cas déséquilibre entre deux fils d'un nœud:

– Il faut recréer un équilibre par des rotations d'arbres ou par éclatement de
nœuds (cas des arbres B)
• Deux types d’arbres de recherche équilibrés :
– 1er type (insertion comme pour les ABR, suivie d’un rééquilibrage) :
• Arbres AVL
• Arbres rouge-noir
• …
– 2ème type (plusieurs clés par nœud) :
• B-Arbres
• …

Master SID – Algorithmique avancée &

67
Programmation 2021-2022
Arbres de Recherche Equilibrés
(AVL)
 Arbres Equilibrés AVL
• Introduits :
– par Adelson-Velskii Landis Landis (d'où le nom d'AVL) dans les
années 60 ;
• Un arbre AVL est :
– un arbre binaire de recherche stockant une information
supplémentaire pour chaque noeud : son facteur d'équilibre ;
• Le facteur d'équilibre d’un nœud :
– représente la différence des hauteurs entre son sous arbre
gauche et son sous arbre droit ;
– Au fur et à mesure que des nœuds sont insérés ou supprimés, un arbre
AVL s'ajuste de lui-même pour que tous ses facteurs d'équilibres restent à
0, -1 ou 1.
– Avec cette condition, on est assuré de toujours avoir un arbre dont la
hauteur est proportionnelle à log(n), où n est la taille de l’arbre

Master SID – Algorithmique avancée &

69
Programmation 2021-2022
Facteur d’équilibre (Exemple)

Master SID – Algorithmique avancée &

70
Programmation 2021-2022
Arbres AVL (Exemple)
12

8 16

4 10 14

2 6

Cet arbre est un arbre AVL

Master SID – Algorithmique avancée &

71
Programmation 2021-2022
 Arbres AVL (Exemple)
Ces nœuds violent 12
la condition

8 16

4 10 14

2 6

1
Après l’ajout de 1 ce n’est plus un arbre AVL
Master SID – Algorithmique avancée &
72
Programmation 2021-2022
 Arbres AVL (Exemple)
12

8 16 Ce nœud viole
la condition

4 10 14

2 6 13

Après l’ajout de 13 ce n’est plus un arbre AVL

Master SID – Algorithmique avancée &

73
Programmation 2021-2022
Arbres AVL (Comment procéder ?)
• Que faire ?
– après chaque insertion ou suppression, rétablir l’équilibre s’il a été
rompu par l’opération

• Observation importante :
– après une insertion, seuls les nœuds qui sont sur le chemin du point
d’insertion à la racine sont susceptibles d’être déséquilibrés

• Deux cas:
– insertion dans le sous-arbre de gauche du fils gauche ou dans le sous-
arbre de droite du fils droit :
Rotation simple

– insertion dans le sous-arbre de droite du fils gauche ou dans le sous-

arbre de gauche du fils droit :
 Rotation double

Master SID – Algorithmique avancée &

74
Programmation 2021-2022
 Rotations

• Les rotations conservent :

– La propriété d’arbre binaire de recherche
– Le parcours infixe

Master SID – Algorithmique avancée &

75
Programmation 2021-2022
 AVL (Exemple de Rotation Simple)
12

8 16

Hauteur = 2
4 10 14

2 6
Hauteur = 0

Master SID – Algorithmique avancée &

76
Programmation 2021-2022
AVL (Exemple de Rotation Simple)
12

8 16

4 10 14

2 6

Master SID – Algorithmique avancée &

77
Programmation 2021-2022
AVL (Exemple de Rotation Simple)
12

4 16

14
2 8

10
6
1

Master SID – Algorithmique avancée &

78
Programmation 2021-2022
AVL (Exemple de Rotation Simple)
12

4 16

14
2 8

10
6
1

Master SID – Algorithmique avancée &

79
Programmation 2021-2022
 Arbres AVL – Rotation Simple
(gauche ou droite)
Nœud *RG(Nœud *a) {
Nœud *b;
b = a->fd;
a->fd = b->fg; Rotation gauche
b->fg = a;
return b;
}
Nœud *RD(Nœud *a) {
Nœud *b;
b = a->fg; Rotation droite
a->fg = b->fd;
b->fd = a;
return b;
}
Master SID – Algorithmique avancée &
80
Programmation 2021-2022
AVL (Exemple de Rotation Double)

12

8 16

4 10 14

2 6

Noeud inséré
7
Master SID – Algorithmique avancée &
81
Programmation 2021-2022
AVL (Exemple de Rotation Double)

12

8 16

4 10 14

2 6

7
Master SID – Algorithmique avancée &
82
Programmation 2021-2022
AVL (Exemple de Rotation Double)

12

8 16

6 10 14

4 7

2
Master SID – Algorithmique avancée &
83
Programmation 2021-2022
AVL (Exemple de Rotation Double)

12

8 16

6 10 14

4 7

2
Master SID – Algorithmique avancée &
84
Programmation 2021-2022
AVL (Exemple de Rotation Double)

12

6 16

14
4 8

10
2 7

Master SID – Algorithmique avancée &

85
Programmation 2021-2022
 Arbres AVL – Rotation Double
(gauche droite ou droite gauche)
Nœud *RGD(Nœud *a) {

a->fg = RG(a->fg); Rotation gauche droite

return (RD(a));
}

Nœud *RDG(Nœud *a) {

a->fd = RD(a->fd); Rotation droite gauche

return (RG(a));
}

Master SID – Algorithmique avancée &

86
Programmation 2021-2022
 Insertion dans un arbre AVL
• En deux étapes :
– Insérer le nœud exactement de la même manière que
dans un arbre binaire de recherche
– Remonter depuis le nœud inséré vers la racine en
effectuant une rotation sur chaque sous-arbre déséquilibré

• Il suffit :
– d'une rotation simple ou d'une double rotation pour
rééquilibrer un arbre AVL après une insertion

• Complexité en O(log(n) :
– La hauteur de l'arbre étant en O(log(n)), et les rotations
étant à temps constant

Master SID – Algorithmique avancée &

87
Programmation 2021-2022
 Insertion dans un arbre AVL
(Exemple détaillé)
Pour chaque nœud, mettre :

0 si ses deux sous-arbres ont la même profondeur

+n si le sous-arbre gauche est plus profond avec une différence = n

-n si le sous-arbre droit est plus profond avec une différence = n

Séquence d’insertion :

2 10 12 4 16 8 6 14

Master SID – Algorithmique avancée &

88
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

0
2

Master SID – Algorithmique avancée &

89
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

-1
2

10 0

Master SID – Algorithmique avancée &

90
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

-2
2

-1
10

12 0

Master SID – Algorithmique avancée &

91
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

0
10

2 0 12 0

Rotation simple

Master SID – Algorithmique avancée &

92
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

1
10

2 -1 12 0

4 0

Master SID – Algorithmique avancée &

93
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

10 0

2 -1 12 -1

4 0 16 0

Master SID – Algorithmique avancée &

94
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

1
10

-1
2 -2 12

-1
4 16 0

8 0

Master SID – Algorithmique avancée &

95
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

0
10

4 0
12 -1

0 2 8 0 16 0

Rotation simple

Master SID – Algorithmique avancée &

96
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

1
10

-1
4 -1 12

0 2 8 1 16 0

6 0

Master SID – Algorithmique avancée &

97
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

0
10

4 -1 12 -2

1
0
2 8 1 16

6 0 14 0

Master SID – Algorithmique avancée &

98
Programmation 2021-2022
 Insertion dans un AVL
(Exemple détaillé)
2 10 12 4 16 8 6 14

1
10

4 -1 14 0

0
2 8 1 12 16
0
0

6 0

Rotation double
Master SID – Algorithmique avancée &
99
Programmation 2021-2022
 Insertion dans un AVL
(Autre exemple)
Exemple où la rotation se fait loin du point d’insertion :

2
10

4 -1 14 0

1
2 8 1 12 16
0 0

0
1 6 -1 9 0

7
0

Noeud inséré
Master SID – Algorithmique avancée &
100
Programmation 2021-2022
 Insertion dans un AVL
(Autre exemple)
Exemple où la rotation se fait loin du point d’insertion :

0
8

0 -1
4 10

1
2 6 0 14 0
-1 9
0
0
0
1 7 0 12 16

Après rotation double

Master SID – Algorithmique avancée &
101
Programmation 2021-2022
 Suppression dans un AVL
• Etape 1 :
– Suppression d'un élément dans un AVL de la même façon que
pour les arbres binaires de recherche :
• remplacer l'élément à supprimer par son prédécesseur ou son
successeur dans l’arbre.
• Etape 2 :
– L'arbre résultant d'une telle suppression peut ne pas être un
AVL :
• il faut alors le réorganiser en arbre AVL.
• le rééquilibrage après suppression fait intervenir les mêmes
techniques que le rééquilibrage après insertion
• dans le cas d'une suppression, la réorganisation de l'arbre peut
nécessiter plusieurs rotations successives, sur le chemin de la feuille
supprimée jusqu'à la racine.
• Complexité en log(n)
Master SID – Algorithmique avancée &
102
Programmation 2021-2022
Suppression dans un AVL
(Exemple 1)

Delete 14

Master SID – Algorithmique avancée &

103
Programmation 2021-2022
Suppression dans un AVL
(Exemple 2)

Delete 40
right rotation, with node 35 as
the pivot

The pivot node is the first node that

has a bf of 2 or -2
Master SID – Algorithmique avancée &
104
Programmation 2021-2022
Suppression dans un AVL
(Exemple 2’)

Delete 32
left rotation, with node 44 as
the pivot

Master SID – Algorithmique avancée &

105
Programmation 2021-2022
Suppression dans un AVL
(Exemple 3)
Delete 40

right rotation, with node 35 as

the pivot

right rotation, with node

30 as the pivot

0
Master SID – Algorithmique avancée &
106
Programmation 2021-2022
 Autre Exemple de Suppression (1)

Delete(20) Backup
1 1 Rotate
10 10 2 10 4 -1

0 4 20 0 0 4 0 4 3 10 1
0

0 3 5 0 0 3 5 0 0 3 5 0 0 5

Initial AVLTree Tree after Idenfitied 10 as the AVL Tree after

deletion of 20 pivot LL Correction

Now, backup the tree Classify the type

updating balance of imbalance
factors
• LL Imbalance:
– bf of P(10) is 2
– bf of L(4) is 0 or 1
Master SID – Algorithmique avancée &
107
Programmation 2021-2022
 Autre Exemple de suppression(2)

Delete(20) Backup
1 1 Rotate
10 10 2 10 5 0

-1 4 2
20 0 -1 4 -1 4 0 4 10 0
1
5 0 AVL Tree after
5 0 5 0
LL Correction
Initial AVLTree Tree after Idenfitied 10 as the
deletion of 20 pivot

Now, backup the tree Classify the type

updating balance of imbalance
factors
• LR Imbalance:
– bf of P(10) is 2
– bf of L(4) is -1
Master SID – Algorithmique avancée &
108
Programmation 2021-2022
 Autre Exemple de Suppression(3)
1
1 15
10 Delete(10)
-1
-1 1 5 20
1 5 20
1 3 -1 7 30 -1
1 3 -1 7 0 15 30 -1
1 2 0 4
1 2 0 4
0 8 0 40
0 8 0 40
0 1
0 1 Tree after deletion of 10
Initial AVLTree
We have copied the
successor of 10 to root and
deleted 15

Now, backup the tree

updating balance
Master SID – Algorithmique avancée & factors 109
Programmation 2021-2022
 Autre Exemple de Suppression(3) – (suite)
Rotate 1
Backup 1
15 15

-2 1 5 30 0
1 5 20

1 3 -1 7 30 -1 1 3 -1 7 20 0 40 0

1 2 1 2 0 4 0 8
0 4 0 8 0 40

0 1 0 1
Identified 20 as the pivot Tree after RR imbalance
is corrected
Classify the type of
imbalance Is this an AVL tree?

• RR Imbalance:
Continue backing up
– bf of P(20) is -2 the tree updating
– bf of R(30) is 0 or -1 balance factors
Master SID – Algorithmique avancée & 110
Programmation 2021-2022
 Autre Exemple de Suppression(3) – (suite)
Backup 2 15 Rotate 0 5

1 5 30 0 1 3 15 0

1 3 -1 7 20 0 40 0 1 2 0 4 7 -1 30 0

1 2 0 4 0 8 0 1
0 8 20 0 40 0

0 1 Final Tree
Identified 15 as the pivot

Classify the type of

imbalance

• LL Imbalance:
– bf of P(15) is 2
– bf of L(5) is 0 or 1
Master SID – Algorithmique avancée & 111
Programmation 2021-2022
 Recherche dans un AVL
• Identique à celle dans un ABR :
– Un AVL est un arbre binaire de recherche

• Complexité en O(log(n):
– Puisque la hauteur d'un arbre AVL est en O(log(n))

Master SID – Algorithmique avancée &

112
Programmation 2021-2022
Arbres de Recherche Equilibrés
(Rouge-Noir)
 Arbres Rouge-Noir
• Définition :
– Un arbre rouge-noir est un arbre binaire de recherche ayant
les propriétés suivantes :
1. Chaque nœud est soit rouge soit noir
2. La racine est noire
3. Si un nœud est rouge, tous ses enfants doivent être noirs
4. À partir de n’importe quel nœud, tous les chemins de la racine
jusqu’à un pointeur NULL doivent avoir le même nombre de nœuds
noirs

• Propriété :
– La racine est noire et il ne peut y avoir deux nœuds rouges
consécutifs :
→ la longueur de tout chemin de la racine à une feuille ne peut être
supérieure à 2 fois le nombre de nœuds noirs dans ce chemin

Master SID – Algorithmique avancée &

114
Programmation 2021-2022
Arbres Rouge-Noir (Exemple)
30

70
15

10 20 60 85

5 50 65 80 90

40 55

Master SID – Algorithmique avancée &

115
Programmation 2021-2022
Arbres Rouge-Noir (Exemple)
30

70
15

10 20 60 85

5 50 65 80 90

40 55

Master SID – Algorithmique avancée &

116
Programmation 2021-2022
Arbres Rouge-Noir (Contre-exemple)
30

70
15

10 60 85
2 noeuds noirs

5 50 65 80 90

83 95
40 55

4 noeuds noirs

Master SID – Algorithmique avancée &

117
Programmation 2021-2022
 Arbres Rouge-Noir (Insertion)
• Comment ? :
– Un nœud inséré est toujours une feuille
– On ne peut pas le colorier en noir, puisque cela
violerait la condition 4
– On colorie le nœud en rouge
– Si le père est noir, pas de problème
– Si le père est rouge, on viole la condition 3. Dans
ce cas, on ajuste l’arbre, par le biais de
changements de couleurs et de rotations
Master SID – Algorithmique avancée &
118
Programmation 2021-2022
 Premier cas : le frère du nœud parent est noir (on
utilise la convention qu’un nœud NULL est noir)

Noeud inséré
G P

S X G
P

D E A B C S
X C

D E
A B

Rotation simple

Master SID – Algorithmique avancée &

119
Programmation 2021-2022
Premier cas : le frère du nœud parent est noir (on
utilise la convention qu’un nœud NULL est noir)

G X

S P G
P

D E A B C S
A X

D E
B C

Noeud inséré

Rotation double

Master SID – Algorithmique avancée &

120
Programmation 2021-2022
Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

10 20 60 85

5 (NOIR) 50 65 80 90

3 (NOIR)
40 55

Noeud inséré
Rotation simple
Master SID – Algorithmique avancée &
121
Programmation 2021-2022
Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

20 60 85

5 10 50 65 80 90

3 (NOIR) (NOIR)
40 55

Rotation simple
Master SID – Algorithmique avancée &
122
Programmation 2021-2022
Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

20 60 85

5 10 50 65 80 90

3 (NOIR) (NOIR)
40 55

Master SID – Algorithmique avancée &

123
Programmation 2021-2022
Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

5 20 60 85

3 10 50 65 80 90

(NOIR) (NOIR)
40 55

Rotation simple
Master SID – Algorithmique avancée &
124
Programmation 2021-2022
Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

5 20 60 85

3 10 50 65 80 90

(NOIR) (NOIR)
40 55

Rotation simple
Master SID – Algorithmique avancée &
125
Programmation 2021-2022
 Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

10 20 60 85

5 (NOIR) 50 65 80 90

(NOIR) 8 40 55

Noeud inséré
Rotation double
Master SID – Algorithmique avancée &
126
Programmation 2021-2022
 Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

20 60 85

5 10 50 65 80 90

8 (NOIR)
(NOIR) 40 55

Rotation double
Master SID – Algorithmique avancée &
127
Programmation 2021-2022
 Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

8 20 60 85

5 10 50 65 80 90

(NOIR)
(NOIR) 40 55

Master SID – Algorithmique avancée &

128
Programmation 2021-2022
 Insertion dans un arbre Rouge/Noir
(Exemple)
30

70
15

8 20 60 85

5 10 50 65 80 90

(NOIR)
(NOIR) 40 55

Master SID – Algorithmique avancée &

129
Programmation 2021-2022
 Deuxième cas : Si le frère du parent est
rouge

Noeud inséré
G P

S X G
P

D E A B C S
X C

D E
A B

Ceci cause un problème. Lequel?

Master SID – Algorithmique avancée &

130
Programmation 2021-2022
 Deuxième cas : Si le frère du parent est
rouge

Noeud inséré
G P

S X G
P

D E A B C S
X C

D E
A B

Ceci cause un problème. Lequel?

Si le parent de P est rouge, il faudra propager vers
le haut les ajustements, ce qui nous fait perdre l’avantage
sur AVL
Master SID – Algorithmique avancée &
131
Programmation 2021-2022
 Arbres Rouge-Noir (top-down)
• Pour éviter de devoir propager vers le haut
l’algorithme de rotation :
– on peut utiliser une approche top-down

• Idée:
– garantir que, lorsqu’on arrive au point d’insertion,
qu’il ne s’agisse pas d’un nœud rouge
– On pourra donc ajouter tout simplement un nœud
rouge, sans risque de violer la propriété 3

Master SID – Algorithmique avancée &

132
Programmation 2021-2022
Arbres Rouge-Noir (top-down) (suite)
• En descendant dans l’arbre, lorsqu’on rencontre un nœud qui a
deux fils rouges, on colorie ce nœud en rouge et en noir ses deux
fils :
X X

FG FD FG FD
• Ainsi, le nombre de nœuds noirs dans un chemin demeure inchangé
• Par contre, on peut se retrouver avec deux nœuds rouges
consécutifs, si le parent de X est rouge. Dans ce cas, il faudra
appliquer une rotation
• Ceci fonctionnera parce qu’on est sur que le nœud frère du parent
de X ne peut être que noir.
• Attention:
– la racine doit toujours demeurer noire

Master SID – Algorithmique avancée &

133
Programmation 2021-2022
 Arbres Rouge-Noir (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

10

Master SID – Algorithmique avancée &

134
Programmation 2021-2022
 Arbres Rouge-Noir (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

10

85

Master SID – Algorithmique avancée &

135
Programmation 2021-2022
 Arbres Rouge-Noir (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

10

85

15

Master SID – Algorithmique avancée &

136
Programmation 2021-2022
 Arbres Rouge-Noir (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 85

Rotation double

Master SID – Algorithmique avancée &

137
Programmation 2021-2022
 Arbres Rouge-Noir (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55
Attention: la racine ne change
pas de couleur
15

10 85

Ajustement durant le parcours

Master SID – Algorithmique avancée &

138
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 85

70

Master SID – Algorithmique avancée &

139
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 85

70

20

Master SID – Algorithmique avancée &

140
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

20 85

Rotation simple

Master SID – Algorithmique avancée &

141
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

20 85

Master SID – Algorithmique avancée &

142
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

20 85

Ajustement durant le parcours

Master SID – Algorithmique avancée &

143
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

20 85

60

Master SID – Algorithmique avancée &

144
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

20 85

60

30

Master SID – Algorithmique avancée &

145
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

30 85

20 60

Rotation double

Master SID – Algorithmique avancée &

146
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

30 85

20 60

Master SID – Algorithmique avancée &

147
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

30 85

20 60

Ajustement durant le parcours

Master SID – Algorithmique avancée &

148
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

10 70

30 85

20 60

50

Master SID – Algorithmique avancée &

149
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

70
15

10 20 60 85

50

Rotation double

Master SID – Algorithmique avancée &

150
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

70
15

10 20 60 85

50

Master SID – Algorithmique avancée &

151
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

70
15

10 20 60 85

50

Ajustement durant le parcours

Master SID – Algorithmique avancée &

152
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)

10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

70
15

10 20 60 85

50 65

Master SID – Algorithmique avancée &

153
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

50 65 80

Remarque: ces noeuds n’ont pas été

modifiés parce qu’il ne sont pas dans le
chemin parcouru
Master SID – Algorithmique avancée &
154
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

50 65 80 90

Master SID – Algorithmique avancée &

155
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

50 65 80 90

Master SID – Algorithmique avancée &

156
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

50 65 80 90

Ajustement durant le parcours

Master SID – Algorithmique avancée &

157
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

50 65 80 90

40

Master SID – Algorithmique avancée &

158
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)

10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

5
50 65 80 90

40

Master SID – Algorithmique avancée &

159
Programmation 2021-2022
 Arbres Rouge-Noir – (Exemple détaillé)
10 85 15 70 20 60 30 50 65 80 90 40 5 55

30

15 70

10 20 60 85

5
50 65 80 90

40 55

Master SID – Algorithmique avancée &

160
Programmation 2021-2022
Arbres Equilibrés
(B-arbres)
 B-arbres
Définition

Un arbre B d'ordre n est tel que :

– la racine a au moins 2 fils
– chaque nœud, autre que la racine, a entre n/2 et n fils
– tous les nœuds feuilles sont au même niveau

Master SID – Algorithmique avancée &

162
Programmation 2021-2022
 B-arbres
Illustration du mécanisme d'insertion (ordre = 3)

75

Construction Bottum-up ( équilibrage garanti )

Les éclatements peuvent être en cascade.

Master SID – Algorithmique avancée &
163
Programmation 2021-2022
 B-arbres
Illustration du mécanisme d'insertion (ordre = 3)

55

Master SID – Algorithmique avancée &

164
Programmation 2021-2022
 B-arbres
Illustration du mécanisme d'insertion (ordre = 3)

57

Master SID – Algorithmique avancée &

165
Programmation 2021-2022
 B-arbres
Illustration du mécanisme d'insertion (ordre = 3)

95

Master SID – Algorithmique avancée &

166
Programmation 2021-2022
 B-arbres
Illustration du mécanisme d'insertion (ordre = 3)

85

Master SID – Algorithmique avancée &

167
Programmation 2021-2022
 B-arbres
Illustration du mécanisme d'insertion (ordre = 3)

87

Master SID – Algorithmique avancée &

168
Programmation 2021-2022
 B-arbres
Utilisation d'un arbre B pour le stockage des données
• Un nœud de l'arbre = un bloc sur le disque.

• A un moment donné seul un bloc est ramené en mémoire.

• Nécessite des blocs de très grande taille ( ordre de 200).

• Deux façons de ranger les articles :

✓ (i) dans les nœuds avec les clés, ( Fichier = B-arbre )
✓ (ii) séparément, donc pointeur additionnel vers l'information.
( B-arbre = Index)

• Si le fichier est grand on préfère de loin utiliser (ii).

Master SID – Algorithmique avancée &

169
Programmation 2021-2022