Dr.

Omari Mohammed
Maître de Conférences Classe A
Université d’Adrar
Courriel : omarinmt@[Link]

SUPPORT DE COURS

Matière : Algorithmiques et Structures de Données 1

Niveau : 2ème Année Licence en Informatique
 ALGORITHMIQUES ET STRUCTURES DE
DONNEES 1

Programme :
1- Rappel sur les structures de données simples : tableaux, listes chaînées.
2- Structures de données séquentielles : piles, files, listes.
3- Structures de données en table : hachage.
4- Structures de données hiérarchiques : arbres.
5- Arbres binaires de recherche.
6- Arbres AVL.
7- Arbres bicolores.
8- B-arbres.
9- Les notations asymptotiques et la complexité d’un algorithme.
10- Preuve d’exactitude d’un algorithme
11- L’algorithme de tri par arbre (heapsort).

Ouvrages :
1- « Arbres, tables, algorithmes », Jacques Guyot, édition Chihab.
2- « Introduction à l’algorithmique », Thomas Corman, édition Dunod.
3- « Introduction to Algorithms », Cormen, Mc Graw Hill edition.
4- « Apprendre à programmer en Turbo C », Claude Delannoy, édition Chihab.

-1-
 Rappels sur les Tableaux et les Listes Chaînées

Dans la plupart des ordinateurs, la mémoire principale est formée d’une

suite de cellules de même taille, repérable à l’aide d’une adresse.
Pour représenter les structures de données en mémoire principale, on a
essentiellement deux modes de stockage : le stockage par tableau (stockage
contigu), et le stockage par pointeur ou liste chaînée (stockage dispersé).

I- Les Tableaux :
L’élément représentatif des structures statiques homogènes est le tableau
que l’on trouve dans la majorité des langages évolués de programmation.
L’allocation de l’espace mémoire d’un tableau est souvent statique.

I-1 Les Tableaux Monodimensionnels :

Le tableau monodimensionnel est la représentation informatique d’un
vecteur de l’espace. Il est constitué d’un ensemble d’élément accessible à l’aide
d’un indice. Cet accès direct est garanti en cas de lecture ou écriture.

#include <stdio.h>
#include <conio.h>

/* Variables Globales*/
int A[100] ;
int I, NombreMax ;

void main() {

/* Effacer l’écran*/
clrscr();

/* Lecture de la taille du tableau*/

printf(“Donner la taille du tableau : ”);
scanf(“%d”,&NombreMax);

/* Lecture des éléments du tableau*/

printf(“Donner les éléments du tableau : \n”);
for(I = 0 ; I <= NombreMax-1 ; I++)
scanf(“%d”,&A[I]);

-2-
 /* Affichage des éléments du tableau*/
printf(“Voici le contenu du tableau : \n”);

for(I = 0 ; I <= NombreMax-1 ; I++)

printf(”%d\n”, A[I]);

/* Pause avant quitter*/

getchar();
getchar();
}

I-2 Les Tableaux Multidimensionnels :

Un élément de tableau multidimensionnel est repéré à l’aide de plusieurs
indices au lieu d’un seul. Néanmoins, la représentation physique dans la
mémoire principale est presque la même.

Mémoire Mémoire

100 5 A[1] 100 5 A[1][1]

102 9 A[2] 102 9 A[1][2]
104 25 A[3] 104 25 A[2][1]
106 -10 A[4] 106 -10 A[2][2]

Représentation physique Représentation physique

d’un tableau monodimensionnel d’un tableau multidimensionnel

Alors quelque soit la dimension d’un tableau multidimensionnel, sa

représentation physique est toujours linéaire.

1 5 7 ………... 9
2 7 10 ………... 2
. . . . .
. . . . .
. . . . .

8 4 5 ………... 3

-3-
Elément Adresse
A[I] @A[1] + (I-1) * TailleElement
A[I][J] @A[1][1] +(I-1) * TaillePremiereDimension
+(J-1) * TailleElement

II- Les Listes Chaînées :

Lorsque le besoin de conserver la mémoire s’élève, il sera nécessaire
d’implémenter les structures de données en utilisant les pointeurs ou les listes
chaînées, où les données sont organisées séquentiellement. Le principe de base
de leur représentation est de suivre les évolutions de la structure, en lui
attribuant de la place en mémoire quand elle grandit, et en la récupérant quand
elle diminue. Ceci est réalisé par un principe d’allocation et libération
dynamique d’espace mémoire. Le TAS (HEAP) est la plage d’espace mémoire
réservée juste pour l’allocation dynamique.

Mémoire

Espace réservé pour les

variables, tableaux,
environnement des
procédures, … (statiques)

Espace réservé pour les

TAS listes chaînées,
environnement des
procédures, … (dynamique)

Dans les langages modernes, on dispose de deux procédures standard

d’acquisition et de libération d’espace mémoire : RESERVE et LIBERE.
La procédure RESERVE La procédure LIBERE
Langage Pascal new() dispose()
Langage C malloc() free()

-4-
II-1 Les Listes Simplement Chaînées (Unidirectionnelles) :
Une liste simplement chaînée est composée d'éléments distincts liés par
un simple pointeur. Chaque élément d'une liste simplement chaînée est formé de
deux parties:
- Un champ (ou plusieurs champs) contenant la donnée (ou l’information).
- Un pointeur vers l'élément suivant de la liste.
- L’ensemble {champ, pointeur} est appelé le maillon.
La liste est caractérisée par sa tête (l’adresse du premier maillon). Aussi,
le dernier maillon a la valeur NULL (Nil en Pascal) pour son pointeur. La queue
(l’adresse du dernier élément) est très utile pour accélérer l’opération
d’insertion.
Champ Pointeur

Tête Maillon NULL

Queue

#include <stdio.h>
#include <conio.h>

/* Definition de Type*/
typedef struct S_Element {
int info ;
struct S_Element* suivant ;
} Type_Element ;

/* Variables Globales*/
Type_Element* tete ;
Type_Element* element ;

void main() {

/* Effacer l’écran*/
clrscr();

/* Créer la liste {1, 2, 3}*/

/* 1 */
tete = malloc (sizeof (Type_Element)) ;
tete -> info = 1 ;
/* 2 */
element = tete ;
element -> suivant = malloc (sizeof (Type_Element)) ;
element = element -> suivant ;
element -> info = 2 ;
/* 3 */

-5-
 element -> suivant = malloc (sizeof (Type_Element)) ;
element = element -> suivant ;
element -> info = 3 ;
element -> suivant = NULL;

/* Affichage des éléments de la liste*/

printf(“Voici le contenu de la liste : \n”);

element = tete;
while (element != NULL) {
printf(”%d\n”, element -> info);
element = element -> suivant;
}

/* Pause avant quitter*/

getchar();
getchar();
}

II-2 Les Listes Doublement Chaînées (Bidirectionnelles) :

Les listes doublement chaînées sont constituées d'éléments comportant
trois champs:
- Un champ contenant la donnée.
- Un pointeur vers l'élément suivant de la liste.
- Un pointeur vers l'élément précédent de la liste.
Les listes doublement chaînées peuvent donc être parcourues dans les
deux sens. La liste est caractérisée par sa tête, aussi que par sa queue.
Champ

Tête Précèdent Suivant

II-3 Les Listes Circulaires :

Une liste circulaire peut être simplement ou doublement chaînée. Sa
particularité est de ne pas comporter de queue (NULL ne figure pas). Le dernier
élément de la liste pointe vers le premier. Un élément possède donc toujours un
suivant.
Champ Pointeur

Tête

-6-
 Les Piles, les Files, et les Listes

I. Les Piles :
Les piles sont des structures de données, où l'ajout et le retrait d'un
élément se fait toujours au sommet (en tête de liste).
Le plus souvent, les piles sont implantées sous forme de liste chaînée.
Néanmoins, une pile peut être implémentée à partir d'un tableau.
Une pile suit la règle LIFO (Last In, First Out): dernier entré, premier
sorti.
Sommet Sommet
Sommet Sommet

Sommet
12 3
7 7 7 7
5 5 5 5 5
Pile Vide Empiler(5) Empiler(7) Empiler(12) Dépiler() Empiler(3)

Terminologie particulière:
- l'extrémité où s'effectue l'ajout et le retrait s'appelle sommet.
- ajouter un élément à une pile se dit empiler (ou push).
- le fait de retirer un élément d'une pile et de récupérer son information
s'appelle dépiler (ou pop).

Exemple d’Utilisation des Piles:

Un programme A appelle une procédure B, qui appelle lui-même une
procédure C qui appelle une fonction D. La pile du programme va évoluer
comme suit: La Mémoire
1. lancement de A pile vide.
2. appel de B par A → l'état de A est empilé.
Etat de C
3. appel de C par B → l'état de B est empilé sur A.
4. appel de D par C → l'état de C est empilé sur B. Etat de B

5. Fin de D → dépilage de l'état de C à poursuite de C.

Etat de A
6. Fin de C → dépilage de l'état de B à poursuite de B.

-7-
 7. Fin de B dépilage de l'état de A à poursuite de A.
L’état d’une procédure représente l’espace mémoire utilisé par cette
procédure.

Représentation par une liste chaînée :

Sommet

Tête 4ème élément 3ème élément 2ème élément 1er élément

Les Primitives (Fonctions/Procédures de base) :

- Empiler()
- Dépiler()
- Vider() ou DépilerTout()
- Vide()
- Taille()

II. Les Files :

Une file ou queue est une structure de données où l'insertion d'un élément
se fait à une extrémité appelée queue et le retrait d'un élément se fait à une autre
extrémité appelée tête.
Une file est le plus souvent représentée par une liste chaînée. Une file suit
la règle FIFO (First In, First Out): premier entré, premier sorti.

Application :
Les files servent à traiter des données dans l'ordre où elles arrivent,
comme dans une file d'attente à un guichet où le premier arrivé est le premier
servi.

-8-
Représentation par une liste chaînée :
Une file doit être accessible à la fois par la tête pour retirer un élément et
par la queue pour ajouter un nouvel élément. La tête et la queue d'une file
correspondent à la tête et la queue de la liste chaînée qui l'implémente.

Tête 1er élément 2ème élément 3ème élément 4ème élément

Queue

Les Primitives :
- Enfiler()
- Défiler()
- Vider() ou DéfilerTout()
- Vide()
- Taille()

II. Les Listes :

Une liste est un ensemble d’élément de même type. Les listes sont
implémentées par des tableaux ou des listes chaînées, selon les besoins
d’implémentation.
Les polynômes correspondent à une liste de données ; chaque élément
est constitué de l’ensemble d’un coefficient et un degré.

Exemple : Soit le polynôme P(x) = X5 + 3X2 + X + 7.

Voici l’implémentation de la liste polynomiale par une liste chaînée :

1 5 3 2 1 1 7 0
Tête

-9-
III. Les Listes Non-Linéaires:
Une liste non linéaire est une structure de donnée dynamique que l’on
l’utilise beaucoup en informatique, surtout dans le domaine de l’intelligence
artificielle. Le langage LISP souvent utilise une base de donnée organisée sous
forme des listes non linéaires.
Spécification Fonctionnelle :
- ( ) représente la liste vide.
- A représente l’atome (ou l’élément) A
- (A) représente la liste à un élément A.
- (A B) représente la liste de deux éléments A et B
- (A (B (C) D) (E)) est une liste composée de trois éléments :
- l’atome A
- la liste à trois éléments (B (C) D)
- et la liste à un élément (E)
Remarque :
1- La liste non linéaire peut être composée d’autres listes ou/et des atomes.
2- Si la liste est composée des atomes seulement, alors c’est une liste
linéaire.

Représentation Physique :
1- Liste Vide : ()

Courant Suivant

Tête

2- La Liste (A)

Liste
Tête
A Atome

-10-
3- La Liste (A B)

Tête
A B

4- La Liste (A (B))

Tête
A

5- La Liste (A (B C))

Tête
A

B C

6- La Liste (A (B C) D)

Tête
A D

B C

Dans les exemples précédents, on observe que le pointeur Suivant pointe

toujours sur une liste. Par contre, le pointeur Courant pointe sur des listes et des
atomes. Afin d’enlever cette ambiguïté, un champ booléen est ajouté pour
distinguer entre l’atome et la liste :

-11-
 V F V
Tête
A D

V V

B C

La structure en C :
Typedef Struct S_Liste {
Struct S_Liste* Suivant ;
Struct S_Liste* Courant_Liste ;
Char Courant_Atome ;
Int Type_Courant ; /* 1 : Vrai, 0 : Faux*/
} Liste ;

-12-
 Structures de données en table : Hachage

Les opérations fondamentales sur une base de données sont : l’insertion, la recherche,
et la suppression. On cherche souvent à trouver des structures de données et des méthodes
d’accès plus efficaces afin d’améliorer le temps requis par ces opérations.
Soit un tableau des noms triés en ordre alphabétique comme suit :

Ali Bachir Celia Dalila Emad Farid George Hassan

La recherche dichotomique binaire est faite sur plusieurs étapes, sauf si le nom
cherché est au milieu. Généralement, si le tableau des données est de taille n, alors le pire des
cas correspond à lg2(n) étapes de recherche pour accéder aux éléments situés aux extrémités.

Solution : Créer une fonction h qui remplace directement chaque mot par son indice
correspondant : h(‘Ali’) = 0 ; h(‘Bachir’) = 1 ; …
La fonction h est appelée une fonction de hachage (ou de dispersion).

Définition : Une fonction de hachage h est une fonction d’un ensemble de clés C dans un
ensemble (d’indices) {0, 1, …, m-1}. Une bonne fonction de hachage doit être calculable très
rapidement et doit distribuer uniformément les clés sur les indices de hachage.

Exemple1 :
h(MOT) = Ord(premier caractère de MOT) – Ord(‘A’) ; où Ord est la fonction de
conversion d’un caractère à son code ASCII.

Exemple 2 :
Si on désire de stocker les entiers 1, 3, 4, 6, 8, 11, on peut choisir la méthode de la
division suivante :
h(k) = k mod m, où mod est l’opération du reste de division entière, et m = 6.
Dans ce cas tous les éléments sont rangés dans un tableau de 6 éléments : h(6) = 0,
h(1) = 1, h(8) = 2, h(3) = 3, h(4) = 4, h(11) = 5.

6 1 8 3 4 11

Avantages : - Accès directe (rapide).

Inconvénients : - Impossible de stocker deux clés si elles ont la même valeur hachée ; h(‘Ali’)
= h(‘Ahmed’) ; h(5) = h(11). On appelle cette situation une collision. La collision peut
-13-
facilement être évitée si la fonction de hachage est bijective. Mais cette méthode conduit à
une énorme perte de l’espace mémoire si le nombre de clés à stocker est très inférieur au
domaine des clés.

Exemple : Stocker les entiers 2, 4, 10, 18, et 20 dans un tableau en utilisant la fonction de
hachage bijective h(x) = (x/2) -1.

2 4 10 18 20

Pour remédier à ce problème, deux solutions ont été proposées : l’adressage fermé, et
l’adressage ouvert.

1- L’Adressage Fermé (avec Chaînage):

Au lieu de sauvegarder les clés directement dans les cellules du tableau, en associe une
liste chaînée pour chaque cellule, chacune contenant la classe des clés de même valeur
hachée.

Exemple :
Insérer successivement les clés 10, 22, 31, 4, 15, 28, 17, 88, et 59 dans une table de
hachage de taille m = 11 gérée en adresse fermé, en utilisant la fonction uniforme de
hachage : h(k) = k mod m.

0 22 88
1
2
3
4 4 15 59
5
6 28 17
7
8
9 31
10 10

-14-
Avantages : - Un nombre limité de données (têtes des listes) est sauvegardés dans la partie
statique de la mémoire ; le reste est sauvegardé dans le tas.
- Collision éliminée.
Inconvénients : - Les clés ne sont pas distribuées uniformément. On peut donc avoir une
grande accumulation de données dans des zones limitées !!!
- L’accès à un élément dans une liste chaînée est coûteux.

2- L’Adressage Ouvert :
2-1 L’Adressage Ouvert Simple:
Dans ce mode d’adressage, tous les éléments sont conservés dans la table de hachage.
Chaque entrée de la table contient soit NULL, soit un élément. En supprimant les listes
chaînées, on libère de la mémoire, ce qui permet d’augmenter la taille de la table et limiter les
collisions.
Lorsqu’on définie la fonction de hachage h, chaque clé k est associé à une permutation
H(k) = {h(k, 0), h(k, 1), …, h(k, m-1)} de {0, 1, …, m-1}. Cette permutation est la suite des
indices des cellules testées lors d’une recherche. Alors, on examine (sonde) successivement
les cellules de la table jusqu’à en trouver une vide.

Remarque : En adressage ouvert, la table peut se remplir complètement, dans ce cas, il ne sera
plus possible d’y insérer des éléments.

Exemple : Même exemple précédent avec la fonction de hachage h(k, i) = (k + i) mod m.

0 22 2- h(22, 0) = 0
1 88 8- h(88, 0) = 0, h(88, 1) = 1
2
3
4 4 4- h(4, 0) = 4
5 15 5- h(15, 0) = 4, h(15, 1) = 5
6 28 6- h(28, 0) = 6
7 17 7- h(17, 0) = 6, h(17, 1) = 7
8 59 9- h(59, 0) = 4, h(59, 1) = 5, h(59, 2) = 6, h(59, 3) = 7, h(59, 4) = 8
9 31 3- h(31, 0) = 9
10 10 1- h(10, 0) = 10

-15-
2-2 L’Adressage Ouvert Double : On observe que dans le mode d’adressage simple, la suite
des essais (permutation) est toujours séquentielle selon l’indice de la table. En fait, les valeurs
h(k, i), h(k, i+1), h(k, i+2), … consiste à une suite numérique non-aléatoire. Ce qui fait que la
recherche dans une table de hachage est loin d’être uniforme.
En mode d’adressage double, on ajoute une deuxième fonction d’hachage afin
d’améliorer la distribution des permutations H(k).

Exemple : Même exemple précédent avec la fonction de hachage h(k, i) =(k + ih2(k)) mod m,
tel que h2(k) = k mod (m-1)

0 22 2- h(22, 0) = 0
1
2 17 7- h(17, 0) = 6, h(17, 1) = 2
3 15 5- h(15, 0) = 4, h(15, 1) = 9, h(15, 2) = 3
4 4 4- h(4, 0) = 4
5
6 28 6- h(28, 0) = 6
7 59 9- h(59, 0) = 4, h(59, 1) = 2, h(59, 2) = 0, h(59, 3) = 9, h(59, 4) = 7
8 88 8- h(88, 0) = 0, h(88, 1) = 8
9 31 3- h(31, 0) = 9
10 10 1- h(10, 0) = 10

- Avantages : Accès aléatoire aux cellules.

- Inconvénients : Pas de garantie d’insertion, même s’il y a une case vide (exemple : on peut
pas insérer la valeur 20 dans la table précédente).
2-3 L’Adressage Ouvert Quadratique : L’adressage double ne nous garantie aucune seuil
maximale à propos du nombre d’essais qu’il faut balayer pour la recherche d’une clé. Pour
cela, l’adressage quadratique a été proposé comme suit :
h(k, i) = (k + i2) mod m
Dans ce mode, si m est un nombre premier, la suite d’essais successifs balaie au plus
la moitié du tableau. Ou bien, on à au moins un nombre d’essais égale à la moitié des cellules
existantes.

Preuve :
Supposons que les essais i et j (i < j et i,j∈{1, m-1}) correspondent à la même cellule
du tableau. Nous avons alors h(k, i) = h(k, j).
Donc on a h(k, j) - h(k, i) = 0.
Ce qui fait que (k + j2) - (k + i2) = 0 mod m
-16-
Alors j2 - i2 = 0 mod m, et donc (j+i)(j-i) = 0 mod m
Comme m est un nombre premier, alors soit (j+i) = 0 mod m ou bien (j-i) = 0 mod m
Si (j-i) = 0 mod m, alors j∈{i, i+m, i+2m, …}. Contradiction puisque j≠i et j∈{1, m-1}.
Il reste que (j+i) = 0 mod m, alors les seuls couples (i, j) possibles sont :
- Si m est pair, alors m = 2n : (i, j) ∈{(1, m-1), (2, m-2), …, (n-1, n+1)}
- Si m est impair, alors m = 2n+1 : (i, j) ∈{(1, m-1), (2, m-2), …, (n, n+1)}
Dans les deux cas précédents, le nombre de possibilités est inférieur ou égale à n, ou
m/2. Ca veut dire que, dans le pire des cas, après le nème essai on tombe sûrement sur une
cellule déjà visitée.

Exemple : Même exemple précédent avec la fonction de hachage quadratique

h(k, i) = (k + i2) mod m

0 22 2- h(22, 0) = 0
1 88 8- h(88, 0) = 0, h(88, 1) = 1
2
3
4 4 4- h(4, 0) = 4
5 15 5- h(15, 0) = 4, h(15, 1) = 5
6 28 6- h(28, 0) = 6
7 17 7- h(17, 0) = 6, h(17, 1) = 7
8 59 9- h(59, 0) = 4, h(59, 1) = 5, h(59, 2) = 8
9 31 3- h(31, 0) = 9
10 10 1- h(10, 0) = 10

-17-
 Les Arbres

L’arbre est une structure de données fondamentale en informatique. Elle est utilisée
pour représenter des données en hiérarchie. Le but d’étudier les arbres est de savoir comment
peut on améliorer la représentation et l’accès aux différentes données. Les arbres sont utilisés
dans des différents domaines, comme la compilation, les graphes, et l’intelligence artificielle.

Exemple 1 : Représentation Administratives des daïras et wilayas :

Algérie

Adrar Chlef ………. Alger ………………………. Rélizane

Timimoun Reggane Aoulef ……….

Exemple 2 : Représentation d’une expression arithmétique :

A – (B + C * (D – E)) * F

A *

+ F

B *

C –

D E

-18-
Exemple 3 : Arbre de décision d’un tri de trois éléments a, b, et c :

a>b a≤b

a>c b>c
a≤c b≤c
c>b c≤b a>c a≤c

(a, c, b) (a, b, c) (c, a, b) (b, a, c) (b, c, a) (c, b, a)

1. Définition : Un arbre binaire est composé d’une racine (ou nœud) et de deux sous-arbres
binaires (gauche et droit). Un arbre binaire peut aussi être vide.

2. Primitives : La structure arbre binaire doit assurer les primitives suivantes :

- Insérer()
- Supprimer()
- Rechercher()
- Taille()
- Vide()

3. Représentation Physique : Un arbre binaire est facilement représenté par une liste
chaînée. Néanmoins, la représentation tabulaire est souvent utilisée pour les arbres de tri.

Exemple 4 :

Tête 2

5 8

1 4 10

7 12

-19-
4. Parcours d’un Arbre : On appelle parcours d’un arbre binaire, toute méthode permettant
l’accès une seule fois aux nœuds de cette arbre.

4.1 Le Parcours en Pré-ordre (Prefix en anglais) :

Dans ce mode, on inspecte d’abord la racine, puis le sous-arbre gauche, et enfin le
sous-arbre droit (RGD). Ce type de parcours est caractérisé par le balayage en profondeur :
vertical de haut en bas.
Exemple : (L’arbre de l’exemple 4)
RGD : 2 5 1 4 7 8 10 12
2 (5 (1) (4 (7) ())) (8 () (10 (12) ()))

4.2 Le Parcours en Post-ordre (Postfix en anglais) :

Dans ce mode, on inspecte d’abord le sous-arbre gauche, puis le sous-arbre droit, et
enfin la racine (GDR). Ce type de parcours est caractérisé par le balayage en profondeur :
vertical de bas en haut.

Exemple : (L’arbre de l’exemple 4)

GDR : 1 7 4 5 12 10 8 2
((1) ((7) () 4) 5) (() ((12) () 10) 8) 2

4.3 Le Parcours en Ordre (Infix en anglais) :

Dans ce mode, on inspecte d’abord le sous-arbre gauche, puis la racine, et enfin le
sous-arbre droit (GRD). Ce type de parcours est caractérisé par le balayage en largeur
(horizontal).

Exemple : (L’arbre de l’exemple 4)

GRD : 1 5 7 4 2 8 12 10
((1) 5 ((7) 4 ())) 2 (() 8 ((12) 10 ()))

-20-
 Les Arbres Binaires de Recherche

Un arbre binaire de recherche est un arbre ordonné horizontalement (de gauche à

droite) ; i.e., la clé de tout nœud non feuille est supérieur à toutes celles de son sous-arbre
gauche, et inférieure à toutes celles de son sous-arbre droit.
Exemple :

13

9 45

5 11 50

7 10 12 48 52

Parcours Pre-Ordre : 13 (9 (5 () (7)) (11 (10) (12))) (45 () (50 (48) (52)))
Parcours Post-Ordre : ((() (7) 5) ((10) (12) 11) 9) (() ((48) (52) 50) 45) 13
Parcours en-Ordre : ((() 5 (7)) 9 ((10) 11 (12))) 13 (() 45 ((48) 50 (52)))

1- Recherche d’un élément :

Puisque l’arbre binaire de recherche est ordonné horizontalement, une simple
recherche dichotomique est déclanché pour trouver une clé quelconque :
1- Tester si la clé de la racine de l’arbre égale à la clé recherchée.
2- Sinon, chercher récursivement dans le sous-arbre gauche si la clé est inférieure à la
racine, sinon dans le sous-arbre droit.
Exemple :
Chercher la clé 12 : Chercher la clé 51 :
12 ≤ 13 51 > 13
12 > 9 51 > 45
12 > 11 51 > 50
12 = 12 (clé trouvée) 51 ≠ 52 (clé non trouvée)

2- Insertion d’un élément :

Le principe de l’insertion d’un élément inexistant dans un arbre binaire de recherche
(ABR) est basé sur la recherche de cet élément. Il est évident qu’on va aboutir à une feuille
(élément inexistant). Alors le nouvel élément est accroché à la dernière feuille ; i.e., à gauche
si inférieur, à droite si supérieur.

-21-
Exemple : Insertion de 3 et 6.

8 8

4 10 4 10

5 9 13 3 5 9 13

3- Suppression d’un élément :

L’opération de suppression d’un élément est effectuée selon 3 cas :
- Si l’élément est une feuille alors on le supprime simplement.
- Si l’élément a un seul descendant alors on le remplace par ce descendant.
- Si l’élément a deux descendants (ou bien deux sous-arbres), on le remplace, au choix,
soit par l’élément le plus à droite (le plus grand) de son sous-arbre gauche, soit par
l’élément le plus à gauche (le plus petit) de son sous-arbre droit.

Exemple : Suppression de 16 et 7.

16

7 18

4 9 24

2 6 8 10

10

8 18

4 9 24

2 6

-22-
4- Modification d’un élément :
Il n’y pas de règle spécifique pour la modification. Une simple implémentation
consiste à supprimer puis insérer la nouvelle valeur de l’élément.

5- Stockage optimal d’un arbre binaire de recherche:

Pour améliorer l’accès aux éléments de l’arbre, on les stocke dans un tableau comme
suit : si un élément est stocké à l’indice i, alors ses fils gauche et droit sont respectivement en
position 2*i et 2*i+1. Si un fils n’existe pas, sa place est perdue (restera vide).

16

7 18

4 9 24

2 6 8 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 7 18 4 9 24 2 6 8 10

16 (7 (4 (2) (6)) (9 (8) (10))) (18 () (24))

Dans le cas où l’arbre binaire est complet, ce stockage est compact et optimal. Notons
qu’avec cette représentation, un simple parcours séquentiel du tableau correspond à un
parcours de l’arbre par niveau, appelé aussi parcours en largeur.

-23-
 Les Arbres AVL
Lorsque plusieurs opérations d’insertion et de suppression sont effectuées sur un arbre
binaire de recherche, l’arbre binaire risque de se dégénérer ; i.e., l’arbre peut se déséquilibrer
et se transformer à une liste linéaire :

10

5 13

4 7 11 15

après la suppression de 4, 5, 7 et 11 :

10

13

15

Ceci enlève tout intérêt de la structure arborescence car on est ramené à une recherche
séquentielle !!!
La solution de ce problème serait de réorganiser l’arbre après chaque modification
(insertion ou suppression)

1- Critère d’équilibre parfait :

Un arbre binaire est parfaitement équilibré si pour tout nœud, la différence entre le
nombre de noeuds du sous-arbre gauche SAG et ce du sous-arbre droit SAD égale à 0 ou 1
(maximum 1). Le problème c’est que ce critère est très coûteux à réaliser.

2- Arbres partiellement équilibrés :

Un arbre partiellement équilibré est un arbre caractérisé par l’équilibre de la hauteur
des sous-arbres gauche et droit.

-24-
 Pour cela, on ajoute l’information BALANCE pour chaque nœud, où sa valeur est
inclue dans {-1, 0, 1}.
typedef struct S_Noeud {
int info ;
struct S_Noeud* gauche ;
struct S_Noeud* droit ;
int balance; /* -1, 0, ou 1*/
} Noeud;
Le facteur d’équilibre BALANCE a le sens suivant :
- Si BALANCE = -1, alors la hauteur du SAG est supérieure à celle du SAD.
- Si BALANCE = 0, alors la hauteur du SAG égale à celle du SAD.
- Si BALANCE = 1, alors la hauteur du SAG est inférieure à celle du SAD.

3- Les Arbres AVL : Ils sont des arbres BR à critère d’équilibre, proposés par G.M.
Andelson-Velski et E.M. Landis en 1962. Dans un arbre AVL, pour tous les nœuds, la
différence entre les hauteurs des sous-arbres gauche et droit égale à 1 au maximum.

4- Insertion dans un arbre AVL :

Dans tout ce qui suit, on va étudier la modification du SAG seulement. Lorsqu’un
nœud est inséré dans un arbre AVL, 4 cas majeurs se produisent :

1er cas : Le SAG n’a pas grandi. Dans ce cas, l’équilibre est inchangé. Aucune action de
rééquilibrage n’est exigée.

-25-
2ème cas : Le SAG a grandi alors que le SAD était maximal (balance = 1). Dans ce cas,
l’équilibre est amélioré (balance = 0). Aucune action de rééquilibrage n’est exigée.

SAG SAD SAG SAD

3ème cas : Le SAG a grandi alors que le SAG et le SAD avaient la même hauteur (balance =
0). Dans ce cas, le SAG atteint la hauteur maximale (balance = -1). Aucune action de
rééquilibrage n’est exigée.

SAG SAD SAG SAD

4ème cas : Le SAG a grandi alors qu’il était déjà maximal (balance = -1).

SAD SAD
SAG SAG

Dans ce cas, le critère d’équilibre AVL n’est plus respecté. Alors, il faut réorganiser
l’arbre selon ces deux cas :
Cas gauche-gauche : c’est le cas où le sous-arbre gauche du SAG a grandi :

2 1
1
2

C
B A B C
A

Dans ce cas, une simple rotation à droite des nœuds 1 et 2 est effectuée. La racine du
SAG devient la racine de l’arbre en question.
-26-
Cas gauche-droite : c’est le cas où le sous-arbre droit du SAG a grandi :

3 2
1 1 3
2
C
A A C
B1 B2
B1 B2

Dans ce cas, cet arbre est divisé lui même en sous-arbre gauche et droit, et sa racine
devient la racine de l’arbre en question.
Remarque : Cette méthode est valable quelque soit la BALANCE entre B1 et B2 (-1, 0, ou
1).

4- Retrait dans un arbre AVL :

Lorsqu’un nœud est supprimé d’un arbre AVL, 4 cas majeurs se produisent :
1er cas : Le SAG n’a pas diminué à cause du retrait (balance n’a pas changé). Dans ce cas,
l’équilibre est inchangé. Aucune action de rééquilibrage n’est exigée.
2ème cas : Le SAG a diminué alors qu’il était maximal (balance = -1). Dans ce cas, l’équilibre
est amélioré (balance = 0). Aucune action de rééquilibrage n’est exigée.

SAG SAD SAG SAD

3ème cas : Le SAG a diminué alors qu’il avait la même hauteur que le SAD (balance = 0).
Dans ce cas, le SAG atteint la hauteur minimale (balance = 1). Aucune action de rééquilibrage
n’est exigée.

SAG SAD SAG SAD

-27-
4ème cas : Le SAG a diminué alors qu’il était minimal (balance = 1).

SAG SAG
SAD SAD

Dans ce cas, le critère d’équilibre AVL n’est plus respecté. Alors, il faut réorganiser
l’arbre selon ces deux cas :

Cas droite-droite : c’est le cas où le sous-arbre doit du SAD à une hauteur supérieur ou égale à
celle de son sous-arbre gauche:

1 2
2 1

A
B A B C
C

Dans ce cas, une simple rotation à gauche des nœuds 1 et 2 est effectuée. La racine du
SAD devient la racine de l’arbre en question.

Cas droite-gauche : c’est le cas où le sous-arbre gauche du SAD à une hauteur supérieur à
celle de son sous-arbre gauche:

1 2
3
1 3
2
A
C A C
B1 B2
B1 B2

Dans ce cas, cet arbre est divisé lui même en sous-arbre gauche et droit, et sa racine
devient la racine de l’arbre en question.
Remarque : Cette méthode est valable quelque soit la BALANCE entre B1 et B2 (-1, 0, ou
1).

-28-
 Les Arbres B et BB

Définition 1: Un arbre B est un arbre N-aire (d’ordre N) qui satisfait les conditions suivantes :
1- Critère d’ordre : Ordonné horizontalement.
2- Critère d’équilibre : Chaque noeud est constitué de N jusqu’à 2N éléments, et que
toutes les feuilles ont la même profondeur.
3- Seule la racine peut avoir moins de N élément.

Exemple : Un arbre B d’ordre 2

25

10 20 30 40

2 5 7 8 22 24 26 27 29 42 45 47 50

13 14 15 18 32 35 38

Représentation physique :
Un arbre B d’ordre N peut être facilement représenté par une liste chaînée non-
linéaire :
typedef struct S_NoeudB {
struct S_Noeud* fils[2*N + 1] ;
int info[2*N];
} NoeudB;
Donc, fils[i] pointe sur la racine du sous-arbre dont ses éléments sont inclues entre
info[i-1] et info[i].

Exemple d’utilisation des arbres B : Si la mémoire est paginée (partagée en pages), il est
utile de charger du disque juste les informations qu’on a besoin momentanément. Dans ce cas,
l’arbre B nous aide à charger les pages dont les informations qu’ils portent sont dans un
intervalle désigné par une feuille (entre 13 et 18 pour le 2ème noeud).

Remarque : On cas d’insertion ou de retrait, une réorganisation de l’arbre B est nécessaire si

une des trois conditions est non respectée.
-29-
Définition 2: Un arbre BB (proposé par R. Bayer) est un arbre B d’ordre 1. Alors, chaque
nœud possède 1 ou 2 éléments.
Implémentation : Un arbre BB peut être implémenté en deux manières :

25 25

10 20 30 10 20 30

Représentation Père-Fils Représentation Père-Fils-Frère

La représentation père-fils est plus proche de l’implémentation physique. Par contre, la

représentation père-fils-frère nous aide à réorganiser (logiquement) l’arbre en cas d’insertion
ou de suppression.
Remarque : - Un nœud peut avoir au plus soit deux fils soit un fils et un frère.
- En cas de manque d’un fils ou d’un frère, un nœud est considéré d’avoir une
feuille de profondeur zéro.

Représentation physique :
Un arbre BB peut être facilement représenté par une liste chaînée non-linéaire :
typedef struct S_NoeudBB {
int info;
struct S_Noeud* gauche;
struct S_Noeud* droit;
int TypeDroit; /*0 : Fils, 1: Frère*/
} NoeudBB;
dans un arbre BB : Lorsqu’un nouvel élément est inséré dans un arbre BB en lui
déséquilibrant le niveau de ses feuilles, 2 cas se produisent pour chaque type d’insertion (à
gauche (SAG) ou à droite (SAD)):
A- Insertion au SAD
1er Cas : La racine a le SAD comme fils :

-30-
 A A B
B

SAG SAD SAG SAD

Dans ce cas, le SAD devient le frère de la racine, et l’arbre n’a pas grandi.

2ème Cas : La racine a le SAD comme frère :

A B A B
C

SAG SAD SAG B1

B2

B
A B C A C

SAG B1 B2 SAG B1 B2

Dans ce cas, le SAD est devisé et distribué à gauche et à droite et sa racine devient la
racine de l’arbre BB. On note ici que l’arbre a grandi.

-31-
B- Insertion au SAG
1er Cas : La racine a le SAD comme fils :

B A B
A

SAG
SAG SAD SAD

- Si A a un fils droit:

A B A B

A1 A2 SAD A1 A2 SAD

- Si A a un frere droit : C

A C B A B

A1 C1 C2 SAD A1 C1 C2 SAD

Dans ce cas, le SAG devisé est distribué à gauche et à droite et la racine devient son
frère.

-32-
2ème Cas : La racine a le SAD comme frère :

B
B C A C
A

SAG
SAG SAD SAD

Dans ce cas, le SAD devient le fils de la racine, et l’arbre est augmenté.

Suppression d’un arbre BB : Suivant la même philosophie de l’insertion, la suppression

peut aussi être divisée en deux cas : suppression au SAG et suppression au SAD. (Cette
section reste comme travail à domicile).

-33-
 Les Arbres Bicolores (Rouge et Noir)

On a vu que les arbres AVL et les arbres B sont des structures de données à critère
d’équilibre. L’inconvénient que ses structures possèdent c’est qu’ils nécessitent plusieurs
opérations de regroupement ou d’éclatement après une opération d’insertion ou de
suppression. Aussi, la hauteur n’est pas vraiment maintenue au niveau des feuilles.
La structure de données d’arbre rouge et noir nécessite des opérations minimales après
une mise à jour pour conserver sa propriété d’arbre équilibré.

Définition : Un arbre rouge et noir est un arbre binaire de recherche où chaque nœud est de
couleur rouge ou noire de telle sorte que :

1. Les feuilles sont nulles et noires,

2. Les fils d'un nœud rouge sont noirs, (ou bien le père d’un nœud rouge est toujours
noir)
3. Toutes les feuilles ont la même hauteur noire : Le nombre des nœuds noirs (internes)
dans un chemin de la racine à n’importe quelle feuille est identique.

Exemple : Un arbre noir avec hauteur noire égale à 3.

17

7 23

21 31
3 11

18 22 29

19

Propriétés :
- Le nombre des feuilles égale au nombre des nœuds internes plus 1.
- Le nombre des nœuds noirs internes est majoritaire (supérieur aux noeuds rouges).
Autrement dit, l’hauteur noire > l’hauteur/2.
- On ne peut pas avoir deux nœuds rouges successifs le long d’un chemin de la racine
vers une feuille.

-34-
Opération de Rotation et de Changement de Couleur : Afin de rééquilibrer un arbre
bicolore lors d’une mise à jour, on commence d’abord par étudier les propriétés des
opérations suivantes :
1 – Factorisation /distribution de la couleur noire :

Factorisation
P P

X Y
Distribution X Y

Dans ces deux cas l’hauteur noire n’est pas changée.

2 – Rotation à gauche et à droite :

P
Rotation à droite X

X P

Y
Rotation à gauche X1
X1 X2 X2 Y

Insertion dans un arbre rouge-noir :

L’insertion d’une clé X dans un arbre bicolore est identique à celle d’un ABR. Alors,
une feuille nulle sera éliminée et remplacée par X, et deux nouvelles feuilles nulles seront
crées et accrochées à X. La couleur de X sera rouge pour que la hauteur noire de l’arbre ne se
modifie pas.

30 30
Insertion de 31

29 29 31

Si le Père est noir, toutes les conditions d’équilibre de l’arbre bicolore sont respectées.
Si le Père est Rouge, la deuxième condition d’équilibre n’est plus respectée. Alors on
distingue 4 cas :
1er Cas : Le père P est la racine : Alors on change la couleur de P en noir. C’est le seul cas où
la hauteur noire est incrémentée.

-35-
 P P

X X

Y Y
X1 X2 X1 X2

2ème Cas : Le frère de P (F) est rouge : Dans ce cas, le grand père G doit être noir. Alors on
distribue la couleur noire vers P et F.

G G

P F P F

X X

F1 F2 F1 F2
Y Y
X1 X2 X1 X2

C’est le seul cas où on doit vérifier plus haut si la deuxième condition d’équilibre est
encore vérifiée. Dans le pire des cas, on effectue lg2(n) opérations de changement de couleurs.

3ème Cas : Le frère de P (F) est noir : Si X est le fils gauche de P, alors on effectue une rotation
à droite entre P et G en changeant leurs couleurs.

Rotation à droite
G P

P F X G

X
F
F1 F2 X1 X2
Y
Y
X1 X2
F1 F2

On note que les sous arbres X1, X2 et Y ont au moins un nœud noir pour faire de
l’équilibre noir avec le sous arbre enraciné à F.

-36-
Si X est le fils droit de P, alors on effectue d’abord une rotation à gauche entre X et P (pour
arriver au même cas précédent), puis une rotation à droite entre X et G en changeant leurs
couleurs.

G Rotation à gauche G

P F X F

X P

F1 F2 F1 F2
X2
Y
X1 X2 Y X1

X
Rotation à droite

P G

F
Y X1

X2
F1 F2

-37-
Suppression dans un arbre rouge-noir :
La suppression d’une clé X d’un arbre bicolore est identique à celle d’un ABR. Alors,
Dans le cas ou le nœud X a plusieurs descendants, on sélectionne un nœud du SAG ou du
SAD contenant la clé Y pour le supprimer. Si ce nœud ne possède que des feuilles
descendantes, alors il est simplement remplacé par une feuille.
La suppression du nœud Y ne pose aucun problème vis-à-vis l’équilibre noir si ce
nœud est rouge. Dans ce cas, la clé X est remplacée par Y. Par contre, si le nœud à supprimer
(celui de Y) est noir, on doit effectuer des opérations de rééquilibrage afin de régler l’hauteur
noire de l’arbre.

30 30 30
Suppression de 40

20 40 20 55 20 55

35 55 35 35

30 Suppression de 40 30 30

20 20 20
40 55 55

35 55 35 35 +

Donc, pour garder l’équilibre noire, on supprime le nœud (Y) mais on garde sa couleur
noire. Cette couleur est ajoutée à la couleur du nœud remplaçant (R) comme suit:
- Si la couleur du nœud remplaçant est rouge, alors elle devient noire.
- Si la couleur du nœud remplaçant est noire, alors elle devient doublement noire.
Alors, on doit rééquilibrer l’arbre juste dans le cas d’un nœud doublement noir. Soit R
le nœud doublement noir.
Cas 1 : Le nœud R est la racine.

R + R

A B A B

-38-
 Dans ce cas, la racine devient simplement noire. C’est le seul cas ou la hauteur noire
est diminuée.
Cas 2 : Le frère F de R est noir. Par symétrie, on suppose que R est le fils gauche de P. Alors,
on distingue 3 cas :
Cas 2-1 : F a deux fils noirs G et D. Dans ce cas, on factorise la couleur noire de R+ et F vers
P quelque soit sa couleur. Si P est rouge il devient noir, sinon doublement noir.

P P +

R + F R F

G D G D

C’est le seul cas où on doit vérifier plus haut si la deuxième condition d’équilibre est
encore vérifiée (pas de nœud doublement noir). Dans le pire des cas, on effectue lg2(n)
opérations de changement de couleurs.

Cas 2-2 : F a le fils droit D rouge. Dans ce cas, on effectue une rotation à gauche entre F et P
en changeant leurs couleurs, quelque soit la couleur de P. D reçoit la couleur noire.

P F

Rotation à gauche
P D
R + F

G D R G
D1 D2
R1 R2

G1 G2 D1 D2 R1 R2 G1 G2

On note que les sous arbres enracinés à D1 et D2 ont au moins un nœud noir pour faire
l’équilibre avec le nœud noir G.

-39-
Cas 2-3 : F a le fils gauche G rouge. Dans ce cas, on effectue d’abord une rotation à droite
entre G et F en changeant leurs couleurs (pour arriver au même cas précédent), puis une
rotation à gauche entre G et P en changeant aussi leurs couleurs, quelque soit la couleur de P.

P P

Rotation à droite
R + F R + G

F
G D

R1 R2 R1 R2 G1
D

G1 G2 D1 D2 G2
G D1 D2
Rotation à gauche
P F

R D

G1 G2

R1 R2 D1 D2

Cas 3 : Le frère F de R est rouge. Par symétrie, on suppose que R est le fils gauche de P. Alors
on effectue une rotation à gauche entre F et P en changeant leurs couleurs, pour y arriver à un
cas similaire au cas 2.

P F

Rotation à gauche
F P D
R +

G D R + G
D1 D2
R1 R2

G1 G2 D1 D2 R1 R2 G1 G2

-40-
 Les Notations Asymptotiques

Le temps d'exécution d'un algorithme ‘A’ pouvait être exprimé comme une fonction
T : N→R+, telle que T(n) représente le temps maximal que prend A sur une entrée de
longueur n. Si nous voulons pouvoir comparer les temps d'exécution de plusieurs algorithmes,
il est d'abord nécessaire de savoir comparer les fonctions entre elles.

1- La Notation « Grand O » :
La notation grand O sert à exprimer le fait que l'ordre de grandeur d'une fonction est
inférieur ou égal à une autre.
Soit f : N→R+ une fonction positive. On défini l'ordre O de f(n) comme l'ensemble:
O(f) = {g : N→R+ / (∃c > 0)(∃n0 ≥ 0)(∀n ≥ n0) : g(n) ≤ cf(n)}, c ∈ R, n0∈N.
On écrit g ∈ O(f) (O(f) est un ensemble) ou g = O(f) (O(f) est un ordre). On dit que
f(n) est une borne asymptotique supérieure de g(n).

c.f(n)

g(n)

0 1 2 n0

Pour montrer qu'une fonction g(n) est dans l'ordre (inférieur) d'une autre fonction f(n),
on doit donc trouver deux constantes c et n0 telles que g(n) ≤ cf(n) est vrai sauf, possiblement,
pour des petites valeurs inférieures à n0.
Exemples :
1 - n + 1 = O(n) ?
On sait que n + 1 < 2n pour n ≥ 1. Alors il existe c = 2 et n0 = 1 tel que :
∀n ≥ n0, n + 1 ≤ cn. Alors n + 1 = O(n).
2- n = O(n +1) ?
On sait que n < n + 1 pour n ≥ 0. Alors il existe c = 1 et n0 = 0 tel que :
∀n ≥ n0, n ≤ c(n + 1). Alors n = O(n + 1).

-41-
3- n = O(n2) ?
On sait que n < n2 pour n ≥ 2. Alors il existe c = 1 et n0 = 2 tel que :
∀n ≥ n0, n ≤ cn2. Alors n = O(n2).
4- n2 = O(n) ?
∀c > 0 et ∀n0 ≥ 0, si n1 = n0 + c, alors n12 > c.n1 .
Alors n2 ≠ O(n). On dit que n2 n’est pas dans l’ordre de n.
5- 5n2 + 3n + 4 = O(n2) ?
On sait que 3n + 4 ≤ n2 pour n ≥ 4.
Alors, pour n ≥ 4, 5n2 + 3n + 4 ≤ 6n2. Donc, il existe c = 6 et n0 = 4 tel que :
∀n ≥ n0, 5n2 + 3n + 4 ≤ cn2. Alors 5n2 + 3n + 4 = O(n2).
Propriétés :
- Si f = O(g) et g = O(h), alors f = O(h).
- Si f ∈ O(g) alors O(f) ⊆ O(g).
- Si f = (O(h)) et g = (O(h)) alors f + g = (O(h))
f ( n)
- Si lim = 0 , alors f = O(g) (l’implication inverse n’est pas correcte).
n →∞ g ( n)

2- La Notation « Grand Oméga Ω » :

La notation grand Ω sert à exprimer le fait que l'ordre de grandeur d'une fonction est
supérieur ou égal à une autre.
Soit f : N→R+ une fonction positive. On défini l'ordre Ω de f(n) comme l'ensemble:
Ω (f) = {g : N→R+ / (∃c > 0)(∃n0 ≥ 0)(∀n ≥ n0) : g(n) ≥ cf(n)}, c ∈ R, n0∈N.
On écrit g ∈ Ω(f) ou g = Ω(f). On dit que f(n) est une borne asymptotique inférieure
de g(n).

g(n)

c.f(n)

0 1 2 n0

Exemples :
– n2 = Ω(n) ?
-42-
 On sait que n < n2 pour n ≥ 2. Alors il existe c = 1 et n0 = 2 tel que :
∀n ≥ n0, n2 ≥ cn. Alors n2 = Ω(n).
Propriétés :
- Si f = (Ω(g)) et g = Ω(h), alors f = Ω(h).
- Si f ∈ Ω(g) alors Ω(f) ⊆ Ω(g).
- Si f = (Ω(h)) et g = (Ω(h)) alors f + g = (Ω(h))
- Si f = (Ω(g)) alors g = (O(f))
f ( n)
- Si lim = ∞ , alors f = Ω(g) (l’implication inverse n’est pas correcte).
n →∞ g (n)

3- La Notation « Grand Thêta Θ » :

La notation grand Θ sert à exprimer le fait que l'ordre de grandeur d'une fonction est
égal à une autre.
Soit f : N→R+ une fonction positive. On défini l'ordre Θ de f(n) comme l'ensemble:
Θ (f) = {g : N→R+ / (∃c1, c2 > 0)(∃n0 ≥ 0)(∀n ≥ n0) : c1f(n) ≤ g(n) ≤ c2f(n)}. c1, c2 ∈ R, n0∈N.
On écrit g ∈ Θ(f) ou g = Θ(f). On dit que f(n) est une borne approchée asymptotique
de g(n).

c2.f(n)

g(n)

c1.f(n)

0 1 2 n0

Exemples :
- 5n2 + 3n + 4 = Θ(n2) ?
On a vu que 5n2 + 3n + 4 ≤ 6n2 pour n ≥ 4. Aussi, 5n2 + 3n + 4 ≥ n2 pour n ≥ 0. Alors il
existe c1 = 1, c2 = 6 et n0 = 4 tel que :
∀n ≥ n0, c1n2 ≤ 5n2 + 3n + 4 ≤ c2n2. Alors 5n2 + 3n + 4 = Θ(n2).
Propriétés :
- Si f = (Θ(g)) et g = Θ(h), alors f = Θ(h).

-43-
- Si f = Θ(g) alors g = Θ(f)
- Si f = (Θ(h)) et g = (Θ(h)) alors f + g = (Θ(h))
- Si f = (Ω(g)) et f = (O(g)) alors f = Θ(g).
f ( n)
- Si lim = c, c ≠ 0 , alors f = Θ(g) (l’implication inverse est correcte).
n →∞ g ( n)

-44-
Les Analyses Asymptotiques (Complexité des Algorithmes)

1. Analyse des Algorithmes Itératifs :

Considérez le segment de code C suivant :
x = 0 ;
for ( i = 1 ; i <= n ; i++)
x++ ;
for ( j = 1 ; j <= n ; j = j * 2)
x++ ;
Le tableau suivant analyse le temps d’exécution de chacune de ces cinq lignes de code.
Ligne Temps d’exécution Nombre d’exécution Ordre
1 c1 1 O(1)
2 c2 n+1 O(n)
3 c3 n O(n)
4 c4 lg n + 1 O(lg n)
5 c5 lg n O(lg n)

Les temps d’exécution c1, c2, c3, c4 et c5 sont des constants inconnus. On est intéressé
par l’ordre du temps d’exécution du code T(n) mais pas par la valeur exacte du temps
d’exécution :
T(n) = c1 + c2(n+1) + c3n + c4(lg n + 1) + c5lg n

= (c1 + c2+ c4 ) + (c2 + c3)n + (c4 + c5) lg n

= O(1) + O(n) + O(lg n)

= O(n) + O(n) + O(n)

= O(n)
Cet exemple démontre que l’estimation du temps de chacune des lignes se fait
beaucoup plus simplement si l’on utilise la notation asymptotique.

Propriété :
- O(f).O(g) = O(f.g) (preuve ?)

-45-
Exemple : Considérez le segment de code C suivant :
x = 0 ;
for ( i = 1 ; i <= n/2 ; i++)
for ( j = 1 ; j <= n ; j = j * 2)
x++ ;
L’analyse de ce code est effectuée dans le tableau suivant :
Ligne Temps d’exécution Nombre d’exécution Ordre
1 c1 1 O(1)
2 c2 n/2 + 1 O(n)
3 c3 n/2 (lg n + 1) O(n)O(lg n)
4 c4 n/2.lg n O(n)O(lg n)
Alors,
T(n) = c1 + c2(n/2+1) + c3n/2(lg n + 1) + c4n/2.lg n

= (c1 + c2 + c3) + c2n/2 + (c3 + c4)n/2.lg n

= O(1) + O(n) + O(n lg n)

= O(n lg n)

2. Analyse des Algorithmes Récursifs :

Considérez le segment de code C suivant :
Void TriFusion(int a, int b) {
if (a = b) return;
TriFusion(a, (a + b)/2);
TriFusion((a + b)/2 + 1, b);
Fusionner(a, b);
}
Si le premier appel est TriFusion(1, n) alors le temps d’exécution T(n) est :
 Θ(1) si n = 1
T ( n) = 
2T (n / 2) + Θ(n) si n > 1

2.1 La Méthode de Substitution :

Cette méthode consiste à « deviner » une borne asymptotique supérieure à T(n), et
démontrer par récurrence qu’elle est vrai. On note qu’il faut avoir un petit peu d’expérience
pour deviner exacte. Néanmoins, il est toujours possible de commencer par une borne assez
supérieure, et faire la diminuer jusqu’à trouver la meilleure borne ; O(n3), O(n2), O(n lg n),
O(n), O( n ), O(lg n), …

-46-
 On considère l’exemple précédent en remplaçant Θ(n) par n, et Θ(1) par 1.
 1 si n = 1
T ( n) = 
2T (n / 2) + n si n > 1
On devine directement (O(nlgn)) que pour certain c, T(n) ≤ c n lg n. Alors, on va le
démontrer par récurrence comme suit :
On suppose qu’il est vrai pour n/2 : Donc T(n/2) ≤ c n/2 lg n/2

Alors : 2 T(n/2) ≤ c n lg n/2 = c n lg n - c n lg 2 = cn lg n – cn

Donc : 2 T(n/2) + n ≤ c n lg n – cn + n

Si on prend c ≥ 2 alors on trouve que T(n) ≤ c n lg n.

Il nous reste de trouver n0. Une série de testes consécutives à partir de 1 nous montre
que pour n ≥ 2 T(n) ≤ 2 n lg n. Démonstration terminée.
Il faut noter que pour d’autres valeurs de Θ(n) et Θ(1) il faut aussi fixer autres valeurs
pour c et n0.

Changer les variables :

Dans quelque cas, il est utile d’utiliser des manipulations mathématiques pour rendre
une expression de récurrence semble à une autre.
Par exemple, si T(n) = 2T( n ) + lg n, on peut remplacer lg n par m. Donc on obtient :
T(2m) = 2T(2m/2) + m. On peut aussi remplacer T(2m) par une autre fonction S(m). On a donc :
S(m) = 2S(m/2) + m. Cette fonction ressemble celle qu’on a vu précédemment.
Alors, on a S(m) = O(m lg m), et donc T(n) = S(m) = O(m lg m) = O(lg n lg lg n).

2.2 La Méthode de l’Arbre de Récurrence :

On a vu que la méthode de substitution ne fonctionne sauf si on devine la borne exacte
de la fonction du temps d’exécution. Malheureusement, ce n’est pas facile de réussir pour
toute type de fonction récursive.
Pour remédier à ce problème, on essaie de construire l’arbre récursive à partir de la
racine T(n), en dessinant ses descendants récursifs (T(n-1), T(n/2), …). Chaque nœud de cet
arbre représente le coût non récursif de la fonction T. Ensuite on calcule la somme des coûts
par niveau et le coût total de la fonction T(n).

Exemple :
Soit la fonction T(n) suivante :

-47-
  1 si n = 1
T ( n) = 
2T (n / 2) + 2n si n > 1

Voici alors son arbre récursive correspondant :

T(n) 2n 2n

T(n/2) T(n/2) n
n

T(n/4) T(n/4) T(n/4) T(n/4)

Niveau 0 2n Coût = 2n

Niveau 1 n Coût = n + n = 2n
n

Coût = 4 * n/2 = 2n
Niveau 2 n/2 n/2 n/2 n/2
………… ………………………………………….. …………

Niveau lg n T(1) T(1) T(1) T(1) ………… T(1) T(1) Coût = n * T(1) = n

Alors, le coût de chaque niveau (sauf le dernier) égale à 2n. Donc :

T(n) = lg n * 2n + n

= 2n lg n + n

= O(n lg n)
On peut aussi en déduire cette relation comme suit :
T(n) = 2T(n/2) + 2n

= 2(2T(n/4) + n) + 2n = 4T(n/4) + 4n

= 4(2T(n/8) + n/2) + 4n = 8T(n/8) + 6n

= 8(2T(n/16) + n/4) + 6n = 16T(n/16) + 8n

……..

= 2iT(n/2i) + i.2n

Donc pour i = lg n, on trouve que :

T(n) = 2lg nT(n/2lg n) + lg n . 2n

= nT(1) + 2n lg n

= n + 2n lg n

= O(n lg n)

-48-
 Il faut bien mentionner que la méthode de l’arbre de décision n’est pas une preuve ou
démonstration. Elle nous aide juste à trouver la borne asymptotique. Il nous reste donc à
compléter la démonstration en utilisant autres méthodes (comme la méthode de substitution).

2.2 La Méthode du Théorème Maître

Rappels :
- si x = y a alors y = log a x

ln x log b x
- log a x = =
ln a log b a

- si f(n) = O( log a n ), alors f(n) = O( log 2 n ) ou O(lg n) (Même règle pour Θ et Ω).

Théorème :
Le théorème maître présente une solution directe pour trouver la borne asymptotique
optimale d’une fonction récursive du type :
T (n) = aT (n / b) + f (n) , où a ≥ 1, b > 1 , et f(n) est une fonction asymptotiquement positive.
Mais il faut d’abord classer la fonction f(n) suivant ces trois cas :
1er Cas : si f (n) = O (n (logb a )−ε ) pour un constant ε > 0, alors T (n) = Θ(n log b a ) .

2ème Cas : si f (n) = Θ(n logb a ) , alors T (n) = Θ(n logb a lg n) .

3ème Cas : - si f (n) = Ω(n (log b a )+ε ) pour un constant ε > 0,

- et si af (n / b) ≤ cf (n) pour un constant c < 1 et n > n0 ( n est suffisamment
large),
alors T (n) = Θ( f (n)) .
Explication :
Le théorème maître essaie de comparer f(n) et n logb a , et décider lequel est une borne
asymptotique approchée pour T(n). Dans le premier cas, n logb a est asymptotiquement supérieur
à f(n). Dans le troisième cas, f(n) est supérieur. Dans le troisième cas, ils sont proche. Nous
allons pas élaborer la démonstration de ce théorème (on le laisse pour les matheux !)
Il reste à signaler qu’il y a des fonctions récursives de type
T (n) = aT (n / b) + f (n) que le théorème maître ne peut pas trouver leur borne asymptotique.

Exemples :
1- T (n) = 9T (n / 3) + n.
Alors pour cette récurrence on a a = 9, b = 3, et f(n) = n.
n logb a = n log3 9 = n2. Tant que f(n) = O(n) = O( n (log3 9 )−ε ) pour ε = 1,
-49-
 alors T (n) = Θ(n log3 9 ) = Θ(n 2 ).

2- T (n) = T (2n / 3) + 1.
Alors pour cette récurrence on a a = 1, b = 3/2, et f(n) = 1.
n logb a = n log3 / 2 1 = n0 = 1. Le deuxième cas est appliqué ici : f(n) = Θ(1).
Donc, T (n) = Θ(n log3 / 2 1 lg n) = Θ(lg n).

3- T (n) = 3T (n / 4) + n lg n.
Pour cette récurrence on a a = 3, b = 4, et f(n) = n lg n.
n logb a = n log 4 3 ≈ n0.793. On a f(n) = Ω(n) = Ω ( n (log 4 3)+ε ) pour ε ≈ 0.21. Alors pour
appliquer le troisième cas, il nous reste de montrer que af(n/b) ≤ c f(n) pour certain c <
1 et n suffisamment large.
af(n/b) = 3 f(n/4) = 3.n/[Link] n/4 = 3/4 n (lg n – lg 4) ≤ 3/4 n lg n.
Donc on a trouver c = 3/4 < 1.
Alors T (n) = Θ( f (n)) = Θ(n lg n).

4. T(n) = T(n/2) + c
a=1
b=2
f(n) = c
nlogba = n0 = 1
c = Θ(1)
f(n) = Θ( nlogba)
T(n) = Θ( nlogba lg n) = Θ(lg n)

T(n) = T(n-1) + c2, T(1) = c1.

T(n) = c1 + c2(n-1)
T(n) = O(n)
Un = Un-1 + 5, U1 = 3.
Un = 3 + 5(n-1)

T(n) = T(n/3) + T(2n/3) + n < 2 T(2n/3) + n

H(n) = T(2n/3) + n
H(n) = Θ(n2)

-50-
H(n) = cn2.

T(n) = 2T(n/2) + 2n
A=2 , b=2, f(n) = 2n
Nlog2(2) = n
F(n) = Θ( Nlog2(2))
Donc T(n) = Θ(n lg n)

-51-
 Preuve d’Exactitude d’un Algorithme

1- Invariant de Boucle :
Un invariant de boucle est une propriété vérifiée tout au long de l'exécution de la
boucle. Il est intéressant lorsqu'il permet de conclure l'exactitude de l'algorithme au moment
de sa terminaison.
Exemple :
Soit la boucle en C suivante :
for(i = 1 ; i <= n ; i++)
for(j = n ; j >= i ; j--)
printf(“%d %d”, i, j);
On peut donc extraire plusieurs invariants de boucle qui maintiennent leur validités au
long de l’exécution de la boucle :
- 1 < 2
- i ≤ n +1
- 1 ≤ j
- i ≤ j

2- Preuve d’Exactitude :
Une preuve d’exactitude d’un algorithme par invariant de boucle utilise la démarche
suivante :
1- Nous prouvons tout d’abord que l’algorithme s’arrête en montrant qu’une
condition d’exécution de boucle finit par ne plus être réalisée.
2- Nous exhibons alors un invariant de boucle, c’est-à-dire une propriété P qui,
si elle est valide avant l’exécution d’un tour de boucle, est aussi valide après
l’exécution du tour de boucle.
3- Nous vérifions alors que les conditions initiales rendent la propriété P vraie
en entrée du premier tour de boucle. Nous en concluons que cette propriété
est vraie en sortie du dernier tour de boucle. Un bon choix de la propriété P
prouvera qu’on a bien produit l’objet recherché. La difficulté de cette
méthode réside dans la détermination de l’invariant de boucle. Quand on l’a
trouvé il est en général simple de montrer que c’est bien un invariant de
boucle.

-52-
 Donc, après qu’on détermine l’invariant de la boucle, on établie une démonstration
(similaire que celle par récurrence) que notre algorithme est correct comme suit :
1- 1ère étape : Initialisation : On montre que l’invariant est valide avant la première
itération de la boucle.
2- 2ème étape : Maintenance : On suppose que l’invariant est vrai avant l’exécution de la
ième itération, est on montre qu’il reste valide après l’exécution de cette itération.
3- 3ème étape : Terminaison : Lorsque la boucle se termine, l’invariant nous donne une
propriété utile pour nous aider à démontrer que l’algorithme est correct.

Exemple :
Soit l’algorithme « Tri par Insertion » suivant :
for(i = 2 ; i <= n ; i++) {
cle = A[i]; /* clé à insérer dans A[1..i-1]*/
j = i -1;
while ((j > 1) && (A[j] > cle)) {
A[j + 1] = A[j];
j = j – 1;
}
A[j + 1] = cle;
}
Supposons que la tableau A lorsque i = 5 était comme suit :

1 2 3 4 5 6 7 8
2 3 7 12 6 1 10 13

On veut donc insérer la clé 6 dans le sous-tableau [2, 3, 7, 12] :

A[5] = A[4]

1 2 3 4 5 6 7 8
2 3 7 12 12 1 10 13

A[4] = A[3]

1 2 3 4 5 6 7 8
2 3 7 7 12 1 10 13

-53-
 A[3] = cle = 6

1 2 3 4 5 6 7 8
2 3 6 7 12 1 10 13

Maintenant, on veut démontrer l’exactitude de cet algorithme en général. Il faut donc

choisir un bon invariant de boucle qui nous aidera à démontrer l’exactitude.
Alors, soit l’invariant suivant : « A[1..i-1] est trié » .
Initialisation : Au début de l’exécution de l’algorithme de tri par insertion, et lorsque i = 2,
le sous-tableau A[1..i-1] contient un seul élément A[1]. Alors, cet évident qu’un tableau
d’un seul élément est trié.
Maintenance : Supposons qu’avant l’exécution de l’itération pour i que l’invariant était
valide (A[1..i-1] est trié). On veut montrer qu’à la fin d’exécution de cette itération, et
lorsque i s’incrémente, l’invariant restera toujours valide ;i .e. A[1..i-1] est trié.
On a donc A[1..i-1] trié avant l’exécution de la boucle interne. Il faut ici
démontrer qu’après l’exécution de la boucle interne que le nouveau sous-tableau A[1..i]
est trié. On peut facilement fixer un deuxième invariant pour la boucle interne comme suit :
« A[1..j] est trié
ET A[j+1..i] est trié
ET tous les éléments du A[j+1..i]sont supérieurs ou égale à cle»
(il reste comme exercice à domicile)
Terminaison : A la fin d’exécution de l’algorithme, l’invariant reste toujours valide
( A[1..i-1] est trié). On sait aussi que la valeur de i pour qu’on puisse sortir de la boucle
doit être égale à n+1. Alors, à la fin d’exécution on a A[1..n]trié.

Ecrire(1)
Pour i = 2, n Faire
Ecrire(i)

Invariant : l’algorithme imprime tous les nombres de 1 jusqu’à i-1.

Initialisation : pour i = 2, l’algorithme imprime tous les nombres de 1 jusqu’à 1.
Maintenance : supposons que l’algorithme imprime tous les nombres de 1 jusqu’à i-1 avant
l’exécution de la ième itération. Au moment de l’exécution de la ième itération, l’algorithme
imprime la valeur de i. Alors, l’algorithme a imprimé tous les nombres de 1 jusqu’à i. A la fin

-54-
de la ième itération, i s’incémente. Alors, l’algorithme a imprimé tous les nombres de 1 jusqu’à
i-1. Donc l’invariant reste valide.
Terminaison : Alors, l’algorithme imprime tous les nombres de 1 jusqu’à n.

-55-
 Tri par Tas (HeapSort)

Autres appellations : Tri par Arbre, Tri Maximier, …

1. Définition 1 : Un arbre binaire partiellement ordonné est un arbre binaire tel que l’élément
contenu dans tout nœud est supérieur ou égal aux éléments contenus dans les fils de ce nœud.
Exemple :

12

7 9

1 6 3

2. Définition 2 : Un arbre binaire est parfait si tous ses niveaux sont complètement remplis,
sauf éventuellement le dernier niveau, et dans ce cas les nœuds (feuilles) du dernier niveau
sont regroupés le plus à gauche.

12 12 12

3 11 3 11 3 11

2 10 2 7 10 2 7 10 1

Arbre Imparfait Arbre Parfait Incomplet Arbre Parfait Complet

3. Représentation par tableau d’un arbre parfait:

Un arbre parfait peut être facilement représenté par un tableau comme suit : On
considère un parcours en largeur de l’arbre, et on place chaque nœud rencontré directement
dans la place successive dans le tableau :

-56-
 12

3 11 12 3 11 2 7 10

2 7 10

L'intérêt d'utiliser un arbre parfait complet ou incomplet réside dans le fait que le
tableau est toujours compacté, les cellules vides s'il y en a se situent à la fin du tableau.

4. Le Tas: On appelle tas un tableau représentant un arbre parfait partiellement ordonné. Le

fait d'être partiellement ordonné sur les valeurs permet d'avoir immédiatement un maximum à
la racine.

5. Propriétés d'un tas T :

- T[1] désigne la racine de l'arbre parfait correspondant.
- T[i / 2] désigne le père de T[i].
- T[2i] et T[2i + 1] sont les fils de T[i] dans l'arbre parfait, s'ils existent.
- Si l'arbre a p nœuds avec p = 2i, alors T[i] n'a qu'un seul fils (gauche), T[p].
- Si i > p / 2, alors T[i] est une feuille.

6. Tri par Tas:

L’opération de tri par tas permet de trier un tableau par ordre décroissant. Elle
comporte les opérations suivantes :
1- Construire le tas (son arbre) contenant les n éléments à trier par des adjonctions
successives.
2- Rechercher le maximum et le placer dans le tableau trié.
3- Supprimer le Maximum du tas et le réorganiser.
4- Recommencer à l’étape 2 jusqu’à ce que le tas soit vide, soit n fois.

Exemple :
On veut trier le tableau [8, 2, 7, 6, 4] :
1ère étape (Construire le Tas): Insertion des éléments dans un arbre parfait partiellement
ordonné :

-57-
 Insérer 8
8 Insérer 2
8 Insérer 7
8 Insérer 6
8 Réorganiser

2 2 7 2 7

8 Insérer 4 8

6 7 6 7

2 2 4

2ème étape (Tri par Tas): Répéter : Supprimer et envoyer la racine vers le tableau trié, et
réorganiser (Entasser):

8 4 7
Réorganiser Réorganiser
6 7 6 7 6 4

2 4 2 2
8 8 8

7 2 6
Réorganiser Réorganiser
6 4 6 4 2 4

2
8 7 8 7 8 7

6 4 2
Réorganiser Réorganiser
2 4 2

8 7 6 8 7 6 4 8 7 6 4 2

-58-
Procédure ConstruireTas :
Pour i ← 1 , n Faire
Debut
Tas[i] ← A[i]
j ← i
Tant Que (j > 1) ET (Tas[j] > Tas[j / 2]) Faire
Debut
Echanger(Tas[j], Tas[j / 2]) {monter Tas[j]}
j ← j / 2
Fin
Fin
Procédure TriParTas :
Pour i ← 1 , n - 1 Faire
Debut
A[i] ← Tas[1] {Extraire le maximum}
Tas[1] ← Tas[TailleTas] {Remplacer le maximum}
TailleTas ← TailleTas -1 {Diminuer la taille du tas}
Entasser() {Réorganiser le tas}
Fin
A[n] ← Tas[1] {Extraire le dernier élément}

Procédure Entasser :
i ← 1
Tant Que (i < TailleTas) ET ((Tas[i] < Tas[2*i]) OU (Tas[i] < Tas[2*i+1]))
Faire {tant que le père est inférieur à un de ses fils}
Debut
Si Tas[2*i] < Tas[2*i + 1] Alors IndiceMax ← 2*i +1
Sinon IndiceMax ← 2*i
Echanger(Tas[i], Tas[IndiceMax])
i ← IndiceMax
Fin
Cette procédure est incomplète car on traite que les nœuds avec deux descendants. Il
reste à l’étudiant de terminer le traitement d’un nœud avec un seul descendant et aussi pour
une feuille.

7. Analyse de la complexité :
- ConstruireTas : O(n lg n)
- Entasser : O(lg n)
- TriTas : O(n lg n)

-59-