ALGORITHMIQUE

Notes du cours FS/1/6584

Université de Mons-Hainaut
Année préparatoire au Master en Informatique

Gilles G EERAERTS
Université Libre de Bruxelles

A NNÉE ACADÉMIQUE 2007–2008

2
Table des matières

1 Introduction 11
1.1 Le contenu et les objectifs du cours . . . . . . . . . . . . . . . . . . . 11
1.1.1 Algorithmes, Algorithmique . . . . . . . . . . . . . . . . . . 11
1.1.2 Les objectifs et l’orientation du cours . . . . . . . . . . . . . 14
1.2 Le pseudo-langage . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.1 Types et variables . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.3 Gestion de la mémoire . . . . . . . . . . . . . . . . . . . . . 16
1.3 Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2 Itération, induction, récursivité 19

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Itération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.3 Récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 Itération et induction . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Raisonnement par induction . . . . . . . . . . . . . . . . . . 22
2.3 Preuves de programmes . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.1 Notion d’invariant de boucle . . . . . . . . . . . . . . . . . . 26
2.3.2 Un exemple de preuve par invariant . . . . . . . . . . . . . . 27
2.4 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.1 Récursivité et induction . . . . . . . . . . . . . . . . . . . . 30
2.4.2 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . 31

3 La complexité algorithmique 33
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Notion d’efficacité . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Mesure du temps de calcul . . . . . . . . . . . . . . . . . . . 34
3.2.2 Compter le nombre d’étapes . . . . . . . . . . . . . . . . . . 35
3.3 La notion de grand O . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.1 Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.2 Définition formelle . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.3 Classes de complexité algorithmique . . . . . . . . . . . . . . 39
3.3.4 Règles de combinaison et de simplification . . . . . . . . . . 40
3.4 Le cas des programmes récursifs . . . . . . . . . . . . . . . . . . . . 42
3.4.1 Utilisation de l’induction . . . . . . . . . . . . . . . . . . . . 43

3
4 TABLE DES MATIÈRES

4 Les listes 45
4.1 Motivation : critique des tableaux . . . . . . . . . . . . . . . . . . . . 45
4.2 Les listes simplement liées . . . . . . . . . . . . . . . . . . . . . . . 46
4.2.1 Comparaison aux tableaux . . . . . . . . . . . . . . . . . . . 47
4.2.2 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.2.3 Listes triées . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Les listes circulaires avec élément pré-tête . . . . . . . . . . . . . . . 55
4.3.1 Différences par rapport aux listes « simples » . . . . . . . . . 56
4.3.2 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4 Les listes doublement liées . . . . . . . . . . . . . . . . . . . . . . . 63
4.5 Implémentation des listes dans les vecteurs . . . . . . . . . . . . . . 65
4.5.1 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.6 Vue récursive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6.1 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5 Les piles et les files 73

5.1 Les piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.1.1 Implémentation dans une liste . . . . . . . . . . . . . . . . . 74
5.1.2 Implémentation dans un vecteur . . . . . . . . . . . . . . . . 75
5.2 Les files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2.1 Implémentation dans une liste . . . . . . . . . . . . . . . . . 79
5.2.2 Implémentation dans un vecteur . . . . . . . . . . . . . . . . 80
5.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3.1 Vérification des parenthèses . . . . . . . . . . . . . . . . . . 86
5.3.2 Évaluation d’une expression en notation postfixée . . . . . . . 87

6 Les arbres 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.1.2 Vocabulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.3 Cas particuliers . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.1.4 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.1.5 Application : les arbres d’expressions . . . . . . . . . . . . . 101
6.2 Parcours des arbres binaires . . . . . . . . . . . . . . . . . . . . . . . 104
6.2.1 Parcours préfixé ou parcours en profondeur . . . . . . . . . . 105
6.2.2 Parcours infixe . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2.3 Parcours postfixé . . . . . . . . . . . . . . . . . . . . . . . . 110
6.2.4 Le parcours par niveaux ou parcours en largeur . . . . . . . . 111
6.2.5 Applications des parcours . . . . . . . . . . . . . . . . . . . 111

7 Algorithmes de recherche 115

7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.2 Données stockées dans des vecteurs . . . . . . . . . . . . . . . . . . 116
7.2.1 Recherche linéaire simple . . . . . . . . . . . . . . . . . . . 116
7.2.2 Recherche linéaire dans un vecteur trié . . . . . . . . . . . . 117
7.2.3 Recherche dichotomique dans un vecteur trié . . . . . . . . . 118
7.2.4 Tables de hachage . . . . . . . . . . . . . . . . . . . . . . . 122
7.3 Données stockées dans des listes . . . . . . . . . . . . . . . . . . . . 127
7.4 Données stockées dans des arbres . . . . . . . . . . . . . . . . . . . 127
7.4.1 Parcours simple . . . . . . . . . . . . . . . . . . . . . . . . . 127
TABLE DES MATIÈRES 5

7.4.2 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . 128

8 Conclusion : aux limites de l’algorithmique 141

6 TABLE DES MATIÈRES
Table des figures

1.1 Une illustration du tri par sélection. Les cases grisées sont celles qui
sont considérées en place. . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Une illustration de la méthodologie que nous adopterons dans le cours. 14

2.1 L’ordinogramme de la boucle tant que. . . . . . . . . . . . . . . . . 21

3.1 Comparaison de polynômes de degrés 3 et 4 (petite échelle). . . . . . 38

3.2 Comparaison de polynômes de degrés 3 et 4 (grande échelle). . . . . . 38
3.3 Comparaison de différentes fonctions caractérisant les principales classes
de complexité algorithmique (échelle logarithmique en ordonnées). . . 40
3.4 Une illustration de l’exécution de Facto(k). . . . . . . . . . . . . . . 44

4.1 Un exemple de liste comprenant trois éléments, et dont la tête est sto-
ckée dans la variable L. . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Un exemple de suppression dans une liste simplement liée. Les poin-
teurs et éléments en pointillés disparaissent lors de la suppression. . . 48
4.3 Un exemple d’insertion dans une liste simplement liée. Les pointeurs
et éléments en pointillés disparaissent lors de l’insertion. . . . . . . . 48
4.4 Un exemple de déplacement : l’élément 4 se trouve entre 2 et 7 avant
le déplacement, et se retrouve entre 1 et 2 après les déplacement. Trois
pointeurs ont été modifiés. Les pointeurs en pointillés réprésentent les
anciennes valeurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5 Un exemple de liste circulaire avec élément pré-tête. . . . . . . . . . 57
4.6 Un exemple d’insertion en tête dans une liste circulaire avec élément
pré-tête. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.7 Une liste circulare avec élément pré-tête vide. . . . . . . . . . . . . . 58
4.8 La recherche de l’information k dans une liste circulaire avec élément
pré-tête. Au pire cas (quand k n’est pas présent dans la liste), le pointeur
fait le tour de la liste et revient à l’élément pré-tête, qui contient k. . . 59
4.9 Un exemple de liste doublement liée. . . . . . . . . . . . . . . . . . . 63
4.10 Un exemple d’insertion dans une liste doublement liée. On insère un
élément portant la valeur 3 avant l’élément portant la valeur 4. . . . . 64
4.11 Un exemple de liste implémentée dans un vecteur, et son équivalent
utilisant des pointeurs. . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.1 Un exemple de pile contenant (de bas en haut) les valeurs 2, 3, 4 et 5. 74

5.2 La pile de la Fig. 5.1 implémentée dans une liste. . . . . . . . . . . . 75

7
8 TABLE DES FIGURES

5.3 Un exemple de manipulation de file dans un vecteur. Les cases grisées

sont celles qui font partie de la file. . . . . . . . . . . . . . . . . . . . 83
5.4 Le vecteur implémentant la file vu comme un vecteur circulaire. Les
cases grisées sont celles qui font partie de la file. . . . . . . . . . . . . 84

6.1 Un exemple d’arbre, qui représente l’organisation hiérarchique d’une

entreprise (un peu fantaisiste). . . . . . . . . . . . . . . . . . . . . . 92
6.2 Un exemple d’arbre. Les informations associées aux nœuds ne sont pas
représentées. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.3 La vue récursive de l’arbre de la Fig. 6.2. . . . . . . . . . . . . . . . 94
6.4 Quelques illustrations du vocabulaire sur les arbres. . . . . . . . . . . 96
6.5 Un exemple d’arbre binaire équilibré. . . . . . . . . . . . . . . . . . 97
6.6 Un exemple d’arbre d’expression qui représente (3 + 5) ∗ 2. . . . . . . 104
6.7 Les quatre parcours d’arbre classiques. La flèche en pontillé indique
l’ordre des appels. Un point à proximité d’un nœud indique à quel mo-
ment le nœud sera effectivement traité lors du parcours. . . . . . . . . 106
6.8 Une illustration du parcours en largeur. Les nœuds grisés ont été traités.
Le contenu de la file à chaque étape est représenté sous l’arbre. . . . . 112

7.1 Une illustration de la recherche dichotomique. Les cases grisées déli-

mitent l’intervalle de recherche . . . . . . . . . . . . . . . . . . . . . 120
7.2 Une illustration du hachage avec chaînage. . . . . . . . . . . . . . . . 125
7.3 Un exemple d’arbre binaire de recherche (équilibré). En pointillés, le
chemin parcouru pour accéder à l’information 23. . . . . . . . . . . . 129
7.4 L’ordre sur les nœuds induit par un arbre binaire de recherche (il s’agit
de l’ordre du parcours infixe). . . . . . . . . . . . . . . . . . . . . . 130
7.5 Deux insertions dans un ABR. Les chemins suivis sont indiqués en
pointillés. Les comparaisons réalisées sont indiquées le long des che-
mins, à côté des nœuds concernés. . . . . . . . . . . . . . . . . . . . 132
7.6 Une illustration des trois cas de suppression dans un ABR. Le nœud à
supprimer est indiqué en grisé. . . . . . . . . . . . . . . . . . . . . . 135
7.7 Le détachement du maximum dans un ABR . . . . . . . . . . . . . . 136
7.8 Un exemple d’arbre dont la hauteur est en O du nombre de nœuds. Il
s’agit en fait d’une liste. . . . . . . . . . . . . . . . . . . . . . . . . . 139
Avant propos

Cet ouvrage constitue les notes du cours d’Algorithmique, dispensé dans le cadre
de l’année préparatoire au Master en Informatique (horaire décalé), co-organisé par les
Universités de Bruxelles et Mons. Il s’agit de la première version de ces notes. À ce
titre, ce travail est certainement perfectible, et susceptible de contenir l’une ou l’autre
coquille. Je fais donc appel à l’indulgence du lecteur, qui – j’en suis convaincu – me
pardonnera volontiers en songeant aux conseils de Nicolas B OILEAU :
Hâtez-vous lentement ; et, sans perdre courage,
Vingt fois sur le métier remettez votre ouvrage :
Polissez-le sans cesse et le repolissez ;
Ajoutez quelquefois, et souvent effacez.

Mes remerciements les plus vifs vont à M. Jérome J ONCKERS, qui a accepté sans
réserve de relire ces notes, avec la rigueur et le professionnalisme qui le caractérisent.
Ses remarques toujours à propos ont indéniablement contribué à améliorer la qualité
de ce syllabus. Je remercie également les étudiants qui, à travers leurs nombreuses
questions et remarques durant le cours m’ont permis de corriger plusieurs erreurs et
imprécisions.

Bruxelles, décembre 2007

9
10 TABLE DES FIGURES
Chapitre 1

Introduction

1.1 Le contenu et les objectifs du cours

1.1.1 Algorithmes, Algorithmique
Pour expliquer ce que sont les ordinateurs, il est de coutume de les comparer
aux calculatrices de bureau, et d’expliquer que, somme toute, un ordinateur n’est rien
d’autre qu’une calculatrice très perfectionnée. Il y a pourtant une différence importante
entre une calculatrice capable d’effectuer les quatre opérations de base et un ordina-
teur : c’est que l’ordinateur est, par définition, programmable, ce qui n’est le cas que
des modèles les plus évolués de calculatrices. . .
Cette différence est fondamentale. Alors qu’une calculatrice ne donne accès qu’aux
fonctionnalités qui sont liées à chacune de ses touches, l’ordinateur offre un jeu d’ins-
tructions de base très riche, dont l’utilisateur peut se servir à sa guise afin d’élaborer
des programmes capables de résoudre des problèmes bien plus complexes que ceux
traités par les instructions de base.
L’immense majorité du travail effectué par un professionnel de l’informatique tou-
che donc de près ou de loin à la question suivante : « Comment faire résoudre tel
problème à un ordinateur ? » Une part de la réponse à cette question est parfois trouvée
dans l’assemblage de solutions préexistantes fournies par des tierces parties. Néan-
moins, tout informaticien se retrouve confronté un jour ou l’autre avec la nécessité de
programmer une nouvelle fonctionnalité, soit pour résoudre le problème posé dans son
entièreté, soit comme étape particulière d’une solution globale dont certaines étapes
sont déjà fournies.

La tâche de l’informaticien consiste alors, grosso modo à traduire des desiderata

exprimés de façon plus ou moins claire et plus ou moins formelle en un programme
dans un langage de programmation bien déterminé.
Un exemple de desiderata pourrait être : « Trier un tableau de nombres entiers
par ordre croissant ». Dans ce cas, il y aura lieu, dans un premier temps, d’établir la
méthode générale qui va être appliquée. Par exemple :
1. Rechercher dans tout le tableau la valeur minimale.
2. Placer cette valeur minimale en première position, et placer la valeur qui était en
première position là où était la valeur minimale (en d’autres mots : échanger les
deux valeurs). La valeur minimale est maintenant « à sa place »

11
12 CHAPITRE 1. INTRODUCTION

3. Recommencer le même traitement sur la partie du tableau contenant les éléments

qui ne sont pas encore à leur place, et ce, tant qu’il y en a.
Cette méthode est illustrée à la Fig. 1.1. Nous l’appellerons tri par sélection, car
à chaque étape nous sélectionnons l’élément à placer en tête du tableau, Elle semble
satisfaisante, et peut donc être traduite dans le langage de programmation choisi.
Il est intéressant de remarquer que nous avons introduit une étape intermédiaire
entre la compréhension du problème et sa résolution en terme de programme infor-
matique. Cette étape a consisté en la description d’une méthode générale de tri, qui
exprime l’essence du programme à produire, et qui aurait d’ailleurs pu être traduite
dans plusieurs langages de programmation différents.
Cette méthode est ce que nous appelons un algorithme, c’est-à-dire une suite d’ac-
tions bien définies à enchaîner pour résoudre un problème. Remarquons que tout
programme est, lui aussi, un algorithme. Mais le pseudo-lanagage a l’avantage d’être
indépendante du choix du langage de programmation final, ce qui nous permettra sou-
vent de tenir des raisonnements formels et rigoureux sur l’algorithme choisi.

La méthodologie que nous venons d’esquisser est résumée à la Fig. 1.2. Dans ce
cadre, la phase de conception de l’algorithme est l’étape essentielle, car c’est à tra-
vers l’algorithme qu’on spécifie l’idée du traitement à réaliser. Cela ne veut pas dire
pour autant que la phase de traduction en programme est facile ou triviale : elle a ses
problèmes spécifiques, mais nous ne les aborderons pas ici. Au contraire, nous allons
nous concentrer sur l’étude de l’algorithmique, c’est-à-dire la discipline qui étudie les
algorithmes et leur conception.
Pour autant, il ne faut pas confondre l’algorithmique avec une liste de solutions pré-
établies pour chaque problème, un peu comme un bon livre de cuisine offre une recette
adaptée à chaque circonstance. En effet, la méthode décrite ci-dessus peut soulever
certaines questions comme :
1. Cette méthode est-elle correcte ? Autrement dit, est-on sûr qu’en l’appliquant à
n’importe quel tableau, on obtiendra toujours un tableau trié ? Afin de nous en
convaincre le mieux possible, nous une preuve formelle et rigoureuse est néces-
saire. Le concept de correction d’un algorithme et les méthodes pour la prouver
seront introduits au Chapitre 2.
2. La méthode utilisée consiste en la répétition d’un même traitement. Est-il pos-
sible d’utiliser d’autres « canevas » d’algorithme ? Nous étudierons notamment
la récursivité au Chapitre 2.
3. Quelle est l’efficacité de la méthode utilisée ? Comment peut-on la mesurer ?
Comment peut-on comparer deux méthodes différentes résolvant le même pro-
blème afin de sélectionner la plus efficace ? Nous apporterons des réponses à ces
questions au Chapitre 3.
Par ailleurs, l’algorithmique est étroitement liée à l’étude des structures de don-
nées. Dans l’exemple de cette introduction, la structure des données est donnée expli-
citement : c’est un tableau d’entiers. On peut dès lors se demander si on n’aurait pas
obtenu un algorithme de tri plus efficace si on avait structuré les données autrement. De
même, la structure de tableau n’est pas forcément adaptée à tous les problèmes. Dans
les chapitres 4, 5 et 6 nous étudierons d’autres structures de données ainsi que leurs
algorithmes associés.
1.1. LE CONTENU ET LES OBJECTIFS DU COURS 13

F IG . 1.1 – Une illustration du tri par sélection. Les cases grisées sont celles qui sont
considérées en place.
14 CHAPITRE 1. INTRODUCTION

l a
r a

n
n

g
ç

u
a

e
i s

n
o

a
u

t u
a

r e
u

l
t

l
r

e
e

{ P

d
r

e
o

s
b

i
l

d
è

e
m

r a
e

t a
e t

F o r m u l a t i o n d e s h y p o t h è s e s

e t r é fl e x i o n s u r l e p r o b l è m e

P s e u d o / l a n g a g e

{ A l g o r i t h m e
P e r m

P
e

r e
t

u
d

v
e

e
r

d
a

e
i s o

c
n

o
n

r r
e

e
r

c
f

t
o

i o
r

n
m

,
e

e
l

t
l e

c .
m

. .
e n t :

T r a d u c t i o n v e r s l e l a n g a g e c h o i s i

P r
L

o
a

g
n

r
g

a
a

m
g

m
e

a
d

t
e

i o n

{ P r o g r a m m e

F IG . 1.2 – Une illustration de la méthodologie que nous adopterons dans le cours.

1.1.2 Les objectifs et l’orientation du cours

Ce cours adopte une approche scientifique de l’algorithmique. Cela signifie qu’on
y enseignera des algorithmes et des structures de données de base qui permettent de
résoudre des problèmes typiques, mais aussi des outils (comme la complexité, les in-
variants) qui permettent d’analyser ces solutions, de les justifier, de mieux les com-
prendre, et d’en élaborer de nouvelles.
Ce cours fera donc appel tant à la rigueur qu’à la créativité des étudiants.

1.2 Le pseudo-langage
Afin de pouvoir nous concentrer sur les aspects purement algorithmiques des no-
tions étudiées dans ce cours, nous allons nous détacher autant que faire se peut des
problèmes liés aux langages de programmation. Nous n’exprimerons donc pas nos al-
gorithmes dans un des langages classiques comme C, C++ ou PASCAL. Nous allons
adopter un pseudo-langage qui pourra être aisément traduit vers n’importe quel lan-
gage de programmation procédural. Cette approche aura l’intérêt de mettre en avant les
traitements nécessaires pour résoudre un certain problème.

1.2.1 Types et variables

Nous supposerons que les variables sont typées et déclarées, ce qui signifie qu’on
veillera à toujours déclarer une variable avant de l’utiliser, et qu’on spécifiera le type
de données que cette variable peut contenir. Les types admis seront les types classiques
comme Entier, Booléen, Chaine (de caractères), etc. Nous pourrons déclarer et utiliser
des tableaux multidimensionnels de ces types, en utilisant la notation [ ], comme en C
ou C++. Nous manipulerons également des pointeurs (voir ci-dessous).
Par ailleurs, le pesudo-langage permettra d’enrichir les types que nous pouvons
utiliser, en créant de nouveaux types. Ceux-ci seront construits à partir des types de
bases ou à partir d’autres structures, de la même façon que les stru t en C ou C++.
Une structure peut être vue comme le groupement de plusieurs variables. On déclare
1.2. LE PSEUDO-LANGAGE 15

une structure à l’aide du mot-clé struct, suivi du nom du type, suivi de la liste des
différentes variables à regrouper dans le type. Ces variables sont appelées des champs,
portent toutes un nom différent et peuvent être de types différents :
struct nom
Type1 nomChamp1 ;
Type2 nomChamp2 ;
..
.
TypeN nomChampN ;

Exemple 1 La structure suivante déclare le nouveau type Etudiant qui regroupe un

entier (le matricule de l’étudiant) et deux chaînes de caractères (ses nom et prénom) :
struct Etudiant
Entier matricule ;
Chaine nom ;
Chaine prenom ;

Il faut bien garder à l’esprit qu’une telle déclaration crée un nouveau type et non
pas une nouvelle variable, ce qui signifie que rien n’est créé en mémoire par ces ins-
tructions. Par contre, une fois cette déclaration effectuée, nous pourrons déclarer des
variables du type Etudiant.
Étant donné une variable v dont le type est une structure, nous pouvons accéder
à chacun des champs de v comme à des variables indépendantes. Ces champs sont
nommés par [Link].

Exemple 2 Si E est une variable de type Etudiant, on assigne le matricule 123 à E

de la façon suivante :

[Link] := 123 ;

1.2.2 Instructions
Les instructions que nous utiliserons sont les suivantes :
:= Il s’agit de l’opérateur d’assignation ou affectation. À gauche de cet opérateur, on
trouvera obligatoirement une variable. À droite de l’opérateur, on trouve une
expression du même type que la variable. L’effet de l’opérateur d’assignation est
le suivant : on commence par évaluer la valeur de l’expression à droite. Ensuite,
cette valeur est stockée dans la variable.
Certains ouvrages utilisent plutôt la notation ← pour désigner l’assignation en
pseudo-langage. Il nous arrivera d’utiliser l’une ou l’autre.
si. . . sinon Il s’agit de l’instruction permettant d’effectuer un test. La syntaxe typique
est si condition alors instructions 1 sinon instructions 2. Dans le cas où la
condition est vérifiée, le bloc instructions 1 uniquement sera exécuté. Dans le
cas contraire, c’est le bloc instructions 2 uniquement qui sera exécuté. La par-
tie sinon est optionnelle. On utilisera parfois l’extension permettant de tester
plusieurs conditions en séquences : si condition 1 alors instructions 1 sinon si
condition 2 alors instructions 2. . . sinon instructions n. Dans ce cas, la condi-
tion 1 est testée d’abord. Si elle est vérifiée, le bloc instructions 1 uniquement
est exécuté (les autres conditions ne sont pas testées). Si la condition 1 n’est pas
16 CHAPITRE 1. INTRODUCTION

vérifiée, on teste la condition 2, et exécute le bloc instructions 2 quand cette der-

nière est vérifiée. Dans le cas contraire, on continue ainsi à tester les instructions
de façon séquentielle, jusqu’à découvrir une condition vérifiée, ce qui donne lieu
à l’exécution du bloc d’instructions associé. Si aucune des conditions n’est véri-
fiée, le bloc instructions n est exécuté.
tant que Il s’agit de l’instruction permettant de répéter un traitement tant qu’une cer-
taine condition est vérifiée. Sa syntaxe est tant que (condition) faire instruc-
tions. Le bloc d’instructions sera exécuté tant que la condition est vraie. Plus
précisément, une boucle tant que s’exécute ainsi : la condition est testée. Si elle
n’est pas vérifiée, les instructions ne sont pas exécutées et la boucle s’arrête. Si
la condition est vérifiée, l’intégralité du bloc d’instructions est exécutée, et on re-
commence : on teste à nouveau la condition ; si elle est fausse on arrête la boucle,
si elle est vraie, on exécute les instructions, etc.
pour Cette instruction permet, comme l’instruction tant que, de répéter un certain
traitement. Il s’agit donc d’une boucle. La particularité de la boucle pour est que
le traitement dépend d’une certaine valeur i qui varie à chaque éxécution.
Exemple 3 Pour afficher toutes les cases d’un tableau, il faut afficher la case 0,
puis la 1, puis la 2, etc. Le traitement à répéter est donc « Afficher la case i », et
il est à répéter pour i variant de 0 à n − 1 (taille du tableau).
La syntaxe de la boucle pour est la suivante : pour var := a . . . b faire instruc-
tions. Cette boucle exécutera d’abord les instructions en donant à la variable var
la valeur a. Elle exécutera ensuite les instructions en donnant à var la valeur
a + 1, puis a + 2, etc jusqu’à donner à var la valeur b (pour laquelle les instruc-
tions seront aussi exécutées).
Exemple 4 Pour afficher un tableau T de n cases, on écrira :
pour i := 0 . . . n − 1 faire Afficher T [i] ;

1.2.3 Gestion de la mémoire

Afin de pouvoir introduire des structures de données dynamiques (c’est-à-dire des
structures dont la taille peut varier au cours de l’exécution du programme), comme
les listes ou les arbres, nous supposerons que nous pouvons allouer de la mémoire de
façon dynamique.
Pour rappel, les langages impératifs classiques permettent d’accéder à la mémoire
de deux façons différentes :
1. Soit via des structures statiques. Il s’agit des variables qui sont déclarées dans le
code, et dont le type et la taille sont connus au moment de la compilation. Ces
variables peuvent soit être globales (auquel cas la mémoire associée est libérée
au moment où le programme se termine), soit locales à un bloc de code (auquel
cas la mémoire est libérée quand on quitte le bloc). Il est important de remarquer
qu’un nom unique est associé à chacune des zones mémoires : le nom de la
variable correspondante.
2. Soit via des structures dynamiques. Ces structures seront stockées dans des por-
tions de mémoire, dont la taille et le type ne sont pas connus à la compila-
tion. L’allocation de la mémoire devra donc se faire au moment de l’exécution.
Comme ces emplacements mémoires ne sont pas associés à une variable, ils sont
1.2. LE PSEUDO-LANGAGE 17

anonymes. On y accédera donc par un autre mécanisme : l’adresse mémoire de

la zone concernée. En pratique, on utilise généralement un pointeur, c’est-à-dire
une variable qui peut contenir une adresse, et qui permet de manipuler la zone
concernée à travers cette adresse.
Remarquons que, même si un pointeur est une variable qui a un nom, une struc-
ture dynamique reste anonyme. En effet :
– Plusieurs pointeurs différents peuvent contenir l’adresse d’une même zone.
Ainsi, plusieurs noms sont associés à la zone.
– Comme le pointeur est une variable, il est possible de modifier son contenu
plusieurs fois tout au long de l’exécution du programme. La zone vers laquelle
le pointeur « pointe » peut donc changer, et un même nom (de pointeur) ne sera
donc pas toujours affecté à la même zone.
– Il est même possible qu’aucun pointeur ne pointe vers une zone donnée. Dans
ce cas, la zone sera tout simplement inaccessible, et la place mémoire réser-
vée sera perdue (à moins qu’un mécanisme du type garbage collector ne soit
implanté, comme dans la plupart des compilateurs JAVA).
Dans tous les cas, il convient donc de toujours bien faire la différence entre le
pointeur (une variable qui a un nom et qui contient une adresse, c’est-à-dire un
entier), et la zone référencée (ou pointée) qui est anonyme et peut être de taille
et de type arbitraire.
Dans notre pseudo-langage, les pointeurs seront déclarés dans une syntaxe à la
C++, c’est-à-dire que pour déclarer un pointeur vers une case mémoire de type T , on
déclarera en fait une variable de type T ∗.

Exemple 5 Si on veut déclarer un pointeur dont le nom est p et qui devra pointer vers
une zone mémoire capable de recevoir un élément de type Entier, on écrira :

Entier* p ;

L’allocation dynamique sera effectuée au moyen de l’opérateur new. Cet opérateur

reçoit le nom d’un type. Il réserve en mémoire la place nécessaire pour stocker une
structure du type spécifié et renvoie l’adresse de l’emplacement réservé. Il y aura donc
lieu de stocker cette adresse dans un pointeur, sous peine de ne plus pouvoir accéder à
la zone réservée.

Exemple 6 L’instruction

p := new Entier ;

crée en mémoire une zone mémoire anonyme de type Entier, dont l’adresse est stockée
dans p.

Il reste à expliquer comment on peut modifier une zone mémoire à travers un poin-
teur. Cela ne peut pas se faire par une « simple » assignation au pointeur puisque celle-ci
modifierait l’adresse qui y est stockée. Pour modifier la zone pointée par un pointeur p,
on utilise la syntaxe ∧ p. Ainsi, si p est un pointeur vers un entier et que l’on veut sto-
cker 5 dans la zone pointée, on écrira ∧ p := 5. Remarquons que cette valeur ne change
pas la valeur du pointeur, qui pointe toujours vers la même zone (et contient donc son
adresse). Il ne faut pas confondre cette instruction avec p := 5, qui stocke la valeur 5
dans le pointeur. Dans ce cas, l’adresse de la zone pointée par p avant l’assignation est
perdue, et p pointe vers la case mémoire d’adresse 5.
18 CHAPITRE 1. INTRODUCTION

Dans le cas où le pointeur p pointe vers une structure, dont on veut accéder au
champ c, par exemple, il faudrait donc écrire ∧ p.c. En effet, ∧ p est le nom de la struc-
ture elle-même (puisque c’est vers elle que p pointe), auquel il faut ajouter .c pour
accéder au champ c. Néanmoins, par souci de simplification, et puisque nous ne ma-
nipulons pas un langage qui doit, in fine être compilé, nous écrirons souvent p.c à la
place de ∧ p.c. Il est de toute façon toujours possible de retrouver le syntaxe exacte, en
regardant si on a affaire à une variable ou à un pointeur.

Exemple 7 Pour créer de façon dynamique un élément de type Etudiant et lui affecter
le numéro de matricule 123, on peut procéder de la façon suivante :
Etudiant * p ;
p := new Etudiant ;
[Link] := 123 ;
Remarquons que, dans le cas présent, p est un pointeur, contrairement à E dans l’Exemple 2.

1.3 Bibliographie
Ce cours se base en grande partie sur les premiers chapitres du livre Foundations of
Computer Science, A. Aho, J. Ullman, Computer Science Press, New York, 1992. Cet
excellent ouvrage aborde différents aspects fondamentaux de l’informatique, avec une
approche résolument scientifique. Néanmoins, il va au-delà du contenu de ce cours car
il aborde aussi les graphes ou la logique. Il en existe différentes versions dans lesquelles
les algorithmes sont présentés soit en C, soit en Pascal. Une traduction française est
publiée chez Dunod sous le titre Concepts fondamentaux de l’informatique.
L’ouvrage Introduction to algorithms 2e ed., T. Cormen, C. Leiserson, R. Rivest,
C. Stein, MIT Press, 2001 est considérée par beaucoup comme la référence en ma-
tière d’algorithmes. Le sujet est traité en profondeur, et, à nouveau, avec beaucoup de
rigueur. Une traduction en français existe également sous le titre Introduction à l’algo-
rithmique, chez Dunod (ISBN 9782100039227).
D’autres références sont données dans la bibliographie.
Chapitre 2

Itération, induction, récursivité

2.1 Introduction
Dans ce chapitre, nous allons étudier trois notions différentes mais proches : l’ité-
ration, l’induction et la récursivité.

2.1.1 Itération
Itération est synonyme de répétition, auquel on le préfère en général dans le vo-
cabulaire couramment utilisé en informatique. Tous les langages de programmation
fournissent des mécanismes permettant de répéter, ou itérer une certaine tâche. En gé-
néral, il s’agit de boucles (pour, tant que, etc). Le contenu de la boucle sera itéré
jusqu’à ce qu’une certaine condition soit remplie. Un algorithme est appelé itératif si
son traitement principal consiste en la répétition d’une certaine séquence d’instructions
(voir, par exemple, l’Algorithme 3, ci-dessous).

2.1.2 Induction
Ce terme appartient au vocabulaire des mathématiques. Le petit Robert y voit une
opération mentale qui consiste à remonter des faits à la loi, à des cas donnés. Dans le
cadre des mathématiques, l’induction est une méthode de preuve, permettant de mon-
trer qu’une proposition est vraie pour n’importe quelle valeur d’un paramètre n. Pour
ce faire, on commence par montrer que la proposition est vraie pour certaines valeurs
initiales bien choisies de n (par exemple n = 0). C’est ce qu’on appelle le « cas de
base1 ». Ensuite, on prouve que si la proposition est vraie pour certaines valeurs (dont
les valeurs initiales), alors elle est aussi vraie pour d’autres. On appelle cette partie de
la preuve le « cas inductif ». Le cas de base et le cas inductif permettent de construire
une chaîne de raisonnement montrant que la proposition est vraie pour toute valeur.
Comme exemple de cas inductif, on montre que si la proposition est vraie pour
n = k, avec k ≥ 0, elle est aussi vraie pour n = k + 1. Ainsi, nous obtenons la chaîne
de raisonnements suivante : puisque la proposition est vraie pour n = 0 (ce qui est vrai,
d’après le cas de base), elle est aussi vraie pour n = 1 (on utilise ici le cas inductif).
Maintenant que l’on sait que la proposition est vraie pour n = 1, on en déduit, grâce au
cas inductif à nouveau que la proposition est vraie pour n = 2. Elle est donc aussi vraie
1 Cela correspond à la loi, au cas donné évoqué par la définition du Petit Robert.

19
20 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ

pour n = 3, pour n = 4, etc. La proposition est donc vraie pour toute valeur entière
positive de n.
En informatique, et plus particulièrement en algorithmique dès lors qu’il s’agit de
raisonner formellement sur certaines propriétés d’algorithmes, les preuves par induc-
tion sont très souvent utilisées.

2.1.3 Récurrence
Le terme « récurrence » recouvre lui aussi une certaine idée de répétition. Dans
le cadre des mathématiques, on parle de définition par récurrence ou de définition
récursive, quand on définit un concept par rapport à lui-même.
Exemple 8 On peut définir la factorielle n! du nombre n ≥ 1 comme
n
n! = ∏ i = n × (n − 1) × (n − 2) × · · ·× 1
i=1

ce qui est la définition classique ; mais aussi comme :


n × (n − 1)! si n > 1
n! = (2.1)
1 si n = 1

La seconde définition est récursive, car dans le cas ou n > 1, on définit la factorielle
de n par rapport à une autre factorielle (en l’occurrence, celle de n − 1).

La notion mathématique de récurrence a donné lieu à une technique de program-

mation, appelée récursivité, dans laquelle un algorithme fait appel à lui-même pour
résoudre un problème.

Exemple 9 La définition récursive de la factorielle (2.1) suggère immédiatement l’Al-

gorithme 1. La définition classique, par contre, suggère plutôt une implémentation ité-
rative, comme celle de l’Algorithme 2.

Entier Facto(Entier n)
début
si n = 1 alors
retourner 1 ;
sinon
n := n × Facto(n − 1) ;
retourner n ;
fin
Algorithme 1 : Une implémentation récursive du calcul de la factorielle.

2.2 Itération et induction

Nous allons maintenant voir comment les techniques d’induction peuvent être uti-
lisées pour raisonner sur les comportements d’algorithmes itératifs. Afin de justifier
l’intérêt des techniques d’induction, qui seront introduites dans la section 2.2.1, nous
2.2. ITÉRATION ET INDUCTION 21

Entier Facto2(Entier n)
début
Entier F := n ;
Entier i := n − 1 ;
tant que i ≥ 2 faire
F := F × i ;
i := i − 1 ;
retourner F ;
fin
Algorithme 2 : Une implémentation itérative du calcul de la factorielle.

a u x

v r a i

I n s t r

F IG . 2.1 – L’ordinogramme de la boucle tant que.

allons d’abord examiner un algorithme itératif dont nous aimerions obtenir certaines
propriétés.
Dans le cadre de ce cours, nous considérerons des programmes itératifs dont le
traitement est réalisé par une boucle du type tant que. Pour rappel, un telle boucle
est composée d’une condition C, et d’une séquence d’instructions qui est répétée tant
que la condition C est vraie. Ce comportement est représenté par l’odinogramme de la
Fig. 2.1.
Remarquons d’emblée que la boucle tant que nous garantit que la condition C sera
fausse à la fin de son exécution. Cette information peut être intéressante pour raisonner
sur le comportement de la boucle, mais n’est en générale pas suffisante, comme le
montre l’exemple qui suit.
Considérons l’Algorithme 3 qui est un exemple d’algorithme itératif. Il reçoit un
tableau d’entiers T et un entier n. Il calcule la moyenne des valeurs stockées dans les n
premières cases de T . Pour ce faire, il calcule la somme de ces n première valeurs dans
22 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ

la variable S, puis renvoie nS . Le calcul de la somme est effectué de manière itérative :

à chaque tour de la boucle tant que, une nouvelle case du tableau (la case T [i]) est
examinée et ajoutée à la variable S.

Entier Moyenne(Entier T [], Entier n)

début
Entier S := 0 ;
Entier i := 0 ;
tant que i < n faire
S := S + T [i] ;
i := i + 1 ;
retourner S/n ;
fin
Algorithme 3 : Un algorithme pour calculer la moyenne des n premières valeurs
stockées dans le tableau T . On fait l’hypothèse que n > 0.

Nous aimerions nous convaincre, par un raisonnement formel et rigoureux, que

cet algorithme est correct. Il nous faut d’abord exprimer rigoureusement ce que nous
entendons par là. Intuitivement, l’algorithme est correct s’il renvoie bien la moyenne
des n premières valeurs du tableau T . Nous faisons l’hypothèse que n > 0. Autrement
dit, nous voulons prouver que :

∑n−1
i=0 T [i]
∀n > 0 : Moyenne(T, n) = (2.2)
n

Remarquons que si nous sélectionnons une valeur de n en particulier (par exemple

n = 5), il est assez simple de faire la preuve, car le nombre d’itérations de la boucle
est fixé. Mais dans ce cas, on n’a pas prouvé la correction de l’algorithme de manière
générale, c’est-à-dire pour n’importe quelle taille du tableau T .
Remarquons également que la seule chose que nous pouvons déduire directement
de la boucle tant que est que la condition i < n sera fausse à la fin de l’exécution, c’est-
à-dire que i ≥ n. En observant que la variable i n’est incrémentée que de 1 à chaque
tour de boucle, on peut même affirmer que i = n à la fin de la boucle. Mais tout cela
n’est pas suffisant pour prouver l’assertion (2.2).
Pour prouver la correction de cet algorithme (pour n’importe quel n), nous devons
essentiellement prouver que la variable S contient bien ∑n−1 i=0 T [i] à la fin de la boucle.
Pour ce faire, il est nécessaire d’utiliser un raisonnement par induction, comme suggéré
dans le paragraphe introductif de ce chapitre.

2.2.1 Raisonnement par induction

Afin d’introduire la notion de preuve par induction, nous allons considérer l’exemple
suivant :
n
∀n ≥ 0 : ∑ 2i = 2n+1 − 1 (2.3)
i=0

Nous avons affaire à la proposition ∑ni=0 2i = 2n+1 − 1 qui doit être vraie pour n’importe
quelle valeur positive de n. Nous allons prouver ce fait par induction.
2.2. ITÉRATION ET INDUCTION 23

Canevas d’une preuve par induction

Une preuve par induction comprend deux parties, appelées cas :
1. La première est le cas de base, dans laquelle la proposition est prouvée directe-
ment pour certaines valeurs bien choisies du paramètre.
2. La seconde est le cas inductif, où l’on prouve que, si la proposition est vraie pour
certaines valeurs du paramètre, alors elle l’est pour d’autres valeurs.
À l’aide du cas du base et du cas inductif, il doit être possible de prouver que la propo-
sition est correcte pour n’importe quelle valeur de n. Il s’agit donc de bien les choisir.
Dans le cadre de notre exemple, on choisira de montrer que :
Cas de base la proposition est vraie pour n = 0.
Cas inductif si la proposition est vraie pour n = k, où k ≥ 0, alors elle l’est pour
n = k + 1.
Avec ces deux cas, on peut en effet montrer que la proposition est vrai pour n’im-
porte quel n. En effet, elle est vraie pour n = 0 (par le cas de base), donc elle est vraie
pour n = 1 (cas inductif), ce qui implique qu’elle est vraie pour n = 2 (cas inductif),
etc.
Il est important de noter que, dans le cas inductif, on tient un raisonnement sous
hypothèse : on suppose que la proposition est vraie pour n = k et on en déduit qu’elle
l’est pour n = k + 1. L’hypothèse « la proposition est vraie pour n = k » est appelée
hypothèse d’induction.

Remarquons qu’on aurait pu prouver également (par exemple) :

Cas de base la proposition est vraie pour n = 0, pour n = 1 et pour n = 2.
Cas inductif si la proposition est vraie pour n = k, où k ≥ 2, alors elle l’est pour
n = k + 1.
Mais cela allonge inutilement le cas de base.

Par contre, les découpes suivantes ne sont pas suffisante pour prouver que la pro-
position est vraie pour tout n :
Cas de base la proposition est vraie pour n = 5.
Cas inductif si la proposition est vraie pour n = k, où k ≥ 5, alors elle l’est pour
n = k + 1.
Cas de base la proposition est vraie pour n = 0.
Cas inductif si la proposition est vraie pour n = k, où k ≥ 0 est un nombre pair, alors
elle l’est pour n = k + 2.
En effet, dans le premier cas, les valeurs 0, 1, 2, 3 et 4 ne sont pas couvertes. Dans
le second cas, les valeurs impaires de n ne sont pas couvertes.

Nous pouvons maintenant, à titre d’exemple, écrire la preuve complète de (2.1) :

Exemple 10 Cas de base n = 0. Cela revient à prouver que :
0
∑ 2i = 21 − 1
i=0

ce qui est équivalent à :

20 = 21 − 1
Or, 20 = 1 et 21 − 1 = 2 − 1 = 1. La proposition est donc vraie pour n = 0.
24 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ

Cas inductif Supposons que la proposition est vraie pour n = k. Cela veut dire que
(hypothèse d’induction) :

k
∑ 2i = 2k+1 − 1 (2.4)
i=0

Montrons que la proposition est vraie aussi pour n = k + 1, c’est-à-dire que :

k+1
∑ 2i = 2k+2 − 1
i=0

Or, ∑k+1
i=0 2 peut se réécrire en : ∑i=0 2 + 2
i k i k+1 . Donc on doit montrer que :

k
∑ 2i + 2k+1 = 2k+2 − 1
i=0

L’hypothèse d’induction (2.4) nous permet de remplacer ∑ki=0 2i par 2k+1 − 1.

On doit donc montrer que :

2k+1 − 1 + 2k+1 = 2k+2 − 1

En réécrivant le membre de gauche, on se rend compte que :

2k+1 − 1 + 2k+1 = 2k+1 + 2k+1 − 1

= 2 × (2k+1) − 1
= 2 × (2 × 2 × · · ·× 2) − 1
| {z }
k+1 fois
= 2 × 2 × · · ·× 2 −1
| {z }
k+2 fois

= 2k+2 − 1

En utilisant l’hypothèse que la proposition est vraie pour n = k, on a donc montré

qu’elle était vraie pour n = k + 1. 

Quelques commentaires s’imposent au sujet de cette preuve :

1. Remarquez que nous avons veillé à bien faire apparaître la découpe en cas de
base et cas inductif. C’est important pour faciliter la compréhension du lecteur.
2. Remarquez que nous avons bien précisé quelle est l’hypothèse d’induction. Cela
doit toujours apparaître clairement dans le cas inductif.
3. Observez comment nous avons transformé ∑k+1 i=0 2 en ∑i=0 2 + 2
i k i k+1 , afin de

pouvoir ensuite se servir de l’hypothèse d’induction. C’est le point crucial de

la preuve, car c’est là qu’on ramène le cas n = k + 1 au cas n = k, ce qui nous
permet de construire notre chaîne de raisonnements.
D’autres exemples sont donnés au cours.
2.3. PREUVES DE PROGRAMMES 25

2.3 Preuves de programmes

Montrons maintenant comment les techniques de preuves développées dans la sec-
tion précédente permettent de raisonner sur des programmes itératifs. Ce lien est assez
naturel, car pour prévoir l’effet de k itérations d’une boucle donnée, il faut en général
connaître l’effet de k − 1 itérations. En effet, la ke itération s’exécute après les k − 1
première itérations, et son effet dépend donc des valeurs des variables après k − 1 itéra-
tions. On retrouve là l’esprit des preuves par induction : pour prouver qu’une certaine
proposition est vraie après un nombre arbitraire d’itérations d’une certaine boucle, on
montrera d’abord que la proposition est vraie avant la première itération ; puis on mon-
trera que si la proposition est vraie pour k − 1 itérations, elle l’est aussi pour k itérations.
Considérons à nouveau l’Algorithme 3. Pour rappel, nous aimerions prouver la
proposition (2.2). Pour ce faire, nous allons prouver que :
Après k itérations de la boucle tant que, nous avons : i = k et S = ∑k−1
j=0 T [ j]
Autrement dit, la variable i compte le nombre d’itérations effectuées par la boucle, et
S contient la somme des k premiers termes du tableau T . Cette affirmation exprime
donc la façon dont l’algorithme progresse : en considérant, à chaque tour de boucle,
une nouvelle case du tableau T , et en ajoutant le contenu de cette case à la variable S.
Ainsi, au bout de n tour de boucles (quand i = n), S contiendra bien la somme des cases
T [0], T [1], . . . , T [n − 1].
Remarquons que cette assertion doit être vraie pour tout k ≥ 0. Remarquons que
dans le cas où k = 0, notre assertion devient « Après 0 itérations de la boucle. . . », ce
qui doit être compris comme « Avant l’exécution de la boucle ».
Théorème 1 Pour tout k ≥ 0 : après k itérations de la boucle tant que de l’Algo-
rithme 3, nous avons : i = k et S = ∑k−1
j=0 T [ j].
Preuve. La preuve est par induction sur k.
Cas de base k = 0 cela revient à prouver que i = 0 et S = 0 avant l’exécution de la
boucle, ce qui est trivialement vrai en raison des deux initialisations en début
d’algorithme.
Cas inductif k = ℓ ≥ 1 l’hypothèse d’induction est la suivante. Après ℓ − 1 itérations
de la boucle tant que de l’Algorithme 3, nous avons : i = ℓ − 1 et S = ∑ℓ−2
j=0 T [ j].
La ℓe itération de l’algorithme a pour effet d’ajouter la valeur stockée dans T [i]
à S (avec i = ℓ − 1, par hypothèse d’induction), puis d’incrémenter i de 1. Donc,
à la fin de la ℓe itération, nous avons :
ℓ−2 ℓ−1
S= ∑ T [ j] + T [ℓ − 1] = ∑ T [ j]
j=0 j=0

et
i = ℓ−1
Ce qui prouve le théorème.

Ayant prouvé ce théorème, nous sommes maintenant en mesure de conclure que
notre algorithme est bien correct. En effet, nous avons déjà observé que la variable i
prend la valeur n lorsque la boucle tant que se termine. Donc, d’après le Théorème 1,
S = ∑n−1
j=0 T [ j] (nous pouvons remplacer i et k par n, puisque i = n et i = k). Comme la
fonction renvoie S/n, nous avons prouvé qu’elle calcule bien la moyenne des n premiers
éléments du tableau T .
26 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ

2.3.1 Notion d’invariant de boucle

Si nous observons attentivement le Théorème 1, nous constatons qu’il nous fournit
une information sur les valeurs des variables de l’Algorithme 3, à des points précis de
l’exécution de la boucle tant que. Ces points dans l’exécution sont : avant l’exécution
de la boucle et après chaque itération de la boucle. Autrement dit : à chaque fois que
l’algorithme aborde l’instruction qui évalue la condition i < n (ce que nous appellerons
plus simplement « le début de la boucle »). Ces instants sont ceux qui correspondent à
la boule noire sur la Fig 2.1.
Le Théorème 1 nous apprend qu’à ces instants, la variable i contient exactement le
nombre k d’itérations qui ont été effectuées, et que la variable S contient la somme des
k = i premières cases du tableau. Ceci peut être résumé par :
i−1
S = ∑ T [ j] (2.5)
j=0

Une assertion qui est toujours vraie en début de boucle est appelée un invariant de
la boucle. C’est le cas de la formule (2.5). Les invariants représentent un outil précieux
pour expliquer le comportement d’une boucle (et donc pour prouver la correction de la
boucle).
Remarquons qu’il existe plusieurs invariants possibles pour une boucle donnée. En
effet, il est également toujours vrai, en début de boucle, que S = ∑i−1 j=0 T [ j] ∧ i ≤ n,
ce qui est plus précis que (2.5). Il est également toujours vrai, en début de boucle,
que 1 + 1 = 2. En effet, cette dernière assertion est toujours vraie (indépendemment
de la boucle), et est donc aussi un invariant de la boucle tant que de l’Algorithme 3.
L’inconvénient est que ce dernier invariant ne nous apprend rien sur les variables de
l’Algorithme 3, et nous permettra donc pas de raisonner à propos de ce dernier. Il
importe donc de choisir un invariant suffisamment précis que pour pouvoir raisonner
sur l’algorithme considéré.
Remarquons également que l’invariant (2.5) nous permet de prouver la correction
de l’Algorithme 3. En effet, à la fin de l’exécution de la boucle, nous savons que i = n.
En remplaçant i par n dans 3, nous obtenons que S = ∑n−1 j=0 T [ j] à la fin de la boucle.

Dans l’exemple que nous avons considéré, nous avons d’abord prouvé le Théo-
rème 1, que nous avons ensuite ré-exprimé sous forme d’invariant. Cette démarche a
été adoptée afin d’exposer clairement les raisonnements à l’œuvre, et d’introduire ai-
sément la notion d’invariant. En pratique, on procède en général de façon quelque peu
différente. Imaginons qu’on veuille prouver qu’une certaine assertion P est vraie à la
fin d’une boucle.
1. On commence par « deviner » un invariant I de la boucle, qui exprime le plus
précisément possible le comportement de celle-ci.
2. On prouve que I est bien un invariant. Ceci se fait par induction, dans le même
esprit que la preuve du Théorème 1 :
(a) On montre que I est vrai initialement (« au bout de 0 itérations »).
(b) On montre que si I est vrai après k itérations, il est aussi vrai après k + 1
itérations.
Ainsi, on est certain que I est vrai au bout d’un nombre quelconque d’itérations,
ce qui en fait bien un invariant.
2.3. PREUVES DE PROGRAMMES 27

3. On montre que dès qu’on sort de la boucle (c’est-à-dire dès que la condition C de
la boucle est fausse), l’invariant garantit que P est vrai. Autrement dit, on montre
que I ∧ ¬C ⇒ P.
Si on n’arrive pas à effectuer le dernier point, c’est soit parce que P n’est pas vraie
à la fin de la boucle (on a donc trouvé un bug. . .), soit parce que l’invariant I n’est pas
assez précis. Il faut alors en trouver un autre et recommencer.

2.3.2 Un exemple de preuve par invariant

Illustrons cette façon de procéder sur l’Algorithme 4. Celui-ci est censé parcou-
rir les n premières cases du tableau T et renvoyer le minimum des valeurs stockées
dans ces cases. Pour ce faire, il parcourt les n premières cases du tableau T tout en
maintenant une variable M qui contient la plus petite valeur rencontrée jusque là. Le
traitement de chaque nouvelle case T [i] consiste à la comparer à M et à mettre M à jour
si nécessaire (c’est-à-dire sir T [i] < M).

Entier Minimum(Entier T [], Entier n)

début
Entier M := T [0] ;
Entier i := 1 ;
tant que i < n faire
si T [i] < M alors
M := T [i] ;
i := i + 1 ;
retourner M ;
fin
Algorithme 4 : Un algorithme qui renvoie la valeur minimum stockée dans les n
premières cases du tableau T .

On aimerait prouver que Minimum renvoie bien le minimum de n premières cases

de T , c’est-à-dire que :

Minimum(T, n) = min T [ j] (2.6)

0≤ j≤n−1

Afin de réaliser cette preuve, nous proposons l’invariant (2.6) qui formalise l’idée
développée ci-dessus. Cet invariant spécifie que M contient le minimum des cases de
T qui ont été explorées. Ces cases sont celles dont l’indice est compris entre 0 et i − 1.

M = min T [ j] ∧ i≤n (2.7)

0≤ j≤i−1

Prouvons qu’il s’agit bien d’un invariant :

Théorème 2 L’assertion (2.7) est un invariant de la boucle tant que de l’Algorithme 4.

Preuve. La preuve est par induction sur le nombre k d’itérations de la boucle.

Cas de base : k = 0 Avant l’exécution de la boucle, nous avons i = 1. L’assertion (2.7)
devient : M = min0≤ j≤0 T [ j] ce qui est équivalent à M = min{T [0]} = T [0]. Ceci
est vrai grâce à l’initialisation de M.
28 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ

Cas inductif : k = ℓ ≥ 1 L’hypothèse d’induction spécifie qu’au bout de ℓ − 1 itéra-

tions de la boucle, l’invariant est respecté. Observons2 qu’on bout de ℓ − 1 ité-
rations, la variable i prend la valeur ℓ. L’hypothèse d’induction garantit donc
qu’au bout de ℓ − 1 itérations, M = min0≤ j≤ℓ−1 T [ j] ∧ i ≤ n. Une fois entré
dans la boucle, on sait que i < n car la condition est vérifiée. On a donc :
M = min0≤ j≤ℓ−1 T [ j] ∧ i < n ∧ i = ℓ. On a ensuite deux possibilités :
1. Soit on entre dans le si. Dans ce cas, on sait que T [i] < M, autrement dit
que T [ℓ] < min0≤ j≤ℓ−1 . Ceci veut dire que T [ℓ] est le minimum des cases
de 0 à ℓ (inclus). Comme on assigne T [i] = T [ℓ] à M, on obtient M =
min0≤ j≤ℓ T [ j]. Par ailleurs i reste inchangé, et donc on a aussi i < n ∧ i = ℓ.
2. Soit on n’entre pas dans le si. Dans ce cas, T [i] ≥ M, autrement dit : T [ℓ] ≥
min0≤ j≤ℓ−1. Donc T [i] ne permet pas de modifier le minimum, et on a
bien M = min0≤ j≤ℓ T [ j]. Par ailleurs, i reste inchangé, et donc on a aussi
i < n ∧ i = ℓ.
Dans les deux cas, on arrive à la même conclusion : M = min0≤ j≤ℓ T [ j] ∧ i <
n ∧ i = ℓ.
Le tour de boucle se termine par l’incrémentation de i, et on a donc, à la fin de la
ℓe itération :
M = min T [ j] ∧ i ≤ n ∧ i = ℓ + 1
0≤ j≤ℓ

Ce qui est équivalent à (on peut remplacer ℓ par i − 1) :

M = min T [ j] ∧ i ≤ n
0≤ j≤i−1


On peut maintenant prouver que l’algorithme est correct. En effet, quand on sort de
la boucle, on sait que i ≥ n. À ce même moment, l’invariant M = min0≤ j≤i−1 T [ j]∧i ≤ n
reste valable. Donc, à la sortie de la boucle, on a3 : i ≥ n ∧ M = min0≤ j≤i−1 T [ j] ∧ i ≤ n.
La conjonction de i ≥ n et i ≤ n implique que i = n. On a donc :

M= min T [ j] ∧ i = n
0≤ j≤n−1

ce qui implique, en particulier que M (la valeur renvoyée) contient le minimum des n
premières cases du tableau T .

2.4 Récursivité
Comme nous l’avons déjà mentionné dans l’introduction de ce chapitre, une défini-
tion récursive est une définition qui fait référence à elle-même ; dans laquelle l’objet à
définir est défini en fonction d’un autre objet sur lequel la même définition s’applique.
Nous avions fourni l’exemple de la factorielle du nombre n : si n = 1, alors la factorielle
de n est 1, sinon, la factorielle de n est la factorielle de n − 1 multipliée par n (ce que
nous avions exprimé sous une forme plus « matheuse » ci-dessus).
Pourquoi une telle définition a-t-elle du sens ? Pour le comprendre, calculons la
factorielle de 5, à l’aide de cette définition :

5! = 4! × 5
2 Ceci pourrait être prouvé rigoureusement.
3 C’est ce que nous avions désigné par I ∧ ¬C plus haut.
2.4. RÉCURSIVITÉ 29

or, par la même définition, nous avons :

4! = 3! × 4

Donc :

5! = 3! × 4 × 5

En appliquant le même raisonnement, nous obtenons :

5! = 2! × 3 × 4 × 5
5! = 1! × 2 × 3 × 4 × 5

Nous retombons donc finalement sur le cas 1!, qui vaut 1, par définition. Donc :

5! = 1×2×3×4×5
= 120

Ce qu’il importe de remarquer dans ce développement, c’est qu’on peut, à un cer-

tain moment, invoquer le cas 1!, dont la définition nous est donnée directement (on
n’a pas besoin de calculer une autre factorielle pour déduire 1!). C’est cette propriété
importante qui fait que la définition récursive de la factorielle a du sens. Sans cela, on
pourrait en être réduit à une définition qui se « mord la queue » comme dans l’exemple
suivant :

Exemple 11

 5
si x = 0
f (x) = 2 × f 2x si x est pair et 6= 0

f (2 × x) − 1 si x est impair

Dans le cas f (0), la fonction est bien définie. Par contre, dans le cas f (2), par exemple,
la définition nous dit de calculer 2 × f (1), et f (1) = f (2)− 1. . . La valeur f (2) est donc
définie en fonction de f (1), qui est définie en fonction de f (2). Cette définition n’a pas
de sens.

Un autre exemple de définition récursive classique et donnée par le plus grand

diviseur commun, ou pgcd. En effet, si i > j, alors :

j si i mod j = 0
pgcd(i, j) =
pgcd( j, i mod j) sinon

Remarquons finalement que cette idée a donné lieu à diverses boutades, notamment
dans le choix des noms des projets dans la communauté open source. L’acronyme GNU,
par exemple, signifie officiellement4 GNU is not Unix. . . Un expert en pédagogie a
un jour décrété que « Pour comprendre la récursivité, il faut d’abord comprendre la
récursivité », etc. . .
4 Voir http ://[Link]/gnu/[Link].
30 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ

2.4.1 Récursivité et induction

Comme on l’a vu dans au cours des paragraphes précédent, une définition récursive
comprend un ou plusieurs cas généraux qui sont proprement récursifs (par exemple :
n! = n × (n − 1)!), et un ou plusieurs cas de base qui ne sont pas récursifs, et auxquels
on aimerait se ramener (par exemple : 1! = 1).
On retrouve donc l’idée de « tout ramener à des cases de base bien définis », déjà
présente dans les preuves par induction. Ces deux concepts sont en effet liés, et il
est possible de prouver des propriétés de définition récursives à l’aide de l’induction,
comme le montre l’exemple suivant :

Exemple 12 Prouvons le théorème suivant, qui indique que les deux définitions (non-
récursive et récursive) de la factorielle sont équivalentes. La fonction f1 calcule la
factorielle par la définition non-récursive, et la fonction f2 la calcule par la définition
récursive.

Théorème 3 Pour tout n ≥ 1, f1 (n) = f2 (n), avec :

n
f1 (n) = ∏i
i=1

et

n × f2(n − 1)! si n > 1
f2 (n) =
1 si n = 1

Preuve. Par induction sur n.

Cas de base : n = 1 Dans ce cas, on a f1 (1) = 1 et f2 (1) = 1.
Cas inductif : n = k > 1 L’hypothèse d’induction nous garantit que pour n = k − 1
f1 (n) = f2 (n). Dans le cas où n = k, nous avons :

f2 (n) = f2 (k) = k × f2 (k − 1)

Or, par hypothèse d’induction, f2 (k − 1) = f1 (k − 1). Donc :

f2 (n) = f2 (k) = k × f1 (k − 1)

Par ailleurs, f1 (k − 1) = 1 × 2 × 3 × . . .× (k − 1), par définition. Donc :

f2 (n) = f2 (k)
= k × 1 × 2 × 3 × . . .× (k − 1)
= 1 × 2 × 3 × . . .× (k − 1) × k
n
= ∏i
i=1
= f1 (k)
= f1 (n)


2.4. RÉCURSIVITÉ 31

2.4.2 Fonctions récursives

La notion de récursivité telle qu’appliquée aux définitions mathématiques a donné
lieu à une technique de programmation, la récursivité, dans laquelle un algorithme fait
appel à lui-même pour résoudre un programme. Cela a déjà été illustré par l’Algo-
rithme 1, qui calcule la valeur n! de façon récursive.
Comme dans le cas des définitions récursive, une fonction récursive peut poser
problème si elle n’exécute jamais son cas de base. Par exemple, l’Algorithme 5 (qui
implémente la fonction f (x) de l’Exemple 11 ci-dessus) ne renverra jamais aucune
valeur pour x = 2, par exemple. En écrivant une fonction récursive, il faut donc toujours
s’assurer que celle-ci finira par atteindre un de ses cas de base, et ceci, quelle que soit
la valeur avec laquelle on l’appelle.

Entier FonctionRec(Entier x)
begin
si x = 0 alors
retourner 5 ;
sinon si x mod 2 = 0 alors
Entier y := FonctionRec(x/2) ;
retourner 2 × y ;
sinon
Entier y := FonctionRec(2 × x) ;
retourner y − 1 ;
end
Algorithme 5 : Une fonction récursive problématique. . .

L’utilisation de la récursivité en algorithme sera extensivement illustrée dans la

suite du cours.

Preuves de programmes récursifs

Il est possible de raisonner formellement au sujet de programmes récursifs. Par
exemple, on peut prouver que l’Algorithme 1 renvoie toujours 1 × 2 × · · ·× n :
n
∀n ≥ 1 : Facto(n) = ∏ i
i=1

Cette preuve se fait par induction est est essentiellement la même que celle du Théo-
rème 3.
D’autres exemples seront développés au cours.
32 CHAPITRE 2. ITÉRATION, INDUCTION, RÉCURSIVITÉ
Chapitre 3

La complexité algorithmique

3.1 Introduction
Le but d’un algorithme est de fournir une solution automatisable à un problème
donné, nous l’avons dit dans le chapitre d’introduction. Mais fournir une solution cor-
recte n’est pas suffisant, encore faut-il que l’algorithme proposé se montre efficace. En
effet, quelle est l’utilité d’un algorithme correct mais qui n’est pas capable de fournir
une réponse en moins de dix ans, même quand il est exécuté sur les meilleurs ordina-
teurs du marché ?
Nous aimerions donc disposer d’une mesure de l’efficacité d’un algorithme. Celle-
ci nous permettrait, étant donné plusieurs algorithmes résolvant le même problème, de
comparer leurs efficacités respectives et de choisir le plus adapté au cas de figure qui
nous intéresse.
C’est l’objet de la complexité algorithmique, que nous appellerons tout simplement
complexité dans ce cours1. La complexité d’un algorithme est une mesure de son effi-
cacité, et un algorithme aura une complexité d’autant plus élevée qu’il sera inefficace.
Tentons de préciser quelque peu ces notions. . .

3.2 Notion d’efficacité

Nous considérerons qu’un algorithme est d’autant plus efficace qu’il consomme peu
de ressources. Les ressources consommées par un algorithme sont typiquement :
– Le temps (processeur)
– La mémoire
– L’espace disque
– Le nombre d’accès au disques
– ...
Dans le cadre de ce cours, nous nous restreindrons au temps. Néanmoins, les techniques
et résultats développés ici seront aisément adaptables à d’autres types de ressources.

1 Remarquez cependant qu’il existe d’autres notions de complexité, tout à fait différentes, comme la com-

plexité d’un problème, ou la complexité de Kolmogorov.

33
34 CHAPITRE 3. LA COMPLEXITÉ ALGORITHMIQUE

3.2.1 Mesure du temps de calcul

La question « Quel est le temps consommé par tel algorithme » n’a, telle quelle,
aucun sens. En effet, le temps de calcul dépend :
1. De la machine sur laquelle l’algorithme est exécuté. Un vénérable i386 est beau-
coup plus lent que la dernière génération de Pentium. . .
2. De la quantité de données à traiter. Par exemple, un algorithme aura certainement
besoin de plus de temps pour calculer la somme de 10.000 nombres que pour
calculer la somme de 10 nombres.
Comme conséquence du premier de ces deux points (nous reviendrons sur le second
un peu plus tard), nous pouvons exclure de mesurer l’efficacité d’un algorithme en
effectuant des tests où l’on chronométrerait le temps d’exécution dans différents cas
de figure. Une telle mesure dépendrait trop du matériel utilisé pour les tests, et ne
refléterait pas fidèlement une caractéristique de l’algorithme.
Pour illustrer la technique que nous allons utiliser pour évaluer l’efficacité d’un
processeur, nous pouvons considérer le problème suivant :
Lire une valeur n en entrée, et afficher à l’écran : les n couples (i, i) pour i
variant de 1 à n.
Par exemple, si on lit sur l’entrée la valeur 5, l’algorithme doit afficher :
1 1
2 2
3 3
4 4
5 5
Pour résoudre ce problème nous proposons les algorithmes 6 et 7.

début
i := 1 ;
lire n ;
tant que i ≤ n faire
j := 1 ;
tant que j ≤ n faire
si i = j alors Afficher i j;
j := j + 1;
i := i + 1;
fin
Algorithme 6 : Un algorithme pour afficher toutes les paires (i, i) avec 1 ≤ i ≤ n.

Dans le cas de l’algorithme 6, les variables i et j prennent des valeurs qui ne seront
pas affichées. En effet, initialement, i vaut 1 et j vaut 1. Ces valeurs seront affichées
puisque i = j. Ensuite, j sera incrémenté successivement à 2, 3,. . . jusqu’à atteindre n.
Toutes ces valeurs ne seront pas affichées puisque nous aurons i 6= j (autrement dit, le
couple (i, j) prendra les valeurs (1, 2), (1, 3),. . . (1, n), qui ne seront pas affichées). On
voit donc que toute une série d’opérations sont inutiles.
L’algorithme 7, par contre, s’arrange pour maintenir i = j et on économise ainsi
une boucle et un test2 .
2 Comme i et j ont toujours la même valeur, on aurait pu se passer d’une des deux variables. Nous avons

choisi de les garder pour simplifier la comparaison.

3.2. NOTION D’EFFICACITÉ 35

début
i := 1 ;
j := 1 ;
lire n ;
tant que i ≤ n faire
Afficher i j ;
j := j + 1 ;
i := i + 1 ;
fin
Algorithme 7 : Un autre algorithme pour afficher toutes les paires (i, i) avec 1 ≤ i ≤ n.

Il est clair que le second algorithme est intrinsèquement meilleur que le premier,
car il fait l’économie de calculs inutiles à l’affichage, et cette économie est totalement
indépendante de la machine choisie pour l’exécution du programme. C’est ce genre
d’observations que nous aimerions capturer dans la notion de complexité.

3.2.2 Compter le nombre d’étapes

Ces considérations nous amènent à mesurer le temps d’exécution d’un algorithme
en nombre d’étapes de calcul élémentaires effectuées. Autrement dit, on considérera
qu’une étape de calcul prend une unité de temps.
Nous prendrons la convention que les instructions suivantes correspondent à une
étape élémentaire :
– Une assignation
– Une opération arithmétique (addition, soustraction,. . .)
– Une comparaison de deux variables (≤, ≥,. . .)
– Une lecture sur l’entrée
– Un affichage

Exemple 13 L’opération i := (i+3)∗2 consomme trois étapes, car l’évaluation de (i+

3) ∗ 2 comprend deux opérations arithmétiques, qui consomment une étape chacune, et
l’assignation consomme une étape.

Nous pouvons immédiatement observer que le nombre d’instructions élémentaires

consommées par un algorithme peut dépendre des données en entrée, et plus préci-
sément de leur quantité. Par exemple, considérons les algorithmes 8 et 9. Il est clair
que l’algorithme 8 consomme deux unités de temps, et ce, quelle que soit la valeur n
lue sur entrée (car l’exécution de l’algorithme 8 ne dépend pas de n). Par contre, l’al-
gorithme 9 exécutera les instructions « Afficher n » (une opération) et i := i + 1 (une
opération), ainsi que le test « i ≤ n » (une opération également) exactement n fois. Son
temps d’exécution dépendra donc de n : il vaut 3n + 2.

début
Lire n ;
Afficher n ;
fin
Algorithme 8 : Un algorithme dont le nombre d’étapes de calcul est constant.
36 CHAPITRE 3. LA COMPLEXITÉ ALGORITHMIQUE

début
lire n ;
i := 1 ;
tant que i ≤ n faire
Afficher n ;
i := i + 1 ;
fin
Algorithme 9 : Un algorithme dont le nombre d’étapes de calcul dépend de la valeur
n lue en entrée.

Un problème similaire se présente dans le cas où l’on a un test. Considérons l’Al-

gorithme 10. Dans le cas où l’utilisateur entre la valeur 1 pour n, l’algorithme consom-
mera 3 étapes (lecture de n, test et affichage). Sinon, l’algorithme consommera 3 + 3n
étapes (le 3n + 2 étapes qui sont communes à l’Algorithme 9, plus le test). Dans le
premier cas, l’Algorithme 10. est donc beaucoup plus efficace que dans le second.
Or, nous voulons donner une complexité unique pour cet algorithme. Le choix gé-
néralement adopté dans ce cas de figure consiste à être pessimiste et à fournir le pire
cas. Dans le cadre de ce cours, nous ferons toujours ce choix. On dira donc que cet
algorithme consomme 3n + 3 étapes.

début
lire n ;
si n = 1 alors
Afficher n ;
sinon
i := 1 ;
tant que i ≤ n faire
Afficher n ;
i := i + 1 ;
fin
Algorithme 10 : Un algorithme dont le nombre d’étapes de calcul est parfois
constant, parfois linéaire.

De manière générale, la difficulté dans l’évaluation du nombre d’étapes requises par

un algorithme se trouvera dans l’évaluation du nombre d’étapes consommées par ses
boucles, car il ne sera pas toujours facile de voir combien de fois la boucle s’exécute.

On peut résumer les considérations de cette section par les quelques règles ci-
dessous. Celles-ci sont souvent3 suffisantes pour évaluer le nombre d’étapes néces-
saires à l’exécution d’un algorithme.
Dans les règles qui suivent I, I1 et I2 sont des blocs d’instructions, et T est un test.
1. Si I1 consomme k1 étapes et I2 consomme k2 étapes, la séquence I1 ; I2 consomme
k1 + k2 étapes.
2. Si I consomme k étapes, T consomme ℓ étapes, alors la boucle TantQue(T ){I}
consomme n × (ℓ + k) + ℓ étapes, où n est le nombre d’exécutions de la boucle.
3
Mais pas toujours : voir les exemples donnés au cours. Pour évaluer correctement le nombre d’étapes
consommé par un algorithme, il est donc impératif d’en comprendre le fonctionnement dans les moindres
détails.
3.3. LA NOTION DE GRAND O 37

Remarquons que les ℓ étapes supplémentaires viennent du fait qu’il faut exécuter
une fois supplémentaire le test pour se rendre compte qu’on doit sortir de la
boucle.
3. Si I1 consomme k1 étapes, I2 consomme k2 étapes et T consomme ℓ étapes,
l’instruction If(T ){I1 }Sinon{I2 } consomme ℓ + max{k1 , k2 } étapes.

3.3 La notion de grand O

Nous sommes maintenant capables de caractériser le nombre d’étapes (toujours au
pire cas, selon ce que nous avons dit plus haute) nécessaires à un algorithme pour ef-
fectuer son traitement. Nous allons maintenant introduire la notion de grand O, qui va
nous permettre d’exprimer ces temps d’exécution de manière plus uniforme, et d’ef-
fectuer des simplifications.

3.3.1 Intuition
Pour ce faire, considérons l’exemple suivant. Supposons qu’on veuille comparer
trois algorithmes, qui doivent traiter des données de taille n. Pour réaliser ce traitement :
1. le premier algorithme nécessite n4 + 3n étapes.
2. le second algorithme nécessite 2n3 + n2 étapes.
3. le troisième algorithme nécessite n3 + 3n étapes.
Le graphique de la Fig. 3.1 montre l’évolution de ce nombre d’étapes en fonction de
la valeur de n (pour n compris entre 0 et 5). On a également indiqué le nombre d’étapes
que prendrait un algorithme nécessitant n3 étapes. On constate que les comportements
des algorithmes 2 et 3 sont très proches l’un de l’autre, et très proches de n3 , alors que
l’algorithme 1 se démarque. Cette tendance est beaucoup plus nette si on regarde des
grandes valeurs de n, comme on peut le voir sur la Fig. 3.2 : les courbes des algorithmes
2 et 3, et la courbe de n3 se confondent, l’algorithme 1 explose.
Sur base de ces observations, nous pouvons dire que les algorithmes 2 et 3 se com-
portent grosso modo de la même manière, c’est-à-dire en consommant de l’ordre de n3
étapes, alors que l’algorithme 1 est beaucoup moins efficaces et consomme de l’ordre
de n4 étapes. Remarquons qu’il s’agit à chaque fois du terme de poids le plus élevé du
polynôme (sans la constante).
La notion de grand O nous permet de formaliser cela. Nous dirons que 2n3 + n2
et n3 + 3n sont en grand O de n3 , tandis que n4 + 3n est en grand O de n4 . Les deux
derniers algorithmes seront donc considérés comme aussi performants l’un que l’autre,
alors que le premier sera vu comme moins performant.

3.3.2 Définition formelle

La définition formelle est la suivante :

Définition 1 Soient f (x) et g(x)
deux fonctions réelles. On dit que f est en grand Ode
g, ce qui est noté f (x) = O g(x) , si et seulement s’il existe deux constantes x0 ≥ 0 et
k ≥ 0 telles que :
∀x > x0 : 0 ≤ f (x) ≤ k × g(x)
38 CHAPITRE 3. LA COMPLEXITÉ ALGORITHMIQUE

A l g o r i t h m e
1

6
0 0

x ^

A l g o r i t h m e
2

A l g o r i t h m e
3

5 0 0

4 0 0

3 0 0

2 0 0

1 0 0

0 1 2 3 4 5

F IG . 3.1 – Comparaison de polynômes de degrés 3 et 4 (petite échelle).

1 x 1 0 8 A l g o r i t h m e

x ^ 3

A l g o r i t h m e

A l g o r i t h m e

8 x 1 0
7

6 x 1 0
7

4 x 1 0 7

2 x 1 0 7

0 2 0 4 0 6 0 8 0 1 0 0

F IG . 3.2 – Comparaison de polynômes de degrés 3 et 4 (grande échelle).

3.3. LA NOTION DE GRAND O 39

Intuitivement, cette définition dit que la fonction g(x) (multipliée par une certaine
constante k) est toujours au-dessus de la fonction f (x), si on néglige les valeurs initiales
de x (celles qui sont ≤ x0 ). La fonction g(x) peut donc être vue comme une borne
supérieure de la fonction f (x), et ce, pour des valeurs de x suffisamment grandes, ce
qui est bien compatible avec notre choix de faire des analyses au pire cas.
Regardons quelques exemples :

Exemple 14 1. La fonction f (x) = 2x3 + x2 est en O(x3 ). Pour montrer cela, il

suffit de trouver les deux constantes x0 et k de la définition. On peut proposer,
par exemple, k = 3 et x0 = 0. En effet :

∀x > x0 : 0 ≤ f (x) ≤ k × g(x)

ssi
∀x > 0 : 0 ≤ 2x3 + x2 ≤ 3x3
ssi
∀x > 0 : 0 ≤ 2x3 + x2 − 2x3 ≤ 3x3 − 2x3
ssi
∀x > 0 : 0 ≤ x2 ≤ x3

ce qui est vrai. En effet, pour tout nombre x strictement positif, son carré est
positif et inférieur ou égal à son cube.
2. La fonction f (x) = 2x3 + x2 est aussi en O(x4 ), O(x5 ), etc. C’est bien cohérent
avec notre intuition qui consiste à voir le O comme une borne supérieure : il est
clair que x4 est une borne supérieure de x3 . Or, 2x3 + x2 est en O(x3 ). Donc, x4
est aussi une borne supérieure pour cette fonction.
3. Par contre, f (x) = 2x3 + x2 n’est pas en O(x2 ), O(x).
4. La fonction f (x) = 5 est en O(1) (preuve : prenez x0 = 0 et k = 5). Elle est donc
aussi en O(x), en O(x2 ),. . .
5. La fonction f (x) = 3 log(2x) est en O(log(x)). Preuve : exercice.

Ainsi, on peut maintenant exprimer les complexités des algorithmes 8, 9 et 10 en

terme de O. L’algorithme 8 a une complexité en O(1), et les algorithmes 10 et 9 ont
une complexité en O(n). Par la suite, on écrira souvent que ces algorithmes sont « en
O(1) », « en O(n) ».

3.3.3 Classes de complexité algorithmique

Il est commode de grouper les fonctions en quelques « classes de complexité algo-
rithme », en fonction de leur caractérisation en terme de O. Voici les classes les plus
courantes :
Complexité O
Constante O(1)
Logarithmique O(log(n))
Linéaire O(n)
Quadratique O(n2 )
Cubique O(n3 )
Exponentielle O(2n )
40 CHAPITRE 3. LA COMPLEXITÉ ALGORITHMIQUE

1 x 1 0 6 y = 1 ( 0 2 0 , 6 )

y = x ( 0 2 0 , 6 )

y = x * * 2 ( 0 2 0 , 6 )

1 0 0 0 0 0

y = x * * 3 ( 0 2 0 , 6 )

y = l o g ( x ) ( 0 2 0 , 6 )

y = 2 * * x ( 0 2 0 , 6 )

1 0 0 0 0

1 0 0 0

1 0 0

1 0

0 5 1 0 1 5 2 0

F IG . 3.3 – Comparaison de différentes fonctions caractérisant les principales classes

de complexité algorithmique (échelle logarithmique en ordonnées).

Dans ce tableau, nous avons présenté les classes par ordre croissant de complexité.
Ainsi, toute fonction en O(n2 ), par exemple, sera aussi en O(n3 ), O(2n ), etc. La
Fig. 3.3 illustre cela en fournissant une comparaison des fonctions caractéristiques de
ces classes.

3.3.4 Règles de combinaison et de simplification

Jusqu’à présent, la méthode suggérée pour calculer la complexité d’un algorithme
en terme de O consiste à calculer la fonction f (x) qui donne le nombre d’étapes né-
cessaire à l’algorithme pour des données de taille x, puis à trouver un fonction g(x) (la
plus précise possible) telle que f (x) = O(g(x)).
Cette approche n’est pas très commode en pratique. On désirerait pouvoir raisonner
directement en terme de O sur certaines parties du programme, et ensuite combiner
ces différents résultats. La définition du O nous permet d’obtenir plusieurs règles de
combinaison et de simplification qui vont nous aider en cela.
Parmi les règles de simplification, on trouve :
Suppression des constantes multiplicatives Une fonction f (x) = c × h(x), où c est
une constante entière, est en O(h(x)). Pour le prouver, il suffit de prendre x0 = 0
et k = c dans la définition.
Par exemple, 3x2 est en O(x2 ).
Terme le plus significatif Dans une somme de fonctions, on peut se contenter de gar-
der le terme le plus significatif quand on passe au O (voir les classes ci-dessus).
Par exemple, f (x) = x + log(x) est en O(x).
3.3. LA NOTION DE GRAND O 41

Dans le cas particulier des polynômes, il s’agit du terme de plus haut degré. Par
exemple, 3x2 + 2x + 3 est en O(3x2 ), et donc en O(x2 ), par la règle de suppres-
sion des constantes multiplicatives.
Les règles de combinaison nous permette d’analyser le programme morceau par
morceau, et de combiner les différents résultats :
Séquence Si I1 est une suite d’instructions en O( f1 ) et I2 est une suite d’instructions
en O( f2 ), alors I1 ; I2 est en O( f1 + f2 ).
Boucle Si I est une suite d’instructions en O( f ), et que T est un test en O(g), alors
tant que (T ){I} est en O(ℓ × ( f + g)), où ℓ est le nombre d’exécutions de la
boucle.
Test Si I1 est une suite d’instructions en O( f1 ), I2 est une suite d’instructions en O( f2 )
et T est un test en O(g), alors si(T ){I1 }sinon{I2 } est en O(max f1 , f2 + g), ou,
plus simplement, en O( f1 + f2 + g). Cette dernière forme est équivalente par
la règle du Terme le plus significatif. De manière similaire, si(T ){I1 } est en
O( f1 + g).
Appel de fonction Un appel de fonction passe le contrôle de l’exécution à la fonction.
Il faut donc calculer la complexité de la fonction, qui pourra alors être utilisée
comme complexité de l’appel. Dans le cas des fonctions récursives, cette com-
plexité peut être plus difficile à calculer. La section 3.4 y est consacrée.
En pratique, le calcul de la complexité d’un algorithme peut faire appel à plusieurs
de ces règles, comme l’illustre l’exemple suivant.
Exemple 15 Revenons aux algorithmes 6 et 7. Nous avions vu intuitivement que le
premier était moins efficace que le second. Pouvons-nous obtenir cette information de
manière plus précise grâce à la complexité ?
La réponse est oui ! Pour ce faire, nous calculons d’abord la complexité de l’al-
gorithme 6. Nous commençons par analyser le contenu de la boucle tant que j ≤ n,
la plus imbriquée. Celle-ci contient un si, dont le corps ne contient qu’une instruction
d’affichage. Elle est donc en O(1). Le test i = j est également en O(1). Par la règle du
Test, tout le si est en O(1 + 1) = O(2), ce qui est en O(1), par la règle de suppression
des constantes multiplicatives.
Le si est suivi d’une assignation, qui est en O(1). Le contenu de la boucle est
donc en O(1 + 1) = O(2), par la règle de la séquence. À nouveau, on simplifie en
O(1). Le test j ≤ n de cette boucle est en O(1). La boucle s’exécute n fois, puisque
j est initialisée à 1 avant la boucle, et incrémentée de 1 à chaque tour de boucle. En
appliquant la règle de la boucle, on trouve que celle-ci est en O(n × (1 + 1)) = O(2n).
On simplifie à nouveau en O(n).
Regardons maintenant la boucle tant que i ≤ n. Elle contient une séquence com-
posée d’une assignation j := 1, en O(1) ; de la boucle analysée ci-dessous, en O(n) ;
et enfin d’une autre assignation i := i + 1 en O(1). Le contenu de la boucle est donc
en O(1 + n + 1) = O(n + 2), soit O(n), car on ne garde que le terme le plus signifi-
catif. Ici aussi, la boucle s’exécute n fois et le test est en O(1). La boucle est donc en
O(n × (n + 1)) = O(n2 + n). Cette dernière expression est en O(n2 ), car on ne garde
que le terme de degré le plus élevé.
Finalement, l’algorithme complet est lui-même une séquence composée d’une as-
signation i := 1 en O(1) ; d’une lecture de n, en O(1) ; et de la boucle analysée au
paragraphe précédent, en O(n2 ). L’algorithme 6 est donc en O(n2 + 2) = O(n2 ).
En analysant l’algorithme 7 à l’aide des mêmes méthodes, on trouve une complexité
de O(n). En effet, celui-ci est composé d’une initialisation en O(1), et d’une boucle
42 CHAPITRE 3. LA COMPLEXITÉ ALGORITHMIQUE

s’exécutant n fois, et dont le contenu et le test sont en O(1). Ceci nous permet de
conclure que l’algorithme 7 est plus efficace que l’algorithme 6.

3.4 Le cas des programmes récursifs

Comme nous l’avons déjà dit, on traite les appels de fonctions en assignant à l’appel
la complexité de la fonction appelée. Par exemple, pour évaluer la complexité de l’Al-
gorithme 11, on procède comme suit : on évalue d’abord la complexité de la fonction
g, qui est en O(n). Ensuite, on considère la fonction f . Celle-ci est composée d’une
boucle Tant que qui s’exécute n fois. Le corps de cette boucle comprend un appel à g,
en O(n) et une incrémentation en O(1). Le corps de la boucle est en O(n + 1) = O(n).
La boucle est donc en O(n × n) = O(n2 ). C’est aussi la complexité de la fonction f .

f (x)
début
i := 0;
tant que i < n faire
g(x) ;
i := i + 1 ;
fin

g(x)
début
. . . Un traitement en O(n). . . ;
fin
Algorithme 11 : Exemple d’appel de fonction et de calcul de la complexité.

L’évaluation de la complexité d’une fonction récursive peut poser des difficultés.

En effet, si nous considérons le cas d’une fonction f qui s’appelle elle-même, et que
nous appliquons le même raisonnement que ci-dessus, nous nous retrouvons à devoir
évaluer la complexité de f afin de pouvoir calculer la complexité de f . . .
Nous allons utiliser à nouveau le raisonnement par induction pour arriver à nos fins.
Considérons le cas de la fonction Facto, donnée à l’Algorithme 2 (Section 2.1.3), qui
calcule la factorielle de n de façon récursive.
Clairement, le temps nécessaire pour calculer la factorielle de n va dépendre du
nombre d’appels récursifs qui ont lieu. En effet, si nous appelons, par exemple Facto(5),
la fonction Facto appelle Facto(4), qui appellera Facto(3), qui appellera Facto(2), qui
appellera Facto(1). Cette dernière s’exécuter en O(1), en renvoyant directement la va-
leur 1. Le nombre d’appels à la fonction Facto est donc exactement 5. Il est facile de
voir qu’un appel à Facto(9), par exemple, aurait donné lieu à 9 appels à Facto ; qu’un
appel à Facto(3) aurait donné lieu à 3 appels, etc.
Or, chacun de ces appels consiste en l’évaluation de la condition du Si (en O(1)),
et en l’appel récursif. Le traitement propre à chaque appel (c’est-à-dire tout ce qui ne
concerne pas l’appel récursif) s’exécute donc en temps constant. Donc, l’algorithme
consiste à enchaîner n appels qui prennent un temps constant, et on peut donc raison-
nablement penser que la complexité de cette fonction est en O(n).
3.4. LE CAS DES PROGRAMMES RÉCURSIFS 43

3.4.1 Utilisation de l’induction

Remarquons que pour arriver à cette conclusion, nous avons utilisé un raisonnement
similaire à celui dont nous nous sommes servis dans les preuves par induction : nous
avons ramené le calcul de la complexité de Facto(n) au calcul de la complexité de
Facto(n − 1), que nous avons ramené au calcul de la complexité de Facto(n − 2),. . .
jusqu’à se ramener à la complexité de Facto(1). Cette dernière est facile à obtenir car
aucun appel récursif n’a lieu.
Ce que nous venons de faire n’est autre que l’esquisse d’une preuve, par induction,
que la complexité de Facto(n) est bien O(n). Écrivons-la formellement.
Théorème 4 Facto est en O(n).
Preuve. Nous allons prouver que l’exécution de Facto(n) peut être décomposée en n
traitements en O(1). Cette preuve est par induction sur n.
Cas de base : n = 1 La fonction renvoie directement 1, ce qui est bien en O(1).
Cas inductif : n = k ≥ 1 L’hypothèse d’induction stipule que l’exécution de Facto(k−
1) peut être décomposée en k − 1 traitements en O(1). L’exécution de Facto(k)
correspond à :
1. L’évaluation de la condition du si en O(1).
2. L’évaluation du paramètre de l’appel récursif, en O(1).
3. L’appel récursif Facto(k − 1).
4. La multiplication du résultat de l’appel récursif par n = k, en O(1).
5. L’assignation à n, en O(1).
6. Le retour de la valeur de n, en O(1).
Au-dehors de l’appel récursif, tous les traitements sont donc en 1). On peut
donc affirmer que l’exécution de Facto(k) se décompose en :
1. Un appel récursif qui correspond à k − 1 traitements en O(1).
2. Des traitements en O(1)
L’exécution de Facto(k) peut donc être décomposée en k traitements en O(1).
On conclut donc que, pour tout n ≥ 1, l’exécution de Facto(n) correspond à exécu-
ter n blocs d’instructions en O(1). Donc, Facto(n) est en O(n). 
Il est important de remarquer que, dans le cas de Facto, la complexité dépend essen-
tiellement de la profondeur des appels récursifs, comme illustré à la Fig. 3.4. Celle-ci
montre l’arbre d’exécution de la fonction Facto, dont la hauteur dépend clairement de
n. Comme chaque niveau de l’arbre s’exécute en temps constant, on retrouve la com-
plexité en O(n).
Ce raisonnement est à rapprocher de celui que nous appliquions dans le cas des
boucles : nous évaluions la complexité d’une itération de la boucle, que nous multi-
pliions ensuite par le nombre d’itérations effectuées. Dans le cas présent, nous éva-
luons la complexité des traitement propres à chaque appel, et nous la multiplions par le
nombre d’appels.
Naturellement, il est possible de combiner appels récursifs et boucles. Dans ce cas,
le nombre d’appels à la fonction récursive peut, lui aussi, dépendre des paramètres de
la fonction (par exemple si l’appel récursif est effectué dans une boucle dont le nombre
d’itérations dépend d’un paramètre). Il faut alors combiner les différentes méthodes
étudiées dans ce chapitre.
44 CHAPITRE 3. LA COMPLEXITÉ ALGORITHMIQUE

Facto(k)

}
n = k
é v a l u e r n 1 A p p e l r e c u r s i f

r e
é

t
v

o
a

u
l u

r n
e

e
r

r
n

} O (1)

n = k  1
é v a l u e r n 1 A p p e l r e c u r s i f

r e
é

t
v

o
a

u
l u

r n
e

e
r

r
n

} O (1)
n = k  2
é v a l u e r n 1

r e
é

t
v

o
a

u
l u

r n
e

e
r

r
n

} O (1)
n

A p p e l r e c u r s i f

n = 3
é v a l u e r n 1 A p p e l r e c u r s i f

r e
é

t
v

o
a

u
l u

r n
e

e
r

r
n

} O (1)

n = 2
é v a l u e r n 1 A p p e l r e c u r s i f

r e
é

t
v

o
a

u
l u

r n
e

e
r

r
n

} O (1)

n = 1
é

r e
v a

t o
l u

u
e

r n
r

e
n

r
=

1
1

} O (1)

F IG . 3.4 – Une illustration de l’exécution de Facto(k).

Chapitre 4

Les listes

Il existe énormément d’applications de l’informatique dans lesquelles il est néces-

saire de stocker de l’information sous forme de liste, c’est-à-dire sous forme de sé-
quence. Par exemple, une application gérant les étudiants et les cours d’une université
devra maintenir :
1. Une liste des cursus offerts
2. Une liste des années dans chaque cursus.
3. Pour chaque année d’études, la liste des cours disponibles
4. Une liste des étudiants
5. Pour chaque étudiant, la liste des cours qu’il a choisis
6. Pour chaque cours, la liste des enseignants impliqués
7. Une liste des locaux disponibles
8. etc
À chaque fois, l’odre des éléments peut être important : on peut désirer stocker les
cursus par ordre de Faculté (d’abord les cursus en philosophie et lettres, puis ceux en
science,. . .) ; stocker les années dans l’ordre imposé par le cursus ; stocker les cours
par ordre du nombre de crédits, ou par mnémonique ; stocker les étudiants par ordre
alphabétique, etc.

4.1 Motivation : critique des tableaux

Imaginons que nous désirions établir le palmarès des étudiants d’une université.
Supposons que les noms des étudiants et les notes obtenues sont stockés sur un fichier.
Pour ce faire, nous pouvons imaginer une solution qui consiste à :
1. Charger la liste des étudiants en mémoire.
2. Pour chaque étudiant, charger la liste de ses points en mémoire et calculer sa
moyenne (que l’on stocke en mémoire, en regard du nom de l’étudiant).
3. Trier les étudiants sur base de leur moyenne.
4. Imprimer le résultat du tri : coordonnées de l’étudiant et moyenne.
Quelle structure allons-nous choisir pour stocker les étudiants en mémoire ? Si nous
choisissons un tableau, il sera nécessaire de déclarer un tableau suffisamment grand

45
46 CHAPITRE 4. LES LISTES

pour contenir tous les étudiants. Malheureusement, le nombre d’étudiants n’est peut-
être pas connu à l’avance. On choisira donc une taille qui nous semble beaucoup plus
grande que le nombre réel d’étudiants, afin de ne pas dépasser la fin du tableau. Mal-
heureusement, les cases surnuméraires occuperont de la place « pour rien ». De plus,
ce nombre d’étudiants est susceptible de varier d’année en année (chaque fois que l’on
désire établir le palmarès). Rien ne nous garantit que la taille suffisante choisie en
2006–2007 pour stocker tous les étudiants le sera encore en 2007–2008. . .
Enfin, l’implémentation du tri risque d’être lourde, car elle implique de déplacer les
informations d’un étudiant d’une case du tableau vers une autre, ce qui peut être fort
coûteux en temps. En effet, considérons le tableau suivant :

0 1 2 3 4
Proust Hugo Lamartine Musset Baudelaire
12/20 15/20 18/20 19/20 14/20

Pour trier ces étudiants par ordre de notes croissantes, et insérer l’étudiant Baudelaire à
la case 1, entre Proust et Hugo, il est nécessaire de décaler Hugo, Lamartine et Musset
d’une case « vers la droite ».
Pour résumer, la faiblesse d’un tableau provient de son aspect statique :
1. Une fois qu’il est déclaré, sa taille ne change plus.
2. Il n’est pas possible d’insérer un élément à une position précise du tableau sans
écraser l’information qui s’y trouve, à moins de la déplacer elle-même.

4.2 Les listes simplement liées

Afin de contourner les difficultés liées aux tableaux, que nous venons d’identifier,
nous allons introduire la structure de liste simplement liée1 . Toutes les structures de liste
font grandement usage de la gestion dynamique de la mémoire. Il est donc conseillé
de revoir la Section 1.2.3, si nécessaire. Dans ce cours, nous supposerons également
que les listes servent à stocker des entiers, dans le but de simplifier le discours. Tout
ce que nous allons dire maintenant pourra s’étendre naturellement à d’autres types
d’informations (comme des chaînes de caractères, etc).
Les problèmes liés aux tableaux proviennent principalement du fait que l’ordre des
éléments est fixé de manière rigide. Si on définit un tableau de cinq cases, par exemple,
ces cinq cases seront stockées de manière contiguë et ordonnée en mémoire, sans qu’il
soit possible d’étendre la zone réservée au tableau. Par exemple, si le premier élément
du tableau est dans la 1024e case mémoire, le second sera dans la 1025e , le troisième
dans la 1026e, etc2 .
Dans une liste, les différents éléments constitutifs de la liste ne seront pas néces-
sairement stockés de façon contiguë, ni ordonnée. Ainsi, le premier élément de la liste
peut se trouver à l’adresse 1024, le second à l’adresse 256, le troisième en 532, le qua-
trième en 2084, etc. Afin de retrouver la bonne séquence des éléments en mémoire, il
est nécessaire d’ajouter de l’information à chaque élément de la liste. Cette information
permettra, dans une première approche, de retrouver l’élément suivant, en indiquant son
adresse.
1 Parfoisappélée : liste chaînée.
2
En faisant l’hypothèse que chaque élément du tableau peut tenir dans une case mémoire. Dans le cas
contraire, si la tableau commence à l’adresse b, et que chaque case consomme une place s en mémoire, la xe
case du tableau commence à l’adresse b + (x − 1) × s et se termine à l’adresse b + x × s − 1
4.2. LES LISTES SIMPLEMENT LIÉES 47

1 2 4 7 N I L

F IG . 4.1 – Un exemple de liste comprenant trois éléments, et dont la tête est stockée
dans la variable L.

Ainsi, chaque élément d’une liste sera constitué d’un enregistrement du type :
struct Elem
Entier info ;
Elem * next ;
que l’on représentera graphiquement comme ceci :

Dans chaque élément de la liste, nous stockerons donc une information, ainsi qu’un
pointeur, indiquant l’endroit en mémoire où se trouve l’élément suivant, s’il existe. Cet
élément suivant indiquera lui-même où se trouve son suivant, et ainsi de suite. Le der-
nier élément de la liste, qui ne possède pas de suivant, contiendra la valeur convention-
nelle NIL dans son champ next. Ainsi, pour accéder à la totalité de la liste, il ne sera
nécessaire de sauvegarder dans une variable qu’un pointeur vers le premier élément. Ce
premier élément, et, par extension, la variable qui contient son adresse, seront souvent
appelés la tête de la liste.
On peut donc représenter schématiquement une liste simplement liée comme pré-
senté à la Fig. 4.1. Cet exemple présente une liste faite de quatre éléments, contenant,
respectivement et dans l’ordre, les valeurs 1, 2, 4 et 7. La tête de la liste est stockée
dans la variable L (qui est donc de type « pointeur vers un Elem », et non pas Elem).
Dans le cas où l’on désire une liste vide, il suffira de stocker la valeur NIL dans la
variable L pointant vers la tête de la liste.

4.2.1 Comparaison aux tableaux

Avant d’aborder les algorithmes de manipulation de listes plus en détail, essayons
de nous convaincre sur cet exemple que cette nouvelle structure répond aux critiques
que nous avions formulées sur les tableaux.
1. La taille de la liste est dynamique, en ce sens qu’elle ne comporte pas plus d’élé-
ments qu’il n’y a d’informations à stocker. Si l’on désire supprimer un élément,
48 CHAPITRE 4. LES LISTES

1 2 4 7 N I L

F IG . 4.2 – Un exemple de suppression dans une liste simplement liée. Les pointeurs et
éléments en pointillés disparaissent lors de la suppression.

1 2 4 7 N I L

F IG . 4.3 – Un exemple d’insertion dans une liste simplement liée. Les pointeurs et
éléments en pointillés disparaissent lors de l’insertion.

on peut s’arranger pour qu’il n’apparaisse plus dans la séquence, et pour désal-
louer la mémoire qui le contenait, comme illustré sur la Fig. 4.2 . Si on désire
ajouter un élément, il suffit d’allouer un nouvel emplacement mémoire pour le
stocker, et modifier les pointeurs de manière à ce que cet élément apparaisse en
bonne place dans la séquence, comme illustré sur la Fig. 4.3.
2. Le déplacement d’un élément se résume à une manipulation de pointeurs, comme
illustré sur la Fig. 4.4
Par contre, le chaînage des éléments par pointeurs a un inconvénient : on ne peut
plus directement accéder à un élément arbitraire de la liste comme on pouvait le faire
avec un tableau. Pour accéder au ke élément du tableau T , par exemple, il suffit d’utili-
ser l’expression T [k]. Dans le cas d’une liste, il est nécessaire de parcourir toute la liste
depuis le début, élément par élément, comme nous le verrons ci-dessous.

4.2.2 Algorithmes
Passons maintenant en revue différents algorithmes permettant de manipuler des
listes simplement liées. Toutes ces fonctions recevront en paramètre une liste, c’est-à-
dire un pointeur vers un élément (la tête de la liste), ainsi que d’éventuels paramètres
supplémentaires.
4.2. LES LISTES SIMPLEMENT LIÉES 49

1 2 4 7 N I L

F IG . 4.4 – Un exemple de déplacement : l’élément 4 se trouve entre 2 et 7 avant le

déplacement, et se retrouve entre 1 et 2 après les déplacement. Trois pointeurs ont été
modifiés. Les pointeurs en pointillés réprésentent les anciennes valeurs.

Ces fonctions sont présentées aux Algorithmes 12, 13 et 14.

Construction d’une liste vide

La fonction ListeVide a pour but d’initialiser une liste. Il suffit donc d’assigner la
valeur NIL à la tête de la liste. Sa complexité est O(1).

Test de la liste vide

La fonction EstVide est une fonction booléenne qui reçoit une liste en paramètre,
et qui renvoie vrai si et seulement la liste est vide (c’est-à-dire si et seulement si la tête
est nulle). Sa complexité est O(1).

Premier élément de la liste

La fonction PremierElem reçoit une liste et renvoie un pointeur vers le premier

élément de la liste, ou NIL si la liste est vide. Cette fonction est triviale, étant donné
que la tête de la liste est l’information demandée. Elle est donnée uniquement dans le
but d’obtenir un ensemble complet de fonctions pour manipuler ce type de listes. Sa
complexité est O(1).

Dernier élément de la liste

La fonction DernierElem reçoit une liste et renvoie un pointeur vers le dernier

élément de la liste, ou NIL si la liste est vide. La différence par rapport à la fonction
précédente tient essentiellement en le parcours qu’il est nécessaire de réaliser pour
obtenir un pointeur vers le dernier élément de la liste.
Pour ce faire, on utilise une boucle qui déplace un pointeur sur chaque élément
successif de la liste, en commençant par la tête. La caractéristique du dernier élément
est que son champ next vaut NIL. Il suffit donc de faire tourner la boucle jusqu’à ce que
cette condition devienne vraie. Il faut néanmoins prendre garde au cas de la liste vide,
qui doit être testé et traité à part. En effet, si la liste est vide, nous avons p = L = NIL,
et l’évaluation du test [Link] 6= NIL donnera lieu à une erreur d’accès mémoire.
50 CHAPITRE 4. LES LISTES

La complexité de cette fonction est en O(n), où n est le nombre d’éléments de la

liste. Remarquons qu’il s’agit d’une complexité au pire cas, mais aussi au meilleur cas,
car on est toujours obligé de parcourir tous les éléments de la liste.

Insertion en tête d’une liste

La fonction InsèreTête reçoit comme paramètres une liste, et un entier qu’il faut
insérer dans la liste. On souhaite que l’élément apparaisse en tête de la liste après
l’insertion.
L’opération consiste à créer un nouvel élément contenant l’entier i. Comme cet
élément doit apparaître en tête de liste, son suivant après l’insertion sera l’élément en
tête avant l’insertion. On recopie donc l’adresse (stockée dans L) de l’élément de tête
dans le champ next du nouvel élément. On fait ensuite pointer la tête vers ce nouvel
élément (ce qui justifie le passage par référence de la tête de liste). Remarquez que cet
algorithme reste correct si la liste est vide initialement.
La complexité est en O(1).

Insertion en fin de liste

La fonction InsèreFin reçoit comme paramètres une liste, et un entier et réalise une
insertion en fin de liste.
Le traitement réalisé consiste à effectuer une insertion après le dernier élément de
la liste. Il se pourrait que celui-ci n’existe pas, ce qui signifie que la liste est vide. Dans
ce cas, l’insertion en fin de liste revient à une insertion en tête. Si la liste n’est pas
vide, nous utilisons DernierElem pour avoir accès au dernier élément, nous créons le
nouvel élément comme successeur de ce dernier élément, puis nous ajustons les champs
en conséquence.
Sa complexité dépend des complexités de EstVide et DernierElem, soit, respecti-
vement O(1) et O(n). En-dehors des appels à ces fonctions, InsèreFin ne réalise que
des traitement en temps constant. Elle a donc une complexité en O(n).

Accès au ke élément
La fonction KIemeElement reçoit une liste L et un entier k, et doit renvoyer un
pointeur vers le ke élément de L, s’il existe. Contrairement aux tableaux, il n’est pas
possible d’accéder directement au ke élément d’une liste. Il faut parcourir la liste depuis
le début, élément par élément, tout en comptant le nombre d’éléments visités. Il se peut
que le ke élément n’existe pas (la liste étant trop courte). Dans ce cas, la fonction
renvoie une erreur, sous forme d’un pointeur nul. Autrement, la fonction renvoie un
pointeur vers le ke élément. Cette fonction est en O(k).

Insertion à la ke position
La fonction InsèreKPos reçoit une liste L et deux entier i et k. Elle insère dans L
un nouvel élément dont l’information est i, et ce, à la position k (si possible). Pour que
l’insertion soit possible, il faut que la liste contienne au moins k − 1 éléments.
L’insertion à la ke position est aisée si on dispose d’un pointeur vers le k − 1e
élément (que l’on obtient à l’aide de la fonction KIemeElement). L’insertion suit alors
l’idée représentée à la Fig. 4.3. Remarquons, une fois de plus, que l’insertion en tête
doit être traitée comme un cas particulier. Celle-ci a lieu si k = 1.
Cette fonction est en O(n) au pire cas.
4.2. LES LISTES SIMPLEMENT LIÉES 51

ListeVide(Elem * &L)
début
L := NIL ;
fin

Booléen EstVide(Elem * L)
début
si L = NIL alors
retourner vrai ;
sinon
retourner faux ;
fin

Elem * PremierElem(Elem * L)
début
retourner L ;
fin

Elem * DernierElem(Elem * L)
début
Elem * p := L ;
si EstVide(L) alors retourner NIL ;
sinon
tant que [Link] 6= NIL faire
p := [Link] ;
retourner p ;
fin

InsèreTête(Elem * &L, Entier i)

début
Elem * p := new Elem ;
[Link] := i ;
[Link] := L ;
L := p ;
fin

InsèreFin(Elem * &L, Entier i)

début
si EstVide(L) alors
InsèreTête(L, i);
sinon
Elem * p := DernierElem(L) ;
[Link] := new Elem ;
p := [Link] ;
[Link] := NIL ;
[Link] := i ;
fin
Algorithme 12 : Algorithmes de manipulation de listes simplement liées (1).
52 CHAPITRE 4. LES LISTES

Suppresion du premier élément

La fonction SuppressionPremier doit supprimer le premier élément de la liste L,
s’il existe. Pour supprimer le premier élément d’une liste, il y a lieu de l’effacer physi-
quement de la mémoire, mais également d’ajuster le pointeur tête. En effet, l’élément
qui était en seconde position avant la suppression passe maintenant en première po-
sition. Remarquons que cette suppression ne peut s’effectuer qu’à la condition que le
premier élément existe, c’est-à-dire que la liste ne soit pas vide. Il faut donc tester cela,
et afficher un message d’erreur si cette précondition n’est pas remplie. La suppression
en tête est en O(1).

Suppression du ke élément d’une liste

La fonction SuppressionKIeme reçoit une liste L et un entier k. Elle doit supprimer
le ke élément de L, s’il existe. Comme nous l’avons vu sur la Fig. 4.2, le seul élément
de la liste à être modifié lors d’une suppression est celui qui précède l’élément à sup-
primer. Quand on supprime le ke élément, il faut donc obtenir un pointeur sur le k − 1e
élément (voir ci-dessus), et modifier le champ next de cet élément (outre la suppression
physique du ke élément).
Ceci n’est naturellement possible que pour k > 1. Quand k = 1, on tente en fait de
supprimer la premier élément de la liste, ce qui demande de modifier le pointeur tête,
comme vu au paragraphe précédent.
Remarquons à nouveau qu’il se pourrait que le ke élément n’existe pas. Dans ce
cas, la recherche retournera une erreur, matérialisée sous la forme d’un pointeur nul, et
la fonction de suppression n’a alors pas d’effet.
La complexité est en O(k), car la complexité de la recherche est ici dominante.

Recherche d’une information

La fonction Recherche reçoit une liste L et une information k, et doit renvoyer un
pointeur vers le premier élément de la liste L dont l’information est k (ou NIL si un
tel élément n’existe pas). Cette fonction est proche de la recherche du ke élément. La
différence principale tient dans le critère d’arrêt de la boucle : on s’arrêtera dès que
l’information est trouvée dans l’élément courant. Si l’information n’est pas présente
dans la liste, la boucle atteindra le dernier élément, et renverra un pointeur nul.
La complexité (toujours au pire cas) est en O(n), où n est le nombre d’éléments de
la liste.
Remarquons que pour que ce programme soit correct, il importe que le test d’une
conjonction se fasse clause par clause, et s’arrête dès qu’une clause est fausse. En effet,
si l’élément k n’est pas présent dans la liste, la boucle finira par atteindre le dernier
élément, et on aura à l’itération suivante p = NIL. Si le test de la boucle tant que
est complètement évalué, on accèdera au champ info d’un pointeur nul, ce qui causera
immanquablement un erreur. Par contre, si on évite d’évaluer [Link] 6= k, puisque p =
NIL, il n’y aura pas d’erreur.
En regardant la condition de la boucle, on en déduit que, en sortie de boucle, soit
p = NIL, auquel cas k n’est pas présent dans la liste ; soit [Link] = k.

Suppression d’une information

La fonction SuppressionInfo reçoit une liste L et une information k. Elle doit sup-
primer dans L la première occurrence d’un élément contenant k comme information
4.2. LES LISTES SIMPLEMENT LIÉES 53

(on peut aisément la modifier pour supprimer toutes les occurrences). Cette fonction
combine les difficultés rencontrées lors de la recherche d’une information et de la sup-
pression. En effet, il ne s’agit pas seulement de trouver l’élément contenant l’informa-
tion k demandée ; il faut également obtenir un pointeur sur l’élément qui le précède, et
ceci afin de pouvoir effectuer la suppression.
Pour ce faire, la stratégie adoptée consiste à parcourir la liste avec deux pointeurs
p et q. On s’arrangera, durant le parcours, pour que le pointeur q pointe toujours sur
l’élément qui précède p dans la liste. Ainsi, si p pointe vers un élément contenant l’in-
formation k (qu’il faut donc supprimer), q pointe vers l’élément dont on doit modifier
le champ next.
À la sortie de la boucle principale, il y a deux possibilités :
1. p = NIL. Dans ce cas, on a parcouru toute la boucle sans trouver l’information
à effacer. On peut décider d’afficher une erreur, ou de ne rien faire.
2. [Link] = k. Le pointeur p pointe donc vers un élément à supprimer. On doit
encore envisager deux cas de figure :
(a) Soit p = L, c’est-à-dire que p pointe vers le premier élément. Dans ce cas,
il y a lieu de faire une suppression, en tête, et le pointeur q ne contient pas
d’information utile.
(b) Soit p 6= L, c’est-à-dire que p est « au milieu » de la liste. À ce moment,
q pointe bien vers l’élément qui le précède et on peut donc procéder à la
suppression de façon habituelle.
La compexité de cette fonction est en O(n) au pire cas.

4.2.3 Listes triées

Dans certains cas, il peut être plus commode de conserver la liste triée. Autrement
dit, en parcourant la liste de la tête au dernier élément, on trouvera les informations
dans un odre bien déterminé (croissant ou décroissant pour les entiers, par exemple).
Dans ce cas, il convient d’adapter certaines opérations.
Dans la suite de cette section, nous prendrons la convention que les listes manipu-
lées sont des listes triées par ordre croissant d’entiers.

Insertion triée
Le but de cette opération est d’insérer une information k dans une liste L, qui est
déjà triée, tout en maintenant le caractère trié de cette liste. Pour ce faire, il convient
de repérer le premier élément de L qui contienne une information ≥ k. Il faudra alors
insérer la nouvelle information avant cet élément.
Comme d’habitude, l’insertion en tête doit être traitée avec soin. Celle-ci aura lieu
si et seulement si soit l’information stockée dans la tête est ≥ k, soit la liste est vide.
Dans le cas contraire, il faudra parcourir la liste. Nous allons à nouveau utiliser la
stratégie développée pour la fonction SuppressionInfo, à savoir l’utilisation de deux
pointeurs p et q, où q pointe toujours vers l’élément qui précède p. On s’arrangera pour
arrêter p sur le premier élément dont l’information est ≥ k (s’il existe). À la fin de la
boucle principale, nous aurons deux possibilités :
1. p = NIL. Dans ce cas, tous les élémentsde la liste sont < k, et il convient donc
d’insérer le nouvel élément à la fin de la liste. Cela revient à insérer après q, qui
pointe à ce moment vers le dernier élément (rappelons que la liste n’est pas vide,
et qu’on n’insère pas en tête).
54 CHAPITRE 4. LES LISTES

Elem * KIemeElement(Elem * L, Entier k)

début
Elem * p := L ;
Entier i := 1 ;
tant que p 6= NIL et i < k faire
i := i + 1 ;
p := [Link] ;
retourner p ;
fin

InsèreKPos(Elem * &L, Entier k, Entier i)

début
Elem * p, q ;
si k = 1 alors
InsèreTête(L, i) ;
sinon
p :=KIemeElement(L,k − 1) ;
si p 6= NIL alors
q := new Elem ;
[Link] := i ;
[Link] := [Link] ;
[Link] := q ;
sinon
Afficher « Erreur : il n’y a pas assez d’éléments » ;
fin

SuppressionPremier(Elem * &L)
début
si EstVide(L) alors
Afficher « Erreur, la liste est vide » ;
sinon
Elem * p := L ;
L := [Link] ;
delete p ;
fin

SuppressionKIeme(Elem * &L, Entier k)

début
Elem * p, q ;
si k = 1 alors
SuppressionPremier(L) ;
sinon
p :=KIemeElement(L,k − 1) ;
si p 6= NIL alors
q := [Link] ;
[Link] := [Link] ;
delete q ;
fin
Algorithme 13 : Algorithmes de manipulation de listes simplement liées (2).
4.3. LES LISTES CIRCULAIRES AVEC ÉLÉMENT PRÉ-TÊTE 55

Elem * Recherche(Elem * L, Entier k)

début
Elem * p := L ;
tant que p 6= NIL et [Link] 6= k faire
p := [Link] ;
retourner p ;
fin

SuppressionInfo(Elem * & L, Entier k)

début
Elem * q, p := L ;
tant que p 6= NIL et [Link] 6= k faire
q := p ;
p := [Link] ;
si p 6= NIL alors
si p 6= L alors
SuppressionPremier(L) ;
sinon
[Link] := [Link] ;
delete p ;
sinon
Afficher « L’élément n’a pas été trouvé » ;
fin
Algorithme 14 : Algorithmes de manipulation de listes simplement liées (3).

2. [Link] ≥ k. Dans ce cas, on peut sans risque d’erreur insérer après q, puisque la
liste n’est pas vide et qu’on ne fait pas d’insertion en tête.
Dans les deux cas, on peut donc insérer après q, sans risque d’erreur.

Recherche d’un valeur

La recherche d’une valeur k dans une liste triée est simplifiée : en effet, dès qu’on
atteint une valeur > k, on sait qu’on ne doit pas explorer le reste de la liste, car toutes
les valeurs suivantes sont elles aussi > k. Néanmoins, la fonction reste en O(n) au pire
cas (où n est le nombre d’éléments dans la liste).
Dans les sections suivantes, nous allons présenter différentes extensions des listes
simplement liées. Ces extensions permettent de pallier certains défauts inhérents aux
listes simples.

4.3 Les listes circulaires avec élément pré-tête

Parmi les défauts des listes que nous avons présentées jusqu’à présent, on trouve
principalement :
– Les difficultés liées à la manipulation du pointeur tête : insertion et suppression
en tête.
– Les difficultés liées au cas particulier de la liste vide.
– Le fait qu’on soit obligé, quand on parcourt la liste à l’aide d’un pointeur p,
de tester continuellement si p est nul, alors qu’un seul élément de la liste a son
champ next à NIL.
56 CHAPITRE 4. LES LISTES

InsertionTriée(Elem * & L, Entier k)

début
si EstVide(L) ou [Link] ≥ k alors
InsèreTête(L, k) ;
sinon
Elem * q := L, p := [Link], r ;
tant que p 6= NIL et [Link] < k faire
q := p ;
p := [Link] ;
r := new Elem ;
[Link] := p ;
[Link] := k ;
[Link] := r ;
fin

Elem * Recherche(Elem * L, Entier k)

début
Elem * p := L ;
tant que p 6= NIL et [Link] < k faire
p := [Link] ;
si p 6= NIL et [Link] 6= k alors
p := NIL ;
retourner p ;
fin
Algorithme 15 : Algorithmes de manipulation de listes simplement liées triées.

4.3.1 Différences par rapport aux listes « simples »

Tous ces problèmes peuvent être résolus en utilisant une structure un peu plus com-
plexe : les listes circulaires avec élément pré-tête. Une telle liste se différencie d’une
liste « simple » par deux caractéristiques :
1. Une liste circulaire avec élément pré-tête contient toujours au moins un élément,
appelé élément pré-tête ou élément bidon. Cet élément est toujours le premier
élément de la liste et ne contient pas d’information significative. Cela signifie
que l’information qui y est stockée ne doit pas être considérée comme faisant
partie de ce qui est stocké dans la liste.
2. Comme son nom l’indique, une liste circulaire avec élément pré-tête est circu-
laire, c’est-à-dire que le champ next du dernier élément contient la même valeur
que L, à savoir l’adresse du premier élément (l’élément bidon, donc).
Un exemple de liste circulaire avec élément pré-tête est représenté à la Fig. 4.5.
L’information stockée dans cette liste est 1, 2, 4, 7 (l’information contenue dans l’élé-
ment bidon – représentée par ? – est ignorée).
Dans une telle liste, il convient donc de distinguer le premier élément (physique)
de la liste, qui est l’élément bidon, et le premier élément significatif, qui est celui qui
suit l’élément bidon (s’il y en a un).
En quoi ces deux différences resolvent-elles nos problèmes ? Passons-les en revue :
– Il n’y a plus vraiment d’insertion et de suppression en tête, puisque le premier
élément significatif d’une liste circulaire avec élément pré-tête est en fait le se-
cond de la liste (celui qui suit l’élément bidon). La seule modification du poin-
4.3. LES LISTES CIRCULAIRES AVEC ÉLÉMENT PRÉ-TÊTE 57

?
1 2 4 7

F IG . 4.5 – Un exemple de liste circulaire avec élément pré-tête.

?
1 2 4 7

F IG . 4.6 – Un exemple d’insertion en tête dans une liste circulaire avec élément pré-
tête.

teur L aura donc lieu au moment de la création de la liste. La Fig. 4.6 donne un
exemple d’insertion tête.
– Une liste circulaire avec élément pré-tête, même vide, contient toujours au moins
un élément (l’élément bidon). On n’aura donc jamais de pointeur L égal à NIL.
La Fig. 4.7 montre une liste circulaire vide.
– La recherche d’une valeur k dans la liste sera également simplifiée. En effet,
comme l’information contenue dans l’élément bidon n’est pas significative, rien
ne nous empêche de la modifier. Ainsi, si on recherche l’information k dans la
liste, on peut placer cette information dans l’élément bidon. On commence la
recherche de k sur le premier élément significatif. Comme la liste est circulaire,
on est certain de trouver l’élément k : soit parmi les éléments significatifs, soit
dans l’élément bidon, qu’on rencontrera immanquablement comme successeur
du dernier élément. Ces deux cas peuvent aisément être discriminés : tout élé-
ment significatif a une adresse 6= L, et l’élément bidon est pointé par L. Le seul
test à faire en parcourant une telle liste à l’aide du pointeur p est donc [Link] 6= k.
La Fig. 4.8 illustre cela.
De manière générale, ces listes ont l’avantage de ne pas utiliser de pointeurs NIL,
ce qui limite les risques d’erreur.
58 CHAPITRE 4. LES LISTES

F IG . 4.7 – Une liste circulare avec élément pré-tête vide.

4.3.2 Algorithmes
Comme dans le cas des listes simplement liées, nous passons en revue quelques
algorithmes classiques. Ceux-ci sont présentés aux Algorithmes 16 et 17.

Construction d’une liste vide

La fonction ListeVide initialise la liste. Il faut créer l’élément pré-tête, est s’ar-
ranger pour que la liste soit circulaire. Il s’agit d’une fonction qui s’exécute en temps
constant.

Test de la liste vide

La fonction EstVide est une fonction booléenne qui reçoit une liste en paramètre,
et qui renvoie vrai si et seulement la liste est vide. C’est le cas si et seulement si la
l’élément bidon a son champ next qui pointe vers lui-même.
Cette fonction est en O(1).

Premier élément de la liste

La fonction PremierElem reçoit une liste et renvoie un pointeur vers le premier
élément de la liste, ou NIL si la liste est vide. Il faut prendre garde à retourner le
premier élément significatif (pointé par [Link], s’il existe (c’est-à-dire si la liste n’est
pas vide).
Cette fonction ne réalise que des tests et des traitements en temps constant. Elle est
donc en O(1).

Dernier élément de la liste

La fonction DernierElem reçoit une liste et renvoie un pointeur vers le dernier
élément de la liste, ou NIL si la liste est vide. Dans ce cas aussi, il est nécessaire de
parcourir la liste jusqu’à atteindre le dernier élément. Cette fois, ce dernier élément
4.3. LES LISTES CIRCULAIRES AVEC ÉLÉMENT PRÉ-TÊTE 59

k
1 2 4 7

k
1 2 4 7

k
1 2 4 7

F IG . 4.8 – La recherche de l’information k dans une liste circulaire avec élément pré-
tête. Au pire cas (quand k n’est pas présent dans la liste), le pointeur fait le tour de la
liste et revient à l’élément pré-tête, qui contient k.
60 CHAPITRE 4. LES LISTES

n’est pas celui dont le champ next est NIL (puisqu’il n’y en a pas), mais celui dont le
champ next est L.
Comme il est nécessaire de parcourir toute la liste, cette fonction est en O(n), où n
est le nombre d’éléments de la liste.

Insertion à la ke position
Cette fonction reçoit une liste L, un entier k et un entier i. Elle insère l’entier i dans
la liste, à la ke position. Cette fonction profite grandement de l’élément pré-tête, ce qui
évite de traiter l’insertion en tête comme un cas particulier. Remarquons que si la liste
ne contient pas assez d’éléments (moins de k − 1), l’insertion n’est pas possible.
On parcourt la liste à l’aide du pointeur p, en commençant sur le premier élément
significatif. À chaque nouvel élément rencontré, on incrémente un compteur. La boucle
s’arrête soit parce que le compteur vaut k − 1, soit parce que p pointe vers l’élément
bidon. Si le compteur vaut k − 1, p pointe vers le k − 1e élément de la liste, et il suffit
d’insérer après p. Sinon, il n’est pas possible d’insérer car la liste ne contient pas assez
d’éléments.
Remarquons que cette fonction est également correcte dans le cas de l’insertion
en tête. En effet, dans ce cas k = 0, et on ne rentre donc pas dans la boucle. p garde
donc sa valeur initiale, à savoir L. On réalise donc l’insertion après l’élément bidon, ce
qui est bien une insertion en tête. Pour autant, celle-ci n’a pas demandé de traitement
particulier, comme c’était le cas dans les listes simples.
Comme cette fonction doit parcourir la liste afin d’atteindre le ke élément, elle est
en O(k).

Recherche d’une valeur

La fonction Recherche reçoit un pointeur vers la tête d’une liste, et une valeur k.
Elle renvoie un pointeur vers le premier élément qui contient la valeur k, ou NIL si
aucun élément ne contient cette valeur.
Cette fonction exploite le procédé décrit ci-dessus, qui consiste à stocker la valeur k
recherchée dans l’élément pré-tête. Ceci permet de diminuer le nombre de tests à effec-
tuer dans la boucle tant que qui parcourt la liste. Le seul test nécessaire est [Link] 6= k.
À la sortie de la boucle, on a donc la garantie que p pointe vers une élément dont le
champ info contient k. Il suffit de tester si p est égal à L, afin de déterminer si l’élément
trouvé est un élément significatif de la liste, ou bien l’élément pré-tête, auquel cas on
est sûr que la liste ne contient pas d’élément dont l’information est k.
Cette fonction est en O(n), où n est le nombre d’éléments dans la liste. Remarquons
que, si la suppression du test p 6= L dans la boucle ne change pas la complexité (en
terme de O) de la fonction (au pire cas, il faut malgré tout appliquer un traitement qui
reste constant à chaque élément de la liste), le temps nécessaire pour traiter chaque
élément est tout de même diminué.

La technique développée dans le cadre de la recherche peut être éxploitée dans

d’autres cas de figure. Par exemple, si on manipule une liste circulaire avec élément
pré-tête triée par ordre croissant, il peut être utile de mettrela valeur +∞ dans l’élément
pré-tête3. Ainsi, la boucle suivante sera suffisante pour trouver l’endroit où insérer une
valeur k tout en gardant la liste triée (quelque soit la valeur k) :
3 En pratique, on utilisera une valeur limite, qui dépend du type de données manipulé, et du langage

considéré. Par exemple, la constante INT_MAX remplit cet office en C ou C++.

4.3. LES LISTES CIRCULAIRES AVEC ÉLÉMENT PRÉ-TÊTE 61

Elem * ListeVide()
début
Elem * p := newElem ;
[Link] := p ;
retourner p ;
fin

Booléen EstVide(Elem * L)
début
si [Link] = L alors retourner vrai ;
sinon retourner faux ;
fin

Elem * PremierElem(Elem * L)
début
si EstVide(L) alors retourner NIL ;
sinon retourner [Link] ;
fin

Elem * DernierElem(Elem * L)
début
Elem * p ;
si EstVide(L) alors p := NIL ;
sinon
p := [Link] ;
tant que [Link] 6= L faire
p := [Link] ;
retourner p ;
fin
Algorithme 16 : Algorithmes de manipulation de listes circulaires avec élément pré-
tête (1).
62 CHAPITRE 4. LES LISTES

InsèreKPos(Elem * L, Entier i, Entier k)

début
Elem * save, p ;
Entier cpt = 0 ;
si k = 1 alors
p := L ;
sinon
p := [Link] ;
tant que p 6= L et cpt < k − 1 faire
cpt := cpt + 1 ;
p := [Link] ;
si cpt = k − 1 alors
save := [Link] ;
[Link] := new Elem ;
p := [Link] ;
[Link] := i ;
[Link] := save ;
sinon
Afficher « Erreur : il n’y a pas assez d’éléments dans la liste » ;
fin

Elem * Recherche(Elem * L, Entier k)

début
Elem * p := [Link] ;
[Link] := k ;
tant que [Link] 6= k faire
p := [Link] ;
si p = L alors
p := NIL ;
retourner p ;
fin
Algorithme 17 : Algorithmes de manipulation de listes circulaires avec élément pré-
tête (2).
4.4. LES LISTES DOUBLEMENT LIÉES 63

N I 1 2 3 4 N I

L L

F IG . 4.9 – Un exemple de liste doublement liée.

tant que [Link] < k faire

p := [Link] ;
De par la présence du +∞ dans l’élément bidon, on a la certitude que ce test sera vrai au
bout d’un temps fini, soit parce que les élément significatifs de la liste contiennent ef-
fectivement une valeur ≥ k (auquel cas il faut insérer avant p), soit parce qu’on a atteint
l’élément bidon (auquel cas il faut insérer en fin de liste, c’est-à-dire avant l’élément
bidon, pointé par p). Dans tous les cas, on insère donc avant p.

4.4 Les listes doublement liées

Une autre extension possible des listes simplement liées consiste à enregistrer dans
chaque élément de la liste l’adresse de l’élément qui le précède, en plus de l’élément
suivant. Un élément de la liste seront donc maintenant du type suivant :
struct Elem
Entier info ;
Elem * next ;
Elem * prec ;

Comme dans le cas des listes simplement liées, le dernier élément de la liste aura
son champ next à NIL. De façon symétrique, le premier élément de la liste aura son
champ prec à NIL également, puisqu’aucun élément ne le précède. La Fig. 4.9 présente
une illustration de liste doublement liée.
Naturellement, ce pointeur supplémentaire alourdit la structure. Néanmoins, cette
adjonction offre plus de flexibilité dans les modalités de parcours de la liste, qui peut
maintenant être traversée « en arrière ». Illustrons cela par l’algorithme suivant. Nous
désirons écrire une fonction qui reçoit une liste L, ainsi que deux entiers i et j. Cette
fonction doit insérer, dans la liste L, un nouvel élément dont l’information est i, et ce,
avant la première occurrence d’un élément portant l’information j. Cette insertion est
illustrée à la Fig. 4.10.
La fonction InsèreAvantJ est donnée à l’Algorithme 18. Elle consiste en un par-
cours de la liste à l’aide du pointeur p, à partir de la tête. Ce parcours s’arrête soit parce
que [Link] = j, auquel cas il faut insérer avant p ; soit parce que p = NIL, auquel cas
la liste ne contient pas d’élément dont l’information est j.
Dans le cas où l’insertion doit être effectuée, celle-ci est rendue plus simple par le
pointeur prec, qui permet d’accéder directement à l’élément précédent celui pointé par
p. Sans ce pointeur, il eût été nécessaire de maintenir un second pointeur q qui pointe
toujours sur l’élément précédent p, ce qui alourdit le parcours.
64 CHAPITRE 4. LES LISTES

N I 1 2 4 5 N I

L L

F IG . 4.10 – Un exemple d’insertion dans une liste doublement liée. On insère un élé-
ment portant la valeur 3 avant l’élément portant la valeur 4.

InsèreAvantJ(Elem * L, Entier i, Entier j)

début
Elem * p := L, q ;
tant que p 6= NIL ∧ [Link] 6= j faire
p := [Link] ;
si p = NIL alors
Afficher « Erreur, élément non trouvé » ;
sinon
q := newElem ;
[Link] := i ;
[Link] := p ;
[Link] := [Link] ;
[Link] := q ;
[Link] := q ;
fin
Algorithme 18 : L’insertion d’un élément dont l’information est i avant un élément
dont l’information est j, dans une liste doublement liée.
4.5. IMPLÉMENTATION DES LISTES DANS LES VECTEURS 65

Par contre, l’insertion à proprement parler est plus complexe que dans le cas d’une
liste simplement liée, puisqu’il y a maintenant quatre (et non plus deux) pointeurs à
modifier.

Remarquons que les deux extensions des listes que nous venons de présenter peuvent
être combinées. Il est en effet tout à fait possible d’envisager des listes doublement liées
circulaires avec élément pré-tête. Dans ce cas, le premier élément de la liste ne sera pas
significatif, et aura son champ prec qui pointe vers le dernier élément de la liste. Ce
dernier aura son champ next qui pointe vers l’élément pré-tête.

4.5 Implémentation des listes dans les vecteurs

Nous venons d’étudier trois types de listes, et nous les avons toutes présentées en
utilisant la notion de pointeur. En effet, c’est la possiblité de pouvoir référencer une
case mémoire arbitraire comme élément suivant (ou précédent, dans le cas des listes
doublement liées) qui nous a permis de nous libérer de la rigidité des vecteurs (voir
l’introduction de ce chapitre).
Néanmoins, un pointeur n’exprime jamais qu’un adresse en mémoire, c’est-à-dire
un décallage par rapport au début de la mémoire. Il est possible de transposer cette
idée dans le contexte des vecteurs : si on associe à chaque case du vecteur une valeur
entière qui indique l’indice (c’est-à-dire le décallage par rapport au début du vecteur)
de la case qui la suit logiquement (et non plus physiquement), on peut implémenter le
concept de liste dans un vecteur.
En pratique, nous procéderons comme suit pour implémenter une liste simplement
liée dans un vecteur4. On utilisera deux vecteurs I et N, et une variable entière T qui
représentera la tête de la liste. Un élément de la liste sera réparti sur une case d’indice
j du vecteur I (qui contiendra l’information de l’élément), et sur une case d’indice j
également, du vecteur N (qui contiendra l’indice de l’élément suivant). Le premier élé-
ment à considérer sera d’indice L. Ainsi, le premier élément contiendra l’information
I[L], le second I[N[L]], le troisième I[N[N[L]]], etc.
La fin de la liste sera indiquée en stockant la valeur conventionnelle −1 dans N.
Ainsi l’élément d’indice j tel que N[ j] = −1 sera le dernier de la liste. Cette valeur
sentinelle remplace le NIL des pointeurs.
Enfin, signalons que, dans le cas où l’on voudra insèrer un nouvel élément dans
une telle liste, il sera nécessaire de savoir dans quelle case des vecteur I et N on peut
le stocker. Dans le cas des listes avec pointeur, cela était effectué de façon automatique
par l’opérateur new. Dans le cas présent, on passera à la fonction, en plus de L, N et I,
un entier pos, indiquant la position de la première case libre dans le vecteur (en faisant
l’hypothèse que toutes celles qui suivent le sont également).
La Fig 4.11 présente un exemple de liste implémentée dans un vecteur, avec son
équivalent utilisant des pointeurs.
On voit que tous les algorithmes écrits sur les listes simples sont aisément transpo-
sés dans le présent contexte. Un pointeur p est remplacé par une variable entière i in-
diquant un indice. Les expressions du type [Link] ou [Link] deviennent respectivement
I[i] et N[i], etc. À titre d’exemple, considérons les algorithmes d’insertion en tête, de
recherche du ke élément et d’insertion en ke position. Ils sont donnés à l’Algorithme 19
. La comparaison avec leurs équivalents exploitant les pointeurs (voir Algorithme 12
4 Tout ce que nous allons présenter ici pourra également être appliqué si on considère d’autres types de

listes.
66 CHAPITRE 4. LES LISTES

1 2 3 4 5 . . .

? ?

7 1 4 2 2

? ?

1 4 1 3 5

1 2 4 7 N I L

F IG . 4.11 – Un exemple de liste implémentée dans un vecteur, et son équivalent utili-

sant des pointeurs.

et Algorithme 13) permet de voir qu’il s’agit véritablement d’une traduction : rien ne
change sur le plan algorithmique.

4.5.1 Application
L’utilité de ces listes n’est peut être pas évidente au premier abord. Une première
justification de ces techniques est que certains langages (comme C OBOL) n’admettent
pas l’utilisation de pointeurs. Une autre utilité de ces listes consiste à optimiser certains
algorithmes travaillant sur des vecteurs, en le tranformant temporairement en liste, par
les moyens décrits ci-dessus. Illustrons cela à l’aide d’un algorithme recevant deux
vecteurs d’entiers V et W (de tailles n et m), qui sont triés par ordre croissant, et qui
doit insérer dans V tous les éléments de W , tout en gardant le caractère trié de V .
On supposera que V est suffisament grand que pour réaliser ce traitement. Pour ce
faire, on supposera que seules les ℓ premières cases de V contiennent de l’information
significative. Les cases ℓ + 1 à n sont non-initialisées.
Un tel algorithme demandera naturellement d’effectuer plusieurs déplacements d’élé-
ments dans le vecteur V pour « faire de la place » aux éléments de W qui doivent y être
insérés. Commençons par décrire une solution « standard » à ce problème (voir Al-
gorithme 20). Nous donnons d’abord une fonction DécallageVecteur, qui reçoit un
vecteur V (de taille n) et un entier i, et qui décalle toutes les cases d’indice ≥ i d’une
position vers la droite (la dernière case est donc perdue). Cette fonction parcourt le
vecteur V depuis sa penultième case jusqu’à sa case d’indice i, à l’aide d’une variable
j ; et déplace chaque case de V à l’aide de l’instruction V [ j + 1] := V [ j].
Nous pouvons maintenant écrire la fonction FusionVecteur. Celle-ci reçoit les
deux vecteurs V et W , ainsi que le nombre ℓ de cases de V qui contiennent de l’infor-
4.5. IMPLÉMENTATION DES LISTES DANS LES VECTEURS 67

InsèreTête(Entier &L, Entier &pos, Entier I[n], Entier N[n], Entier i)

début
Entier j := pos ;
pos := pos + 1 ;
I[ j] := i ;
N[ j] := L ;
L := j ;
fin

Entier KIemeElement(Entier L, Entier I[n], Entier N[n], Entier k)

début
Entier j := L ;
Entier i := 1 ;
tant que j 6= −1 et i < k faire
i := i + 1 ;
j := N[ j] ;
retourner j ;
fin

InsèreKPos(Entier &L, Entier &pos, Entier I[n], Entier N[n], Entier k,

Entier i)
début
Entier i, ℓ ;
si k = 1 alors
InsèreTête(L, pos, I, N, i) ;
sinon
j :=KIemeElement(L,k) ;
si j 6= −1 alors
ℓ := pos ;
pos := pos + 1 ;
I[ℓ] := k ;
N[ℓ] := N[ j] ;
N[ j] := ℓ ;
sinon
Afficher « Erreur : il n’y a pas assez d’éléments » ;
fin
Algorithme 19 : Trois algorithmes manipulant des listes simples implémentées dans
des vecteurs.
68 CHAPITRE 4. LES LISTES

mation. La fonction maintient en permanence deux indices i et j. L’indice j parcourt

le vecteur W , et indique quelle case de W doit être insérée dans V . L’indice i parcourt
le vecteur V , et permet de répérer la position à laquelle W [ j] doit être inséré. Chaque
itération de la boucle principale met un élément W [ j] à sa place dans V . Pour ce faire,
la boucle intérieure fait avancer l’indice i tant que les valeurs V [i] sont strictement infé-
rieures à W [ j]. La boucle s’arrête également si i = ℓ + j − 1. En effet, V contient à tout
moment ℓ + j − 1 valeurs significatives, à savoir les ℓ valeurs présentes intialement,
plus les j − 1 valeurs de W qui ont déjà été placées. Quand la boucle intérieure s’arrête,
on sait que :
1. soit V [i] ≥ W [ j]. La valeur W [ j] doit donc être recopiée en V [i], après que les
cases V [i], V [i + 1],. . ., V [n] ont été déplacées vers la droite.
2. soit on a passé en revue toutes les valeurs significatives de V , et on doit donc
insérer W [ j] après celles-ci, soit en V [i]. Le décallage des cases V [i], V [i + 1],. . .,
V [n] n’est pas nécessaire mais n’est pas incorrect non plus (on peut l’éviter à
l’aide d’un test).

DécallageVecteur(Entier V [n], Entier i)

début
Entier j := n − 1 ;
tant que j ≥ i faire
V [ j + 1] := V [ j] ;
j := j − 1 ;
fin

FusionVecteur(Entier V [n], Entier ℓ, Entier W [m])

début
Entieri := 1, j := 1 ;
tant que j ≤ m faire
tant que i ≤ ℓ + j − 1 et V [i] > W [ j] faire
i := i = 1;
DécallageVecteur(V, i) ;
V [i] := W [ j] ;
i := i + 1 ;
j := j + 1 ;
fin
Algorithme 20 : Une solution au problème de fusion des vecteurs triés, utilisant un
décallage dans le vecteur.

Comme pour chaque insertion des m éléments de W , il est nécessaire d’effectuer

dans V un décallage en O(ℓ), la complexité de cette solution est O(m × ℓ).
Comme on le voit, cette solution fait régulièrement appel à DécallageVecteur, qui
est assez lourde. Dans une liste, ce décallage ne serait pas nécessaire puisque l’inser-
tion peut être effectuée en temps constant. On peut obtenir un algorithme plus efficace
(voir Algorithme 21) en ajoutant à V un second vecteur N et une variable L qui le trans-
forment en liste. Le vecteur N sera initialisé de telle façon que, pour tout 1 ≤ j < ℓ,
N[ j] = j + 1 (initialement, chaque case j a pour suivante la case j + 1), et N[ℓ] = −1
(la case ℓ est la dernière à considérer). L sera intialisée à 1 (la première case du vecteur
est également la première de la liste). On viendra ensuite insérer chque case du vecteur
W dans la liste constituée de V , N et L. Ces insertions ne demanderont pas d’opération
4.6. VUE RÉCURSIVE 69

de déplacement, puisque seuls les « pointeurs » (c’est-à-dire les valeurs de N) seront

modifiés. À la fin de l’opération, il suffira de recopier les m + ℓ éléments de la liste
formée par V , N et L dans un vecteur temporaire, puis de remettre le contenu de ce
vecteur dans V .
En pratique, l’insertion est réalisée à l’aide de deux indices i et k. Une boucle tant
que passe tous les éléments de la liste contenue dans V qui sont plus petit que W [ j].
L’indice k pointe toujours vers l’élément qui précède logiquement i. Dès que la boucle
tant que (i 6= −1 et I[i] < W [ j]) s’arrête, il faut réalier l’insertion entre l’élément k et
l’élément i. Ceci peut donner lieu à une insertion en tête dans le cas où W [ j] est plus
petit que tous les éléments de V . Dans ce cas, on n’entre pas dans la boucle tant que,
ce qu’on peut aisément détecter en initialisant k à −1 avant la boucle et en vérifiant la
valeur de k après la boucle : si k = −1, on insère en tête, sinon, on insère après k.
Cette solution peut paraître plus lourde à la lecture, mais elle est plus efficace que
la précédente (du moins en temps, étant donné que les vecteurs supplémentaires oc-
cupent de la place en mémoire). En effet, chaque insertion s’effectue maintenant en
temps constant. Comme il y a lieu d’insérer m éléments, et comme on effectue un seul
parcours de V , la complexité des insertions est en O(m + ℓ). C’est également la com-
plexité des deux opérations de recopiage qui sont effectuées séquentiellement. Au total,
la complexité de cette fonction est donc O(m + ℓ).

4.6 Vue récursive

Tous les algorithmes étudiés dans ce chapitre sont des algorithmes de type itératif.
Néanmoins, on peut trouver une version récursive pour la plupart d’entre eux. Pour ce
faire, il faut d’abord trouver une définition récursive de la notion de liste. La voici :

Définition 2 Une liste est :

1. Soit la liste vide NIL ;
2. Soit un élément (la tête) suivi d’une liste.

Ainsi, une liste contenant un seul élément est vue comme un élément suivi de la
liste vide. Une liste de k éléments est un élément suivi d’une liste de k − 1 éléments,
etc.

4.6.1 Algorithmes
Il est maintenant aisé de donner des algorithmes récursifs sur les listes. À titre
d’exemple, nous considérons la recherche d’une valeur i et l’insertion en ke position.
Ces algorithmes sont présentés à l’Algorithme 22.

La recherche d’une valeur i La fonction Recherche reçoit une liste L et une valeur
i, et renvoie un pointeur vers la première occurrence d’un élément contenant i, ou NIL
s’il n’existe pas de tel élément. Dans le cas où la liste L est la liste vide, la fonction
peut directement renvoyer NIL. Sinon, la liste est composée d’une tête, et d’une liste
dont la tête est [Link]. Dans ce cas, deux possibilités se présentent. Soit la tête contient
i, auquel cas la fonction renvoie L. Soit la tête ne contient pas i, et la fonction effectue
un appel récursif pour obtenir un pointeur vers un élément contenant i dans la liste dont
la tête est [Link].
70 CHAPITRE 4. LES LISTES

FusionVecteurListe(Entier V [n], Entier ℓ, Entier W [m])

début
Entier tmp[n], N[n], L, i, j, k ;
i := 1 ;
tant que i ≤ ℓ − 1 faire
N[i] := i + 1 ;
N[ℓ] := −1 ;

i := 1 ;
j := 1 ;
k := −1 ;
tant que j ≤ m faire
V [ℓ + j] := W [ j] ;
tant que i 6= −1 et V [i] < W [ j] faire
k := i ;
i := N[i] ;
si k = −1 alors
N[ j + ℓ] := L ;
L := j + ℓ ;
sinon
N[k] := j + ℓ ;
N[ j + ℓ] := i ;
j := j + 1 ;

i := 1 ;
j := 1 ;
tant que i 6= −1 faire
tmp[i] := V [ j] ;
i := i + 1 ;
j := N[ j] ;
i := 1 ;
tant que i ≤ ℓ + m faire
V [i] := tmp[i] ;
i := i + 1 ;
fin
Algorithme 21 : Une solution au problème de fusion des vecteurs triés, version
« listes ».
4.6. VUE RÉCURSIVE 71

L’insertion d’un élément à la ke position La fonction InsèreKPos reçoit une liste

L, un entier k et un entier i, et insère un nouvel élément d’information i à la ke position
dans L (ou affiche un message d’erreur si cela n’est pas possible). Dans le cas où la
liste est vide, l’insertion se fait en tête, et n’est possible que si k = 1. Dans le cas où la
liste n’est pas vide, on a deux possibilités. Soit k = 1, et on effectue l’insertion en tête.
Soit k 6= 1, et on effectue un appel récursif pour insérer l’élément dans liste dont la tête
est [Link]. Attention, dans ce cas, la position d’insertion change : elle devient k − 1,
puisque la liste considérée pour l’appel récursif possède un élément de moins en tête.

Elem * Recherche(Elem * L, Entier i)

début
si L = NIL ou [Link] = i alors
retourner L ;
sinon
retourner Recherche([Link], i) ;
fin

InsèreKPos(Elem * &L, Entier k, Entier i)

début
Elem * p ;
si k = 1 alors
p :=new Elem ;
[Link] := i ;
[Link] := L ;
L := p ;
sinon si L 6= NIL alors
InsèreKPos([Link], k − 1, i) ;
sinon
Afficher « Erreur : insertion impossible. »
fin
Algorithme 22 : Deux algorithmes récursifs sur les listes.
72 CHAPITRE 4. LES LISTES
Chapitre 5

Les piles et les files

Dans ce chapitre, nous allons étudier deux nouvelles structures de données très
couramment utilisées : les files et les piles.
Les noms de ces structures évoquent clairement leur fonctionnement respectif. Une
file (ou queue en anglais) contiendra des informations ordonnées de façon linéaire
(comme dans une liste). Comme dans une file d’attente dans un commerce, il ne sera
possible d’ajouter de l’information qu’à la fin de la file, et de n’en prélever qu’au début.
Une pile (ou stack en anglais), au contraire, se comportera comme une pile d’assiettes :
on n’aura accès qu’à l’information se trouvant au sommet de la pile, que ce soit lors de
l’ajout ou lors de la lecture.
Les files et les piles ont énormément d’applications en informatique. Elles sont
présentes dans de nombreux composants d’un système d’exploitation. Elles sont égale-
ment nécessaires pour définir de façon simple et élégante certains algorithmes, comme
nous les verrons à la fin de ce chapitre, et dans le chapitre suivant.
Étant donné que les informations stockées dans une file ou dans une pile le sont
de façon linéaire, on aura souvent recours soit aux listes, soit aux tableaux pour implé-
menter ces structures.

5.1 Les piles

Une pile est un type de données formé d’une séquence d’éléments a1 , a2 , . . . , an .
Les opérations autorisées sur la pile sont des manipulations de l’extrémité de la sé-
quence, que l’on appelle le sommet de la pile. En effet, on représente une pile comme
un empilement d’éléments, l’élément a1 étant dans le fond de la pile, avec l’élément
a2 au-dessus de lui, etc, jusqu’à avoir an au sommet. Cette représentation intuitive est
montrée à la Fig. 5.1.
Les opérations autorisées sur la pile sont les suivantes :
PileVide Cette opération crée une nouvelle pile, vide. On représentera souvent la pile
vide par ε (c’est-à-dire la séquence vide).
Push Cette opération reçoit en paramètre une pile (vide ou non) et un élément. Elle
ajoute l’élément au sommet de la pile. Plus précisément, si la pile contient la
séquence a1 , a2 , . . . , an , et que l’élément à ajouter est x, la pile résultante sera
a1 , a2 , . . . , an , x. Si la pile reçue est vide, la pile résultante sera simplement x.
Pop Cette opération est symétrique de Push. Elle reçoit une pile, et supprime l’élé-
ment au somment de la pile, s’il existe. Plus formellement, si la pile reçue est

73
74 CHAPITRE 5. LES PILES ET LES FILES

F IG . 5.1 – Un exemple de pile contenant (de bas en haut) les valeurs 2, 3, 4 et 5.

a1 , . . . , an , avec n ≥ 2, la pile résultante est a1 , . . . , an−1 . Si la pile reçue est a1 , la

pile résultante est ε . On ne peut pas faire de Pop sur une pile vide.
Top Cette opération permet de consulter l’information stockée dans la pile. Suivant
la politique de la pile, qui ne donne accès qu’à son sommet, on ne peut consul-
ter que l’information stockée au sommet de la pile. Top reçoit donc une pile
a1 , . . . an , et renvoie an . Top n’est pas définie quand la pile est vide.
EstVide Cette opération reçoit une pile et dit si la pile est vide ou non. Elle renvoie
donc vrai si et seulement si la pile reçue est ε .

Exemple 16 Considérons une pile initialement vide ε . Si nous effectuons le Push de

trois valeurs 5, 7 et 9 (successivement), nous obtenons la pile 5, 7, 9 (le fond est bien
en début de séquence). L’opération EstVide retourne alors faux. En faisant un Pop,
on obtient la pile 5, 7. L’opération Top renvoie alors 7. Avec deux nouveaux Pop, on
obtient la pile vide ε . Il n’est plus possible de faire de Pop ou de Top.

On voit donc que la politique d’accès à la pile ne permet de consulter que l’élément
le plus récemment inséré dans la pile, car c’est celui qui est présent au sommet. Au-
trement dit, le premier élément qu’on pourra supprimer d’une pile est celui qui a été
inséré en dernier. Cette constatation, qui résume bien les opérations propres à la pile,
est exprimée en anglais par last in, first out, abrégé en LIFO.

5.1.1 Implémentation dans une liste

Comme nous l’avons dit dans l’introduction de ce chapitre, la structure d’une pile
est la même que celle d’une liste. La différence tient dans les manipulations qui sont
autorisées (des opérations comme la suppression du ke élément, par exemple, ne seront
pas autorisées).
On peut donc tout naturellement implémenter une pile dans une liste. Pour faciliter
les opérations, il est plus commode de stocker le sommet de la pile en tête de liste, étant
5.1. LES PILES 75

5 4 3 2 N I L

F IG . 5.2 – La pile de la Fig. 5.1 implémentée dans une liste.

donné que c’est la seule partie de la pile que nous devrons manipuler directement. Les
éléments sont donc stockés dans la liste de haut en bas. La Fig. 5.2 illustre cela.
Ainsi, il est facile d’implémenter les opérations sur la pile à l’aide des opérations
sur la liste :
PileVide Créer une pile vide revient à créer une liste vide, grâce à ListeVide.
Push Le Push revient à effectuer une insertion en tête dans la liste, ce qui peut se faire
à l’aide d’InsèreTête.
Pop Le Pop revient à faire une suppression en tête, à l’aide de SuppressionPremier.
Top Le Top revient à consulter l’information stockée dans le premier élément, auquel
on accède à l’aide de la fonction PremierElem.
EstVide La pile est vide si et seulement si la liste est vide. On fait donc appel à
EstVide.
Remarquons que toutes ces fonctions sont correctes indépendemment du type de liste
(simplement ou doublement liée, avec ou sans élément pré-tête) choisi.
Comme une pile est une liste, on définira le type Pile comme une structure conte-
nant simplement un pointeur vers la tête de la liste. Ainsi, on cache les détails d’implé-
mentation, et les signatures des fonctions seront les mêmes si on choisit d’implémenter
la pile autrement (voir section suivante) :
struct Pile
Elem * som ;

À titre d’exemple, l’Algorithme 23 donne le code de ces cinq primitives dans le cas
d’une pile d’entiers.

5.1.2 Implémentation dans un vecteur

Naturellement, il est également possible d’implémenter une pile dans un vecteur.
L’idée consiste à stocker les éléments de bas en haut, c’est-à-dire en mettant l’élément
au fond de la pile dans la première case du vecteur, etc. Cette disposition est naturelle
car la pile ne peut croître que par son sommet. Si celui-ci était stocké au début du
vecteur, on serait obligé de recourir à des tassements et des déplacements du vecteur
à chaque Push ou Pop, pour garder le sommet dans la première case et ne pas perdre
d’information.
Afin de pouvoir réaliser les opérations sur le sommet, il est nécessaire de retenir
où celle-ci se situe dans le vecteur. Cela peut se faire à l’aide d’une variable entière,
qui indique l’indice de la case contenant le sommet. Dans le cas où la pile est vide, on
prendra une valeur conventionnelle (0 par exemple).
76 CHAPITRE 5. LES PILES ET LES FILES

PileVide(Pile & P)
début
ListeVide([Link]) ;
fin

Push(Pile &P, Entier i)

début
InsèreTête([Link], i) ;
fin

Pop(Pile &P, Entier i)

début
SuppressionPremier([Link]) ;
fin

Entier Top(Pile P)
début
Elem * p :=PremierElem([Link]) ;
retourner [Link] ;
fin

Booléen EstVide(Pile P)
début
retourner EstVide([Link]) ;
fin
Algorithme 23 : L’implémentation d’une pile d’entiers dans une liste.
5.2. LES FILES 77

On implémentera donc la pile à l’aide d’un vecteur V et d’une variable entière som,
telles que V [som] contient l’information au sommet de la pile. Dans le cas présent, une
pile sera donc plutôt un enregistrement du type :
struct Pile
Entier V [n] ;
Entier som ;

Les opérations sont alors faciles à implémenter :

PileVide Cette opération consiste simplement à initialiser la variable som à 0 pour
indiquer que le vecteur ne contient pas d’éléments de la pile.
Push La nouvelle information peut être stockée en V [som + 1], et som doit être incré-
mentée. Cette opération suppose que le vecteur V est de taille suffisante pour
accueillir le nouvel élément.
Pop Le Pop consiste simplement à décrémenter la variable som. Remarquons que cette
décrémentation est bien cohérente avec notre choix de mettre [Link] à 0 quand la
pile est vide.
Top Il suffit de renvoyer l’information stockée au sommet, c’est-à-dire dans V [som].
EstVide La pile est vide si et seulement si la variable som vaut 0.
Ces opérations sont détaillées à l’Algorithme 24.

5.2 Les files

Une file est également une séquence a1 , a2 , . . . , an d’éléments, mais les opérations
applicables diffèrent par rapport à la pile. Dans une file, l’écriture et la lecture ne se
font pas « au même endroit » : on peut ajouter une information en début de file, mais
on n’a le droit d’écrire qu’à la fin de la file.
Plus formellement, si la file contient la séquence a1 , a2 , . . . , an , on appellera a1 le
début de la file, et an la fin de la file. L’écriture d’une information x se fait à la fin
et donne lieu à la file a1 , a2 , . . . an , x. La lecture se fait au début et donne lieu à la file
a2 , . . . , an . Les opérations autorisées sur file sont les suivantes :
FileVide Cette opération crée une file vide (dénotée par ε ).
Enqueue Cette opération reçoit une file et un élément x en paramètre, et ajoute x
dans la file. Si la file est constituée de la séquence a1 , a2 , . . . , an , on obtient la
file contenant la séquence a1 , a2 , . . . , an , x. Si la file est vide, on obtient la file
contenant la séquence x.
Dequeue Cette opération reçoit une file et supprime l’élément en début de file. Si la
file reçue est a1 , . . . , an , avec n ≥ 2, la file résultante est a2 , . . . , an . Si la file reçue
est a1 , la file résultante est la file vide ε . Naturellement, la suppression n’est pas
autorisée sur une file vide.
First Cette opération reçoit une file et renvoie l’élément en début de file. Cette opéra-
tion n’est pas autorisée sur une file vide. Par contre, si la file reçue est a1 , . . . , an ,
le résultat est a1 .
EstVide Cette opération reçoit une file et renvoie vrai si et seulement si la file est vide.

Exemple 17 Considérons la file vide ε . Effectuons trois Enqueue successifs des va-
leurs 5, 7 et 9. On obtient alors la file 5, 7, 9 (c’est-à-dire la même séquence que dans
78 CHAPITRE 5. LES PILES ET LES FILES

PileVide(Pile & P)
début
[Link] := 0 ;
fin

Push(Pile & P, Entier i)

début
[Link] := [Link] + 1 ;
P.V[[Link]] := i ;
fin

Pop(Pile & P)
début
[Link] := [Link] − 1;
fin

Entier Top(Pile & P)

début
retourner P.V[[Link]] ;
fin

Booléen EstVide(Pile & P)

début
si [Link] = 0 alors
retourner vrai ;
sinon
retourner faux ;
fin
Algorithme 24 : L’implémentation d’une pile d’entiers dans un vecteur.
5.2. LES FILES 79

le cas de la pile). Un Dequeue donne la file 7, 9. Appliquées à cette file, l’opération

First renvoie 7, et l’opération EstVide renvoie faux. En faisant deux Dequeue supplé-
mentaires, on ré-obtient la file vide, sur laquelle ni Dequeue ni First ne peuvent être
appliqués.

5.2.1 Implémentation dans une liste

Il est aisé d’implémenter une file dans une liste. On choisira de mettre le début
de la file en tête de liste, et la fin de la file en fin de liste. Le type File sera alors :
struct File
Elem * deb ;

Cette convention étant fixée, il est facile de traduire les opérations sur une file en
terme d’opérations sur une liste :
FileVide revient à créer une liste vide.
Enqueue revient à ajouter un élément en fin de liste.
Dequeue revient à effectuer une suppression en tête.
First revient à renvoyer l’information stockée dans l’élément de tête.
EstVide revient à tester si la liste est vide.
L’Algorithme 25 détaille ces opérations.

FileVide(File & F)
début
ListeVide([Link]) ;
fin

Enqueue(File & F, Entier i)

début
InsèreFin([Link], i) ;
fin

Dequeue(File & F)
début
SuppressionPremier([Link]) ;
fin

Entier First(File F)
début
Elem * p := PremierElem([Link]) ;
retourner [Link] ;
fin

Booléen EstVide(File & F)

début
retourner [Link] ;
fin
Algorithme 25 : L’implémentation d’un file dans une liste, avec un seul pointeur.
80 CHAPITRE 5. LES PILES ET LES FILES

Remarquons que toutes ces opérations s’effectue en temps constant, sauf l’opéra-
tion Enqueue, qui demande de parcourir toute la liste pour insérer en fin, ce qui est en
O(n). Cette complexité peut être ramenée à O(1) si on garde en permanence un poin-
teur vers le dernier élément de la liste (en plus du pointeur vers la tête). On considère
alors un type File défini comme suit :
struct File
Elem * deb ;
Elem * fin ;

On peut alors adapter les algorithmes manipulant les files pour tenir compte de cette
nouvelle structure. Ceux-ci sont donnés à l’Algorithme 26. Remarquons que, comme
nous utilisons une structure quelque peu différente des listes chaînées simples, nous
sommes obligés d’écrire des algorithmes ad hoc, ce qui est quelque peu moins élégant
que la solution présentée à l’Algorithme 25.
Voici le détail de ces fonctions :
FileVide Il faut prendre garde à mettre la valeur NIL tant dans le pointeur de début
que dans le pointeur de fin.
Enqueue L’accès à la fin de la liste est maintenant simplifié grâce au pointeur de fin.
Il faut d’abord créer l’élément à ajouter, avec l’information i, et le champ next
à NIL (puisque cet élément deviendra le dernier de la liste). Ensuite, on ajoute
le nouvel élément à la suite de celui pointé par [Link], à condition que ce dernier
pointeur ne soit pas nul. Dans le cas contraire, la file est en fait vide, et il suffit
de faire pointer à la fois [Link] et [Link] sur le nouvel élément.
Dequeue La suppression en tête se fait de la même manière que dans une liste simple,
en utilisant [Link] comme pointeur tête. Il faut prendre garde à stocker NIL dans
[Link] si cette suppression donne lieu à une file vide (c’est-à-dire si la file ne
contenait qu’un seul élément avant la suppression).
First Cette opération revient à renvoyer l’information stockée dans l’élément de tête.
EstVide Cette opération revient à tester si la liste est vide, ce qui peut se vérifier en
testant un des deux pointeurs.

5.2.2 Implémentation dans un vecteur

Comme dans le cas des piles, il est possible d’implémenter une file dans un vecteur.
La question de l’ordre de stockage se pose à nouveau. Néanmoins, contrairement au cas
de la file, il n’y a pas d’ordre meilleur qu’un autre. En effet, tant le début que la fin de
la file peuvent évoluer, alors que dans le cas de la pile, seul le sommet pouvait être
modifié.
On devra donc repérer dans le vecteur V (qui contient les élément de la file), deux
positions deb et f in. On adoptera donc le type suivant :
struct File
Entier V [n] ;
Entier deb ;
Entier f in ;

On stockera les éléments de la file entre les cases deb et f in − 1 (comprises), du

début à la fin de la file. Initialement, nous aurons deb = f in = 1, ce qui produit bien
une file vide (il n’y a pas de cases entre les indices 1 et 0). On stockera les nouvelles
5.2. LES FILES 81

FileVide(File & F)
début
[Link] := NIL ;
[Link] := NIL ;
fin

Enqueue(File & F, Entier i)

début
Elem * p :=new Elem ;
[Link] := i ;
[Link] := NIL ;
si FileVide(F) alors
[Link] := p ;
[Link] := p ;
sinon
[Link] := p ;
[Link] := p ;
fin

Dequeue(File & F)
début
Elem * p := [Link] ;
[Link] := [Link] ;
delete p ;
si [Link] = NIL alors
[Link] := NIL ;
fin

Entier First(File F)
début
retourner [Link] ;
fin

Booléen EstVide(File & F)

début
si [Link] = NIL alors
retourner vrai ;
sinon
retourner faux ;
fin
Algorithme 26 : L’implémentation d’un file dans une liste, avec deux pointeurs.
82 CHAPITRE 5. LES PILES ET LES FILES

valeurs dans la case f in, que l’on incrémentera alors. Symétriquement, un Dequeue
s’obtiendra simplement en incrémentant deb.
Malheureusement, cette simple politique de gestion du vecteur ne saurait être sa-
tisfaisante. Observons l’exemple de la Fig. 5.3. On y a représenté différentes étapes de
manipulation d’un vecteur contenant une file, et la file correspondante. Initialement, la
file est vide. On effectue ensuite 4 Enqueue, ce qui fait croître la valeur de f in. Puis,
on effectue deux Dequeue. Comme on le voit sur la figure, les cases 1 et 2 deviennent
alors inutilisables, car les éléments qui seront ensuite ajoutés apparaîtront à droite de
la case d’indice f in. Lorsque cet indice atteindra la dernière case du vecteur, il ne sera
plus possible de faire de nouveaux Enqueue. Ainsi, chaque Dequeue diminue la taille
potentielle de la file.
On peut palier ce problème en considérant que le vecteur est circulaire, tel qu’illus-
tré à la Fig. 5.4. Cela signifie qu’on considère qu’il existe une case « à droite » de la
case d’indice n, qui est la case d’indice 1. Ainsi, quand on incrémente f in ou deb, et
que la valeur d’un des deux dépasse n, il convient de la remettre à 1. Ceci peut aisément
s’obtenir à l’aide de l’opérateur modulo.
Dans le cadre de ce cours, nous avons adopté la convention de numéroter les cases
du vecteur de 1 à n. Ainsi, l’opération d’incrémentation « circulaire » d’un indice i
parcourant le tableau est i := (i mod n) + 1. Dans le cas où les cases sont numérotées
de 0 à n − 1 (comme dans le langage C ou C++, par exemple), l’opération devient
i := (i + 1)mod n.
Avec cette politique de gestion du vecteur, si la file est stockée dans un vecteur de
taille n, il est à tout moment possible d’y maintenir au plus n éléments, et ce, quelque
soient les opérations qui ont déjà été effectuées. Les fonctions qu’on obtient alors sont
données à l’Algorithme 27. Voici leurs descriptions :
FileVide Il suffit de stocker 1 dans [Link] et [Link].
Enqueue La nouvelle valeur doit être stockée dans la case d’indice [Link] (pour rappel,
cet indice indique la première case libre, et non pas la dernière case occupée).
On doit ensuite incrémenter [Link], en tenant compte du caractère circulaire du
vecteur.
Dequeue Cette opération consiste simplement à incrémenter [Link], de façon circu-
laire. Les informations supprimées restent dans le vecteur, mais sont ignorées.
First La case contenant le début de la file est celle d’indice [Link]. On renvoie simple-
ment son contenu.
EstVide La file est vide si et seulement si les indices de début de fin sont égaux.
Attention, ils ne sont pas forcément égaux à 1 (ils peuvent avoir avancé au fur et
à mesure des Enqueue et Dequeue).

5.3 Applications
Terminons ce chapitre en présentant deux applications des piles (nous verrons
d’autres applications des piles et des files dans le chapitre suivant).
Outre ces applications que nous donnons à titre d’exemple, rappelons tout de même
que les files et les piles ont de nombreuses applications dans les systèmes d’exploita-
tion et les compilateurs. La partie de la mémoire qui retient le contexte d’un processus
lorsque celui-ci est swappé out est gérée comme une pile (il s’agit du stack système).
5.3. APPLICATIONS 83

d e b

fi n

? ? ? ? ?

d e b fi n

5 7 9 1 1

d e b fi n

5 7 9 1 1

fi n d e b

5 7 9 1 1 1 3

F IG . 5.3 – Un exemple de manipulation de file dans un vecteur. Les cases grisées sont
celles qui font partie de la file.
84 CHAPITRE 5. LES PILES ET LES FILES

F IG . 5.4 – Le vecteur implémentant la file vu comme un vecteur circulaire. Les cases

grisées sont celles qui font partie de la file.
5.3. APPLICATIONS 85

FileVide(File F)
début
[Link] := 1 ;
[Link] := 1 ;
fin

Enqueue(File F, Entier i)
début
F.V[[Link]] := i ;
[Link] := ([Link] n) + 1 ;
fin

Entier Dequeue(File F, Entier i)

début
Entier R := F.V[[Link]] ;
[Link] := ([Link] n) + 1 ;
retourner R ;
fin

Booléen EstVide(File F)
début
si [Link] = [Link] alors
retourner vrai ;
sinon
retourner faux ;
fin
Algorithme 27 : L’implémentation d’un file dans une vecteur (circulaire).
86 CHAPITRE 5. LES PILES ET LES FILES

Un compilateur gère les contextes des fonctions à l’aide d’une pile également : la fonc-
tion courante a son contexte stocké au sommet de la pile, et les fonctions appelantes
ont leurs contextes respectifs stockés dans la pile, selon l’ordre des appels. Ainsi, un
appel de fonction correspond à un Push, et un retour à un Pop. Enfin, les files trouvent
une application naturelle chaque fois qu’une file d’attente est nécessaire, comme, par
exemple, dans un spooler d’impression, ou dans un serveur web.

5.3.1 Vérification des parenthèses

La première application consiste à écrire un algorithme qui vérifie si une expression
est bien parenthésée. Nous considérerons des expressions arithmétiques, formées de
nombres entiers et des quatre opérateurs. Ces expressions pourront être parenthésées à
l’aide de deux types de parenthèses différentes : () et [].
Une expression est dite est bien parenthésée si :
1. Pour toute parenthèse fermante d’un certain type, il existe une parenthèse ou-
vrante du même type qui la précède, et qui n’a pas encore été fermée.
2. Toute parenthèse ouvrante d’un certain type est fermée par une parenthèse fer-
mante du même type.

Exemple 18 Les expressions suivantes sont bien parenthésées :

– ([3 + 5] ∗ (2 ∗ 9))
– 1+4
– ([(2)])
Les expressions suivantes ne sont pas bien parenthésées :
– (3 + 5] : les types de parenthèses ne correspondent pas.
– ((3) : une des deux parenthèses n’a pas été fermée.
– (4)) : on ferme une parenthèse qui n’a pas été ouverte.

L’algorithme que nous proposons reçoit une expression S, telle que décrite ci-
dessus, et accède à chacun des n éléments qui la composent séquentiellement, et que
nous dénotons par S1 , S2 , . . . , Sn . Par exemple, dans (13+2), nous avons S1 =), S2 = 13,
S3 = +, etc.
Cet algorithme considère chaque élément Si l’un après l’autre (i = 1, . . . n). À tout
moment, il doit savoir quelles sont les parenthèses qui sont encore ouvertes, et il doit
également savoir dans quelle ordre ces parenthèses ont été ouvertes. Ainsi, quand il
rencontre une parenthèse fermante, il doit simplement comparer cette parenthèse fer-
mante à la dernière parenthèse ouvrante qui n’a pas encore été fermée, et vérifier que
les types correspondent.
On voit donc qu’il est nécessaire de pouvoir stocker toutes les parenthèses ou-
vrantes, dans l’ordre où elles ont été rencontrées, tout en ne devant maintenir un accès
direct qu’à la dernière parenthèse ouverte qui n’a pas encore été fermée. Ceci peut
aisément être obtenu à l’aide d’une pile :
– À chaque parenthèse ouvrante rencontrée, on effectue un Push.
– À chaque parenthèse fermante rencontrée, on vérifie que la pile n’est pas vide à
l’aide de EstVide. Si la pile est vide, on a trouvé une parenthèse fermante qui
n’a pas été ouverte. Sinon, on vérifie à l’aide de Top que la parenthèse fermante
correspond bien à la dernière parenthèse ouvrante, et on effectue une Pop.
– On ignore les autres caractères.
5.3. APPLICATIONS 87

À la fin du parcours de l’expression, la pile doit être vide, car, dans le cas contraire,
cela signifie qu’une parenthèse ouvrante n’a pas été fermée. L’Algorithme 28 présente
cette solution.

Booléen VérifierParenthèses(Expression S, Entier n)

début
Entier i = 1 ;
Pile P ;
PileVide(P) ;
tant que i ≤ n faire
si Si = ( ou Si = [ alors
Push(P, Si ) ;
sinon si Si =) alors
si EstVide(P) ou Top(P) 6= ( alors
retourner faux ;
sinon
Pop(P) ;
sinon si Si =] alors
si EstVide(P) ou Top(P) 6= [ alors
retourner faux ;
sinon
Pop(P) ;
i := i + 1 ;
si EstVide(P) alors
retourner vrai ;
sinon
retourner faux ;
fin
Algorithme 28 : Un algorithme pour vérifier qu’une expression est bien parenthésée.

5.3.2 Évaluation d’une expression en notation postfixée

La seconde application consiste à donner une algorithme qui évalue une expression
arithmétique en notation postfixée. Ces expressions sont quelque peu différentes des
expressions « classiques », en ce sens que les opérateurs arithmétiques sont placés
après les deux opérandes, et non pas entre les deux opérandes.

Exemple 19 Par exemple, l’expression 3 + 2 s’écrit 3 2 + en notation postfixée.

L’expression (3 + 2) ∗ 5 est le produit de l’expression 3 + 2 et de l’expression 5. La
première se note 3 2 + en notation postfixée, et la seconde reste 5. Le produit des deux
se note donc 3 2 + 5 ∗.
Comme on le voit, l’avantage de cette notation est qu’elle permet de se passer des
parenthèses, la priorité étant implicite.

Pour évaluer1 une expression S en notation postfixée, on procède comme suit. On

inspecte chaque élément Si de l’expression l’un après l’autre. Si nous rencontrons un
1
Ce problème n’est pas purement théorique : de nombreux compilateurs convertissent les expressions
arithmétiques en expressions postfixées, et les évaluent, ou génèrent le code pour les évaluer selon un algo-
rithme similaire à celui que nous allons présenter.
88 CHAPITRE 5. LES PILES ET LES FILES

entier, nous devons le retenir jusqu’à ce que nous trouvions l’opérateur qui va lui être
appliqué (et qui le suit forcément). Chaque fois que nous rencontrons un opérateur,
nous savons qu’il s’applique aux deux dernières valeurs calculées. Nous devons donc
retenir toutes les valeurs qui ont été lues, et qui n’ont pas encore servi dans une opé-
ration. Ces valeurs doivent être retenues dans l’ordre où elles ont été lues. Après avoir
effectué le calcul, nous devons également retenir le résultat, puisqu’il pourrait lui aussi
être l’opérande d’un autre opérateur (par exemple, dans 3 2 + 5 ∗, il faut retenir le
résultat de 3 2 +, puisqu’il devra être multiplié par 5).
À nouveau, nous voyons que la mémoire dont nous avons besoin suit une politique
de pile : à tout moment, nous devons retenir toutes les dernières valeurs lues ou cal-
culées, et ce, dans l’ordre où elles l’ont été. Mais pour appliquer un opérateur, nous
n’avons besoin que des deux dernières valeurs.
Notre algorithme parcourra donc l’expression depuis Si jusqu’à Sn , et fonctionnera
ainsi :
– Chaque valeur entière rencontrée est stockée sur la pile grâce à Push.
– À chaque opérateur, on Pop les deux dernières valeurs de la pile, on effectue
l’opération et on Push le résultat.
À la fin, la valeur de l’expression se trouve au sommet de la pile. L’Algorithme 29
présente cette procédure.
5.3. APPLICATIONS 89

Entier ÉvaluationPostFix(Expression S, Entier n)

début
Entier i := 1, x1 , x2 ;
Pile P ;
PileVide(P) ;
tant que i ≤ n faire
si Si = + alors
x1 := Top(P) ;
Pop(P) ;
x2 := Top(P) ;
Pop(P) ;
Push(P, x2 + x1 ) ;
sinon si Si = − alors
x1 := Top(P) ;
Pop(P) ;
x2 := Top(P) ;
Pop(P) ;
Push(P, x2 − x1 ) ;
sinon si Si = ∗ alors
x1 := Top(P) ;
Pop(P) ;
x2 := Top(P) ;
Pop(P) ;
Push(P, x2 ∗ x1 ) ;
sinon si Si = / alors
x1 := Top(P) ;
Pop(P) ;
x2 := Top(P) ;
Pop(P) ;
Push(P, x2 /x1 ) ;
sinon
Push(P, Si ) ;
i := i + 1 ;
retourner Top(P) ;
fin
Algorithme 29 : Un algorithme pour évaluer une expression postfixeé.
90 CHAPITRE 5. LES PILES ET LES FILES
Chapitre 6

Les arbres

6.1 Introduction
Les structures que nous avons considérées jusqu’à présent sont uniquement des
structures linéaires, dans le sens où :
1. chaque élément de la structure possède au plus un prédécesseur direct, et
2. chaque élément de la structure possède au plus un successeur direct.
En effet, dans un tableau de taille n, chaque case i (pour 1 < i < n) possède comme
unique prédécesseur la case i − 1, et comme unique successeur la case i + 1. La case
0 n’a pas de prédécesseur, mais la case 1 est son unique successeur. La case n n’a elle
pas de successeur, mais bien un prédécesseur : la case n − 1. Dans les listes, chaque
élément possède un seul et unique champ next, qui référence un successeur unique, ou
qui contient un valeur conventionnelle pour indiquer qu’il n’y a pas de successeur. Par
ailleurs, la tête n’a pas de prédécesseur, et, pour tous les autre éléments e , il n’existe
qu’un seul autre élément e′ dont le champ next référence e. Enfin, les piles et files sont
essentiellement des listes.
Nous allons considérer, dans ce chapitre, une généralisation de ces structures li-
néaires en levant la restriction numéro 2 : chaque élément aura au plus un seul prédé-
cesseur, mais sera autorisé à avoir plusieurs successeurs1 . On a dès lors affaire à une
structure qui se ramifie, puisque, lors d’un parcours de cette structure, on a, à chaque
élément, plusieurs choix possibles pour « continuer le parcours ». C’est pour cette rai-
son que ce type de structures est appelé un arbre2 .

L’importance des arbres en informatique est considérable. D’une part, les struc-
tures de type arborescent se rencontrent naturellement dans plusieurs cas pratiques de
la vie quotidienne que l’on désire modéliser et manipuler à l’aide d’algorithmes. Par
exemple l’organisation hiérarchique d’une entreprise est un arbre. La Fig. 6.1 en donne
un exemple. D’autre part, les arbres jouent un rôle très important dans de nombreux
algorithmes, et ils sont la clef de voûte indispensable pour rendre ces algorithmes effi-
caces. Sans arbre, pas de base de données, pas de système de fichiers, pas de compres-
sion MP3, etc.
1 Nous supposerons également qu’il n’y a pas de cycle dans la structure.
2
Remarquons que si nous relâchons les deux hypothèses ci-dessus, à savoir qu’on autorise également
chaque élément à avoir plusieurs prédécesseurs, on obtient un graphe. Nous n’aborderons pas les graphes
dans ce cours.

91
 F IG . 6.1 – Un exemple d’arbre, qui représente l’organisation hiérarchique d’une entreprise (un peu fantaisiste).

e
r
e
l
t
c
e
i
s
d
e
v
n
r
h
ä
e
c
H
S r
O
e
n
n
n
o
i
a
q
u
m
s
o
i
e
r
l
v
i
e
a
T
D
b
"
e
n
e
s
c
n
o
i
i
h
v
ug
t
ü
i
r
r
r
s
e
B
O
o
S
p
m
h
o
c
a
c
"
B
.
t
S
.
n
J
e
m
n
e
e
r
n
t
c
i e a
r
m
v d
a
u
r
e
p
i
h
e
é
c
L
S
S
D
e
t
n
u q
r
i
o
e
i
t
b
s
n
i
u
h
a
v
i
c
m
S
D
o
e
i
r
n
e
e
n
c
v
i
o
o
v
h
h
t
r
p
e
e
m
e
S
y
B
S
CHAPITRE 6. LES ARBRES 92
6.1. INTRODUCTION 93

6.1.1 Définitions
Il est possible de donner deux types de définitions des arbres : une définition « clas-
sique », en termes d’ensembles ; ou bien une définition récursive. Suivant la définition
qu’on adopte, on pourra formuler les algorithmes de façon itérative ou récursive.
Voici d’abord la définition ensembliste :

Définition 3 Un arbre est une structure de données composée d’un ensemble N de

nœuds. Chaque nœud n est composé d’une information Λ (n) et d’un ensemble Succ (n)
de nœuds successeurs. Par ailleurs, un et un seul nœud de N est appelé la racine,
dénoté r.
Ces éléments respectent les conditions suivantes :
1. r n’a pas de prédécesseur : pour tout nœud n ∈ N, r 6∈ Succ (n).
2. Chaque nœud n’a pas plus d’un prédécesseur : pour tout nœud n ∈ N, il n’existe
pas de paire de nœuds n1 et n2 tels que n1 6= n2 , n ∈ Succ (n1 ) et n ∈ Succ(n2 ).
3. On peut accéder à chaque nœud depuis la racine : pour tout nœud n, il existe
une séquence n1 n2 , . . . , nk de nœuds telle que : n1 = r, nk = n et, pour tout 1 ≤
i ≤ k − 1 : ni+1 ∈ Succ (ni ).

Remarquons que les points 2 et 3 de cette définition obligent chaque nœud (à part
la racine) à posséder exactement un prédécesseur. En effet, le point 2 indique que le
nombre de prédécesseur de chaque nœud est ≤ 1, et le point 3 implique que chaque
nœud (à part la racine) doit posséder un nombre de prédécesseurs ≥ 1.
Illustrons cette définition à l’aide d’un exemple :

Exemple 20 La Fig. 6.2 présente un exemple d’arbre à 7 nœuds. La relation « a pour

successeur » est représentée par une flèche. Nous avons donc N = {n1 , n2 , . . . , n7 }. La
racine est le nœud r = n1 : elle est bien dépourvue de prédécesseur. Elle possède 3
successeurs : Succ (n1 ) = {n2 , n3 , n4 }. Certains nœuds n’ont pas de successeur, comme
par exemple : n3 ou n9 . Tous les nœuds ont au plus 1 prédécesseur, et sont accessibles
à partir de la racine. Par exemple, on accède à n7 , via la séquence n1 n4 n7 .

Comme on le voit, la définition d’un arbre est plus complexe que celle d’une liste ou
d’une autre séquence linéaire. On peut néanmoins obtenir une définition relativement
simple si on admet une définition récursive :

Définition 4 Un arbre est :

1. soit l’arbre vide
2. soit un nœud n appelé racine et un ensemble (potentiellement vide) {A1 , A2 , . . . , An }
d’arbres non-vides appelés sous-arbres.
À chaque nœud est associée une information Λ (n).

Illustrons cette définition :

Exemple 21 Reprenons l’arbre de la Fig. 6.2. Nous avons illustré la vue récursive de
cette arbre à la Fig. 6.3. Cet arbre est maintenant vu de la façon suivante : il est com-
posé du nœud n1 (qui constitue sa racine) et de trois sous-arbres A, B et C, représentés
en grisé sur la figure. A est un arbre dont la racine est n2 , et dont les sous-arbres sont
D et E. C est un arbre dont la racine est n4 et dont le sous-arbre est F. B, D, E et F
sont des arbres composés de leur seule racine (respectivement n3 , n5 , n6 , n7 ).
94 CHAPITRE 6. LES ARBRES

F IG . 6.2 – Un exemple d’arbre. Les informations associées aux nœuds ne sont pas
représentées.

n 1

A B C

n 2 n 3 n 4

D E F

n 5 n 6 n 7

F IG . 6.3 – La vue récursive de l’arbre de la Fig. 6.2.

6.1. INTRODUCTION 95

Il n’est pas difficile de se convaincre que les deux définitions sont équivalentes. En
effet, l’arbre vide de la Définition 4 correspond à un arbre dont l’ensemble des nœuds
est vide. Un nœud n de la Définition 3 correspond à un nœud n′ dans la Définition 4, tel
que Λ (n′ ) = Λ (n), et tels que les successeurs de n′ sont des arbres A1 , A2 , . . . , Ak dont
les racines r1 , r2 , . . . rk constituent l’ensemble Succ (n).

6.1.2 Vocabulaire
Un certain vocabulaire conventionnel est associé aux arbres. Il permet en général de
simplifier l’exposé des algorithmes sur les arbres. Nous présentons ce vocabulaire dans
les cadre de la définition ensembliste, mais il peut aisément être transposé dans le cadre
de la vue récursive. Toutes ces définitions sont illustrées par des exemples ci-dessous.
Fils : Les nœuds de l’ensemble Succ (n) sont appelés les fils de n.
Père : Le père d’un nœud n est l’unique nœud n′ dont n est le fils. Remarquons que la
racine n’a pas de père.
Feuille : Une feuille est un nœud qui n’a pas de fils.
Nœud interne : Un nœud est un nœud interne si et seulement si il n’est pas une feuille.
Chemin : Un chemin dans un arbre est une séquence n1 n2 · · · nk de nœuds de l’arbre
telle que, pour tout 1 ≤ i < k : ni+1 ∈ Succ(ni ). On dit que ce chemin va de
n1 à nk . La longueur d’un chemin n1 n2 · · · nk est le nombre k de nœuds qui le
composent.
Remarquons que, d’après les définitions d’un arbre, il n’y a qu’un seul chemin
allant de la racine à un nœud n donné.
Accessible : Un nœud n est accessible à partir d’un nœud n′ s’il existe un chemin
allant de n à n′ dans l’arbre.
Descendant : Un nœud n est un descendant d’un nœud n′ si et seulement si n est
accessible à partir de n′ .
Hauteur : La hauteur d’un arbre est la longueur du plus long chemin partant de la
racine de l’arbre. Dans la suite, la hauteur d’un arbre A est notée hauteur(A).
Profondeur : La profondeur d’un nœud n de l’arbre est la longueur du chemin allant
de la racine à n.

Exemple 22 La Fig. 6.4 illustre ce vocabulaire. Elle présente un arbre formé de 12

nœuds, et de hauteur 4, comme en témoigne le chemin en gris : n1 n2 n6 n11 . Un autre
chemin dans l’arbre est n4 n8 n12 (flèches en pointillés). Les fils de n4 sont n7 , n8 et n9
(et n4 est donc le père de ces trois nœuds). Les descendants de n4 sont ses fils, plus n12 .
La profondeur de n5 et n6 par exemple est 3. Celle de n10 est 4, etc. Les nœuds n4 et n1 ,
par exemple, sont des nœuds internes, alors que n11 est une feuille.

6.1.3 Cas particuliers

En pratique, les arbres que l’on utilise, ou qui rendent efficaces les algorithmes pro-
posés, sont des cas particuliers de la définition générale donnée ci-dessus. Dans cette
section, nous détaillons trois restrictions supplémentaires qui seront souvent utilisées
par la suite.
96 CHAPITRE 6. LES ARBRES

P e e s e s

r o f o n d u r d n o u d

n 1

h
e

a u t u r = 4

F i l s e

d n 4

n 2 n 3 n 4

n 5 n 6 n 7 n 8 n 9

n 1 0 n 1 1 n 1 2

D e s c e s e

n d a n t d n 4

C h h
e m i e l e

n ( d o n n a a u t u r )

h
A e c e m i

u t r n

F IG . 6.4 – Quelques illustrations du vocabulaire sur les arbres.

6.1. INTRODUCTION 97

n 1

n 2 n 3

n 4 n 5 n 6

F IG . 6.5 – Un exemple d’arbre binaire équilibré.

Arbres ordonnés Dans les définitions données au début de ce chapitre, nous avons
toujours considéré qu’un nœud possédait un ensemble de fils, ce qui signifie qu’il
n’existe pas d’ordre sur ces fils. En pratique, on fixera souvent un ordre, et on parlera
alors du premier fils, du second fils, du dernier fils, etc.

Arbres n-aires Pour différentes raisons, il sera en général pratique de limiter le

nombre de fils qu’un nœud peut posséder. On parle alors d’arbre n-aire :

Définition 5 Un arbre n-aire est un arbre dont chaque nœud possède au plus n fils.

Le cas le plus utilisé en pratique (et dans la suite de ce cours), et l’arbre binaire, où
chaque nœud possède au plus n = 2 fils. Dans la suite, nous supposerons implicitement
qu’un arbre binaire est ordonné, et nous appellerons respectivement fils gauche et fils
droit le premier et le second fils d’un nœud. Dans les cas des arbres binaires (ordonnés)
nous autoriserons un nœud à posséder un fils droit mais pas de fils gauche. (ce qui
revient à supposer que le fils gauche est vide).

Exemple 23 La Fig. 6.5 présente un exemple d’arbre binaire. En effet, les nœuds n1 et
n2 ont deux fils ; le nœuds n3 a un fils ; et les nœuds n4 , n5 et n6 n’ont pas de fils. n2 est
le fils gauche de n1 et n3 est le fils droit de n1 .

Arbres équilibrés Comme nous le verrons dans la suite, la complexité de plusieurs

algorithmes sur les arbres dépend de la hauteur des arbres auxquels ils sont appliqués.
Dans ce contexte, les arbres dont les nœuds sont repartis entre les différents sous-arbres
de « façon équitable » seront les plus favorables (du point de vue du temps d’exécution).
98 CHAPITRE 6. LES ARBRES

La définition d’arbre équilibré (balanced tree) capture cette notion de « répartition

équitable des nœuds dans les sous-arbres ». Intuitivement, pour qu’un arbre composé
d’un nœud n et de sous-arbres A1 , A2 , . . . , Ak soit équilibré, il faut qu’il respecte deux
critères. Tout d’abord, il faut que chacun de ses sous-arbres soit équilibré. Ensuite, il
faut que les hauteurs des sous-arbres soit à peu près équivalentes. Plus rigoureusement,
nous demanderons que les hauteurs de deux sous-arbres A1 et A2 , quels qu’ils soient,
différent au plus de 1. En effet, nous ne pouvons pas imposer que tous les sous-arbres
aient la même hauteur, car il se pourrait qu’il n’y ait pas assez de nœuds que pour
satisfaire ce critère. Par exemple, un arbre binaire à deux nœuds n1 et n2 , tel que n1
est la racine, et n2 le fils gauche de n1 doit être considéré comme équilibré, même si
le fils gauche de n1 contient plus de nœuds (il en contient 1) que son fils droit (qui
n’en contient pas). Autrement, il ne serait pas possible de construire d’arbre binaire
équilibré avec deux nœuds (ni avec 4, 5, 6,. . . nœuds).
Nous pouvons maintenant donner la définition d’arbre équilibré. Elle est formulée
de façon récursive :

Définition 6 Un arbre A est équilibré si et seulement si :

1. chacun de ses sous-arbre est équilibré et
2. pour toute paire A1 , A2 de sous-arbres de A, |hauteur(A1 ) − hauteur(A2 )| ≤ 1

Exemple 24 L’arbre de la Fig. 6.5 est un arbre binaire équilibré.

Propriété des arbres binaires équilibrés Montrons maintenant que la définition

d’arbre équilibré que nous venons de donner satisfait bien notre critère de « hauteur
minimale ». Pour ce faire, nous allons prouver qu’un arbre équilibré contenant n nœuds
a une hauteur h = O(log(n)), ce qui, intuitivement, signifie que la hauteur est « petite »
par rapport au nombre de nœuds.
Cette preuve requiert quelques pré-requis mathématiques que nous allons mainte-
nant exposer.
Tout d’abord, nous devons définir les nombres de Fibonacci3. Il s’agit d’une sé-
quence infinie de nombres appelés F1 , F2 , F3 , . . ., telle que chaque nombre est égal à la
somme des deux précédents (en commençant avec F1 = 1 et F2 = 1). Voici la définition
(inductive) formelle :

Définition 7 La séquence F1 , F2 , F3 , . . . des nombres de Fibonacci est une séquence de

nombre entiers définie inductivement comme suit :
– F1 = 1 ;
– F2 = 1 ;
– pour tout i ≥ 3 : Fi = Fi−1 + Fi−2.

Cette séquence est donc :

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, . . .
3 D’après le nom du mathématicien italien Leonardo F IBONACCI (c. 1175 - c. 1250). Son Liber Abaci

contribua à introduire les chiffres arabes en occident. C’est dans ce livre qu’on trouve un exercice consistant
à calculer la séquence qui porte son nom. Néanmoins, cette séquence était déjà connue des mathématiciens
indiens, bien avant lui.
6.1. INTRODUCTION 99

Il a été établi que cette suite a plusieurs connexions avec le nombre d’or4 ϕ qui
vaut :
√
1+ 5
ϕ= ≈ 1, 618 . . .
2
Plus précisément, on sait que :

ϕi
∀i ≥ 1 : Fi ≥ √ − 1 (6.1)
5

Tous ces résultats peuvent être trouvés dans des ouvrages classiques de mathéma-
tiques discrètes, comme [5]. Nous pouvons maintenant prouver notre théorème :

Théorème 5 Soit A un arbre binaire équilibré composé de n nœuds, et de hauteur h.

Alors, h = O(log(n)).

Preuve. Nous allons tout d’abord prouver que si A est un arbre de n nœuds et de
hauteur h, alors Fh ≤ n, c’est-à-dire qu’un tel arbre contient nécessairement un nombre
de nœuds qui est supérieur au he nombre de Fibonacci. Nous allons établir ce résultat
par induction sur h.

Cas de base h = 1 ou h = 2. Dans le cas où h = 1, l’arbre possède exactement n = 1

nœud. Nous avons bien F1 = 1. Dans le cas où h = 2, l’arbre possède au moins 2
nœuds. Nous avons donc n ≥ 2. Or 2 ≥ F2 = 1.
Cas inductif h = ℓ > 2. L’hypothèse d’induction est : tout arbre binaire équilibré de
hauteur h′ ≤ ℓ − 1 possède au moins Fh′ nœuds. D’après la définition d’un arbre
équilibré, les deux sous-arbres de la racine sont équilibrés. D’après cette défi-
nition toujours, nous avons deux possibilités. Soit les deux fils sont de hauteur
ℓ − 1. Soit l’un des deux est de hauteur ℓ − 1 et l’autre de hauteur ℓ − 2.
Considérons d’abord le second cas. Le fils qui est de hauteur ℓ − 1 (et est aussi
équilibré) possède, par hypothèse d’induction, au moins n1 ≥ Fℓ−1 nœuds. L’autre
fils, possède, pour la même raison, au moins n2 ≥ Fℓ−2 nœuds. Or, l’arbre de hau-
teur ℓ que nous considérons possède n1 + n2 + 1 nœuds. Donc :

n = n1 + n2 + 1
> n1 + n2
≥ Fℓ−1 + Fℓ−2
= Fℓ
= Fh

Nous avons donc bien Fh ≤ n.

Dans le cas où chaque fils est de hauteur ℓ − 1, il est facile de voir que l’arbre
résultant contiendra au moins autant de nœuds que dans le cas où l’un des fils est
de hauteur ℓ − 1 et l’autre de hauteur ℓ − 2. Nous avons donc aussi Fh ≤ n.

Nous savons donc maintenant que pour tout arbre binaire équilibré possédant n
4
Le nombre d’or est une valeur qui était régulièrement utilisée dans les mesures des statues ou des temples
grecs. Cette proportion était considérée par les Grecs comme particulièrement harmonieuse. Le nom ϕ est
choisi en hommage au sculpteur Feida (Phidias).
100 CHAPITRE 6. LES ARBRES

nœuds et de hauteur h : n ≥ Fh . Or, grâce à l’équation (6.1), nous obtenons :

ϕh
n ≥ Fh ≥ √
5
−1
ϕh
⇒ n≥ −1
√
√ 5
⇒ 5(n+ 1) ≥ ϕ h 
√
⇒ logϕ 5(n + 1) ≥ h
√ 
⇒ logϕ 5 + logϕ (n + 1) ≥ h
√ 
Nous voyons donc que logϕ 5 + logϕ (n + 1) est une borne supérieure de la hau-
√ 
teur h. Nous pouvons donc utiliser la notation O, dans laquelle logϕ 5 disparaît,
 
puisqu’il s’agit d’une constante, et nous obtenons : h = O logϕ (n + 1) , ce qui est en
O(log(n)) 

6.1.4 Implémentation
Nous pouvons maintenant nous tourner vers des considérations plus pratiques, à
savoir l’implémentation de la structure d’arbre. L’implémentation que nous allons pré-
senter ici utilise des pointeurs et est complètement dynamique. Remarquons qu’il est
également possible d’implémenter un arbre dans un tableau, mais nous ne discuterons
pas cette possibilité ici.
De manière générale, un arbre est composé de nœuds qui possèdent chacun un
certain nombre de successeurs, que nous avons appelés fils. La structure de base sera
donc celle qui permet d’implémenter un nœud, et un arbre sera essentiellement un
pointeur vers le nœud racine (ou bien NIL si l’arbre est vide).
Comme, de manière générale, le nombre de fils d’un nœud n’est pas borné, il faut
prévoir, dans la structure qui représente un nœud, une liste contenant les adresses de
tous les fils du nœud. On obtient alors les déclarations suivantes. Tout d’abord, les élé-
ments de la liste de successeurs :
struct ElemArbre
Nœud * info ;
ElemArbre * next ;
Puis, les nœuds à proprement parler :
struct Nœud
Entier info ;
ElemArbre * succ ;

En pratique, la gestion d’une liste pour stocker les adresses des fils d’un nœud est
souvent considérée comme lourde, surtout si on a affaire à un arbre ordonné et que l’on
désire pouvoir accéder immédiatement au ke fils d’un nœud. C’est pourquoi on adopte
souvent l’hypothèse simplificatrice qui consiste à considérer qu’on ne manipule que
des arbres N-aires, pour un N « suffisamment grand ». On peut dès lors stocker les
adresses des fils dans un tableau de successeurs, les cases inutilisées étant initialisées
à NIL :
struct Nœud
Entier info ;
Nœud * succ[N] ;
6.1. INTRODUCTION 101

Finalement, dans le cas des arbres binaires – de loin les arbres les plus courants –
on peut explicitement différencier fils gauche et fils droit dans deux champs du nœud :
struct Nœud
Entier info ;
Nœud * fg ;
Nœud * fd ;

À titre d’exemple, nous présentons maintenant quelques fonctions qui manipulent

la structure d’arbre binaire. Elles sont données à l’Algorithme 30 et à l’Algorithme 31,
et commentées ci-dessous :
ArbreVide Cette fonction construit un arbre vide en mettant le pointeur racine à NIL.
CréerRacine Cette fonction reçoit un arbre (vide) et un entier i, et crée une racine
contenant l’information i.
InsèreGauche et InsèreDroite Ces deux fonctions insèrent respectivement un nou-
veau nœud portant l’information i comme fils gauche (droit) de l’arbre A. On
suppose donc que l’arbre A n’a pas encore de fils gauche (droit).
EstVide Cette fonction renvoie vrai si et seulement si l’arbre A est vide (c’est-à-dire
ssi son pointeur racine est égal à NIL).
EstFeuille Cette fonction renvoie vrai si et seulement si l’arbre passé est une feuille
(c’est-à-dire ssi ses deux fils sont NIL).
FilsGauche et FilsDroit Ces fonctions renvoient respectivement un pointeur vers le
fils gauche (droit) de l’arbre A.
InfoRacine Cette fonction permet de consulter l’information stockée dans la racine de
l’arbre.
Comme on peut le voir, les fonctions d’insertions données ne fonctionnent que dans
le cas où l’on insère une nouvelle feuille. De plus, nous n’avons pas donné de fonction
de suppression. Ces restrictions sont justifiées par le fait qu’il existe plusieurs manières
d’insérer ou de supprimer dans un arbre binaire, qui dépendent de l’information stockée
dans l’arbre, et de la façon dont cette information est stockée. Nous étudierons, dans le
chapitre suivant, un cas particulier, appelé arbre binaire de recherche, pour lequel nous
fournirons les fonctions d’insertion et de suppression adaptées.

6.1.5 Application : les arbres d’expressions

Une application classique des arbres binaires consiste à représenter et manipuler
des expressions arithmétiques. Dans cette section, nous considérerons des expressions
formées :
– de nombres entiers
– d’opérateurs +, −, ∗ ou /
– de parenthèses
Comme les opérateurs considérés sont tous binaires, la structure d’arbre binaire
convient particulièrement bien à leur représentation. En effet, une expression comme
3 + 5, par exemple, consiste à appliquer l’opérateur + sur les valeurs 3 et 5, ce qui peut
se représenter par un arbre dont la racine est étiquetée par +, et les fils gauche et droit
par 3 et 5 respectivement. Si nous considérons maintenant l’expression (3 + 5) ∗ 2, elle
consiste en la multiplication de l’expression 3 + 5 par l’expression 2. Nous pouvons
donc construire une arbre dont la racine est étiquetée par ∗, dont le fils gauche est
102 CHAPITRE 6. LES ARBRES

ArbreVide(Nœud * & A)
début
A := NIL ;
fin

CréerRacine(Nœud * &A, Entier i)

début
A := new Nœud ;
[Link] := i ;
[Link] := NIL ;
[Link] := NIL ;
fin

InsèreGauche(Nœud * A, Entier i)
début
[Link] := new Nœud ;
[Link] := i;
[Link] := NIL;
[Link] := NIL;
fin

InsèreDroite(Nœud * A, Entier i)
début
[Link] := new Nœud ;
[Link] := i;
[Link] := NIL;
[Link] := NIL;
fin
Algorithme 30 : Quelques fonctions de base pour manipuler un arbre binaire stockant
des entiers.
6.1. INTRODUCTION 103

Booléen EstVide(Nœud * A)
début
si A = NIL alors
retourner vrai ;
sinon
retourner faux ;
fin

Booléen EstFeuille(Nœud * A)
début
si EstVide(FilsGauche(A)) et EstVide(FilsDroit(A)) alors
retourner vrai ;
sinon
retourner faux ;
fin

Nœud * FilsGauche(Nœud * A)
début
retourner [Link] ;
fin

Nœud * FilsDroit(Nœud * A)
début
retourner [Link] ;
fin

Entier InfoRacine(Nœud * A)
début
retourner [Link] ;
fin
Algorithme 31 : Quelques fonctions de base pour manipuler un arbre binaire stockant
des entiers (suite)
104 CHAPITRE 6. LES ARBRES

F IG . 6.6 – Un exemple d’arbre d’expression qui représente (3 + 5) ∗ 2.

l’arbre correspondant à 3 + 5, et le fils droit est étiqueté par 2. Ceci est illustré à la
Fig. 6.6. Comme on le voit, la priorité fixée par les parenthèses est implicite dans
l’arbre : afin de pouvoir évaluer le ∗, on devra d’abord évaluer le +, puisque celui-ci
est son fils gauche.
Nous pouvons maintenant définir un arbre d’expression :
Définition 8 Un arbre d’expression est un arbre binaire, tel que :
– Chaque feuille est étiquetée par un nombre entier i, et représente l’expression i ;
– Chaque nœud interne :
– est étiqueté par un opérateur op ;
– possède un fils gauche f g et un fils droit f d ;
– représente l’expression E1 op E2 , où E1 est l’expression représentée par f g,
et E2 est l’expression représentée par f d.
Nous verrons, dans la section suivante, que les algorithmes généraux de parcours
permettent de manipuler de façon très élégante ces arbres d’expression.

6.2 Parcours des arbres binaires

Supposons que nous désirions appliquer un certain traitement à chaque nœud d’un
arbre binaire A (par exemple : afficher l’information contenue dans la racine). Pour
ce faire, il nous faudra certainement : traiter la racine de l’arbre, traiter le sous-arbre
gauche et traiter le sous-arbre droit. S’il est raisonnable de dire que le sous-arbre gauche
doit être traité avant le sous-arbre droit (sinon, pourquoi aurait-on choisi cet ordre ?),
il est plus difficile de décider à quel moment il y a lieu de traiter la racine. Est-ce avant
d’avoir traité les deux fils ? après les avoir traités ? entre les deux traitements ?
Contrairement à une liste, un arbre ne possède pas un seul ordre naturel sur ses
éléments, mais bien plusieurs. Ces différents ordres sont formalisés par la notion de
6.2. PARCOURS DES ARBRES BINAIRES 105

parcours, c’est-à-dire de procédure traversant tous les nœuds de l’arbre et les traitant
chacun une et une seule fois à un moment précis. L’ordre dans lequel les nœuds sont
traités fixe l’ordre sur les nœuds.
Dans cette section, nous étudions quatre parcours. Les trois premiers suivent le
canevas que nous venons d’exposer (traitement de la racine, du fils gauche et du fils
droit), en faisant varier le moment auquel la racine est traitée. Ces parcours sont très
faciles à exprimer de façon récursive, mais nous en étudierons également des versions
itératives, qui utilisent une pile. Nous étudierons ensuite le parcours par niveaux, qui
fait appel à la structure de file du Chapitre 5. Ces parcours sont illustrés à la Fig. 6.7 et
sont donnés aux Algorithmes 32 à 37.

ParcoursPréfixé(Nœud * A)
début
si ¬EstVide(A) alors
Traiter A ;
ParcoursPréfixé(FilsGauche(A)) ;
ParcoursPréfixé(FilsDroit(A)) ;
fin

ParcoursInfixe(Nœud * A)
début
si ¬EstVide(A) alors
ParcoursInfixe(FilsGauche(A)) ;
Traiter A ;
ParcoursInfixe(FilsDroit(A)) ;
fin

ParcoursPostfixé(Nœud * A)
début
si ¬EstVide(A) alors
ParcoursPostfixé(FilsGauche(A)) ;
ParcoursPostfixé(FilsDroit(A)) ;
Traiter A ;
fin
Algorithme 32 : Le trois parcours « de base » exprimés de façon récursive.

6.2.1 Parcours préfixé ou parcours en profondeur

Comme son nom le suggère, le parcours préfixé consiste à traiter la racine de l’arbre
avant de traiter le fils gauche et le fils droit. Ce traitement n’a pas lieu si l’arbre passé
à la fonction est vide. La formulation récursive de ce parcours est donc extrêmement
simple, et est donnée à l’Algorithme 32.
Intéressons-nous maintenant à une implémentation itérative de ce parcours. Pour
ce faire, nous devons d’abord mieux comprendre comment il fonctionne. Considérons
l’exemple de la Fig. 6.5. Sur cet arbre, le parcours préfixé traite les nœuds dans l’ordre
suivant : n1 , n2 , n4 , n5 , n3 , n6 . Initialement, l’appel récursif est effectué sur n1 : n1 est
traité, puis on effectue l’appel récursif sur n2 . À ce moment, l’appel récursif sur n3
n’est pas encore exécuté, et on peut donc considérer qu’il est « en attente ». L’appel
 P

P
c

x
r

t
P
a

fi
n

é
r

i
a

e
p

p
CHAPITRE 6. LES ARBRES

0
1

9
2

8
4

1
3

6
5

8
1
2

3
4

7
5

1
8

0
106

x
r

i
a

a
p

F IG . 6.7 – Les quatre parcours d’arbre classiques. La flèche en pontillé indique l’ordre des appels. Un point à proximité d’un nœud indique à quel
moment le nœud sera effectivement traité lors du parcours.
6.2. PARCOURS DES ARBRES BINAIRES 107

ParcoursPréfixé(Nœud * A)
début
Pile P ;
PileVide(P) ;
Push(P, (A, d)) ;
tant que ¬EstVide(P) faire
(A, action) := Top(P) ;
Pop(P) ;
si ¬EstVide(A) alors
si action = d alors
Push(P, (FilsDroit(A), d)) ;
Push(P, (FilsGauche(A), d)) ;
Push(P, (A, t)) ;
sinon
Traiter A ;

fin
Algorithme 33 : Le parcours préfixé exprimé de façon itérative.

ParcoursInfixe(Nœud * A)
début
Pile P ;
PileVide(P) ;
Push(P, (A, d)) ;
tant que ¬EstVide(P) faire
(A, action) := Top(P) ;
Pop(P) ;
si ¬EstVide(A) alors
si action = d alors
Push(P, (FilsDroit(A), d)) ;
Push(P, (A, t)) ;
Push(P, (FilsGauche(A), d)) ;
sinon
Traiter A ;

fin
Algorithme 34 : Le parcours infixe exprimé de façon itérative.
108 CHAPITRE 6. LES ARBRES

ParcoursPostfixé(Nœud * A)
début
Pile P ;
PileVide(P) ;
Push(P, (A, d)) ;
tant que ¬EstVide(P) faire
(A, action) := Top(P) ;
Pop(P) ;
si ¬EstVide(A) alors
si action = d alors
Push(P, (A, t)) ;
Push(P, (FilsDroit(A), d)) ;
Push(P, (FilsGauche(A), d)) ;
sinon
Traiter A ;

fin
Algorithme 35 : Le parcours infixe exprimé de façon itérative.

récursif sur n2 effectue le traitement de n2 , ainsi qu’un nouvel appel sur n4 , ce qui met
l’appel récursif sur n5 « en attente », mais avant l’appel sur n3 lui aussi « en attente ».
Une façon de résumer cette explication, consiste à exprimer le travail effectué par
l’algorithme sous forme d’une séquence d’actions, qui peuvent être de deux types :

1. soit l’algorithme doit effectuer l’appel récursif sur un nœud, ce que nous appelle-
rons développer le nœud. L’action consistant à développer l’arbre dont la racine
est n sera indiquée dans la séquence par (n, d).

2. soit l’algorithme doit traiter le nœud. L’action consistant à traiter l’arbre dont la
racine est n sera indiquée dans la séquence par (n, t).

Les actions présentes dans la séquence sont exécutées l’une après l’autre par l’algo-
rithme : la première est donc l’action courante et les suivantes sont en attente. Exécu-
ter l’action consiste parfois à remplacer cette action par plusieurs autres actions dans la
séquence : dans le cas du développement de A, on doit insérer les actions qui indiquent
qu’il faut traiter A et développer ses deux fils.
Initialement, la seule action qui doit être effectuée est le développement de n1 ,
ce que nous noterons par la séquence suivante : (n1 , d). Développer n1 consiste tout
d’abord à traiter n1 , puis à développer le fils gauche de n1 , puis à développer le fils
droit de n1 . Nous pouvons donc remplacer cette séquence par (n1 t), (n2 , d), (n3 , d).
L’algorithme doit donc maintenant traiter n1 , comme indiqué par le premier élément de
la séquence. Une fois que cela est fait, nous pouvons supprimer (n1 t) de la séquence
des actions à effectuer, et nous voyons qu’il nous reste à effectuer (n2 , d), (n3 , d). Déve-
lopper n2 revient à traiter n2 , puis développer n4 et n5 . Nous obtenons donc la séquence
(n2 , t), (n4 , d), (n5 , d), (n3 , d). On voit que le développement de n3 reste « en attente »,
et que ce développement aura lieu avant les développements de n5 et n3 . L’algorithme
6.2. PARCOURS DES ARBRES BINAIRES 109

continue ainsi et s’arrête lorsque la séquence est vide :

(n1 , d)
→ (n1 , t), (n2 , d), (n3 , d)
→ (n2 , d), (n3 , d)
→ (n2 , t), (n4 , d), (n5 , d), (n3 , d)
→ (n4 , d), (n5 , d), (n3 , d)
→ (n4 , t), (NIL, d), (NIL, d), (n5 , d), (n3 , d)
→ (n5 , d), (n3 , d)
→ (n5 , t), (NIL, d), (NIL, d), (n3 , d)
→ (n3 , d)
→ (n3 , t), (n6 , d), (NIL, d)
→ (n6 , d), (NIL, d)
→ (n6 , t), (NIL, d), (NIL, d)
→ ε
Il est facile de voir que les manipulations effectuée sur la séquence suivent une
politique de pile, dont le sommet est le début de la séquence. On obtient ainsi un algo-
rithme itératif qui effectue le parcours préfixé d’un arbre A. Cet algorithme maintient, à
tout moment, la séquence décrite ci-dessus dans une pile, avec le début de la séquence
au sommet. Initialement, la pile contient (A, d). Ensuite, tant que la pile n’est pas vide,
l’algorithme effectue les actions suivantes. Il commence par enlever un couple (A, act)
du sommet de la pile, indiquant que l’action act doit être appliquée à l’arbre A :
1. si l’arbre A est vide, rien n’est effectué ;
2. si l’action est t, l’algorithme traite A ;
3. si l’action est d, l’algorithme effectue le Push de : (FilsDroit(A), d), puis de
(FilsGauche(A), d) et enfin de (A, t). Remarquons que l’ordre est « inversé »
par rapport à la spécification naturelle du parcours préfixé. C’est dû au fait qu’on
utilise une pile, et que la prochaine action effectuée sera dès lors la dernière
insérée dans la pile.
Cet Algorithme est donné à l’Algorithme 33.

L’algorithme que nous venons de présenter a l’avantage d’être aisé à expliquer,

et d’offrir une canevas général d’algorithme de parcours, comme nous le verrons ci-
dessous. Néanmoins, il est possible d’en obtenir une version plus simple, grâce aux
deux constatations suivantes :
1. Le développement d’un arbre A consiste à effectuer les Push successifs de ses
sous-arbres droits et gauche (avec l’action d), puis de lui-même, accompagné de
l’action t. Or, comme (A, t) est la dernière information mise sur la pile, c’est
aussi la première qui en sortira. Autrement, chaque fois que l’on met (A, t), on
a la garantie que la prochaine chose à effectuer sera de traiter A. Dans ce cas,
il n’est pas nécessaire de mettre (A, t) sur la pile : il suffit de traiter A avant de
stocker ses deux fils. Comme on ne met désormais plus d’élément de la forme
(A, t), il n’est plus nécessaire de spécifier l’action d pour ceux qu’on y stocke.
2. Nous pouvons à nouveau appliquer le même raisonnement. Après avoir traité
A, nous stockons FilsGauche(A) et FilsDroit(A) sur la pile. Cela signifie que
la prochaine action à effectuer consiste à développer le fils gauche, c’est-à-dire,
stocker FilsGauche(FilsGauche(A)) et FilsDroit(FilsGauche(A)) sur la pile,
etc. On voit qu’il n’est pas nécessaire de faire transiter le fils gauche sur la pile
si c’est pour l’en retirer immédiatement après.
110 CHAPITRE 6. LES ARBRES

Au final, l’algorithme fonctionne comme suit. Recevant un arbre A, il traite sa racine,

Push son sous-arbre droit sur la pile, et « descend » dans son fils gauche grâce à
A := FilsGauche(A). Ce traitement est recommencé jusqu’à ce qu’il n’y ait plus de
fils gauche. À ce moment, on Pop le dernier fils droit en attente de la pile, et on re-
commence le même traitement. On s’arrête dès que la pile est vide. L’Algorithme 36
présente cette solution.

ParcoursPréfixé(Nœud * A)
début
Pile P ;
PileVide(P) ;
répéter
Traiter A ;
Push(P, FilsDroit(A)) ;
A := FilsGauche(A) ;
si EstVide(A) et ¬EstVide(P) alors
A := Top(P) ;
Pop(P) ;
jusqu’à EstVide(P) ;
fin
Algorithme 36 : Une version simplifiée du parcours préfixé.

6.2.2 Parcours infixe

Dans le parcours infixe, on traite la racine après avoir traité le fils gauche, mais
avant d’avoir traité le fils droit. La version récursive est donnée à l’Algorithme 32.
Il est facile de voir – comme indiqué sur la Fig. 6.7 – que l’ordre des appels ré-
cursifs est le même dans le cas du parcours infixe que dans le cas du parcours préfixé.
La seule différence tient dans le fait que le traitement est effectué entre les appels,
et non pas avant eux. Sur base de cette observation, on adapte aisément l’algorithme
itératif donné pour le parcours postfixé, afin d’obtenir un algorithme pour le parcours
infixe. L’adaptation consiste à changer le traitement à effectuer quand on rencontre un
couple du type (A, d) au sommet de la pile : il faut maintenant pusher successivement
(FilsDroit(A), d), (A, t) et (FilsGauche(A), d), afin que la racine soit traitée après le
développement de FilsGauche(A), mais avant le développement de FilsDroit(A).
L’Algorithme 34 présente cette solution.

6.2.3 Parcours postfixé

Le parcours postfixé vient compléter les deux précédents : on y traite la racine
après avoir traité successivement les deux fils. La version récursive est donnée à l’Al-
gorithme 32.
La version itérative est, elle aussi, une modification des parcours préfixé et infixe,
dans laquelle on Push successivement (A, t), (FilsDroit(A), d) et (FilsGauche(A), d).
Elle est donnée à l’Algorithme 35.
6.2. PARCOURS DES ARBRES BINAIRES 111

6.2.4 Le parcours par niveaux ou parcours en largeur

Le parcours par niveaux (parfois appelé parcours en largeur) se différencie des
trois parcours précédents car il n’a pas de formulation récursive immédiate. Par contre,
sa formulation itérative ressemble aux parcours précédents.
Commençons par expliquer intuitivement ce que nous entendons par parcours par
niveaux. Comme on le voit sur la Fig. 6.7, il s’agit de parcourir d’abord tous les nœuds
de profondeur 1, puis ceux de profondeur 2, puis ceux de profondeur 3, etc, et ce de
gauche à droite (suivant l’ordre imposé naturellement par les pointeurs).
Si nous considérons l’arbre binaire de la Fig. 6.5, le parcours par niveaux se déroule
comme suit. On traite d’abord le nœud n1 . Ce faisant, on rencontre ses deux fils n2 et
n3 , que l’on met en attente. Ensuite, on traite n2 . On rencontre alors ses deux fils n4
et n5 qui doivent, eux aussi être mis en attente. Néanmoins, contrairement à ce qui se
passait avec la pile utilisée dans les parcours préfixé, infixe ou postfixé, les fils n4 et n5
devront être traité après qu’on a traité n3 . En effet, il faut avoir traité tous les nœuds
de même profondeur avant de passer au « niveau » suivant. Or, n3 est de profondeur
2, alors que n4 et n5 sont de profondeur 3. Ce sont donc les nœuds qui ont été mis en
attente en premier qui devront être traités d’abord. On a affaire à une politique de type
FIFO, caractéristique des files.
Ceci nous fournit un algorithme pour le parcours en largeur. Celui-ci maintient en
permanence une file d’élément à traiter, qui contient initialement l’arbre A à parcourir.
Tant que la file n’est pas vide, l’algorithme prélève l’arbre qui se trouve en début de file,
traite sa racine, et insère, successivement le sous-arbre gauche et le sous-arbre droit de
A dans la file.

ParcoursLargeur(Nœud * A)
début
File F ;
FileVide(F) ;
Enqueue(F, A) ;
tant que ¬EstVide(F) faire
A := First(F) ;
Dequeue(F) ;
si ¬EstVide(A) alors
Traiter A ;
Enqueue(F, FilsGauche(A)) ;
Enqueue(F, FilsDroit(A)) ;
fin
Algorithme 37 : Le parcours par niveaux d’un arbre binaire.

Exemple 25 La Fig. 6.8 illustre l’exécution du parcours en largeur sur l’arbre de la

Fig. 6.5. À chaque étape, on a représenté la file correspondante.

6.2.5 Applications des parcours

Le calcul de la hauteur d’un arbre binaire Afin d’obtenir une algorithme récur-
sif calculant la hauteur d’un arbre, il faut d’abord en donner une définition récursive.
Naturellement, la hauteur de l’arbre vide est 0. Si nous voyons un arbre comme une
CHAPITRE 6. LES ARBRES

1
n

3
n

6
n

1
n

3
n

6
n

6
n

6
112

F IG . 6.8 – Une illustration du parcours en largeur. Les nœuds grisés ont été traités. Le contenu de la file à chaque étape est représenté sous l’arbre.
6.2. PARCOURS DES ARBRES BINAIRES 113

racine flanquée de deux sous-arbres, il est clair que la hauteur de l’arbre dépendra des
hauteurs des sous-arbre, auxquelles il faudra ajouter 1 pour la racine. Comme la hau-
teur d’un arbre est définie par rapport à son plus long chemin, il convient de garder la
hauteur du plus haut des deux sous-arbre :
Définition 9 La hauteur hauteur(A) d’un arbre A est :
– 0 si l’arbre est vide
– 1 + max{hauteur((FilsGauche(A)), hauteur((FilsDroit(A))}, sinon
On voit qu’il faut donc calculer la hauteur des deux fils avant de pouvoir calculer la
hauteur de l’arbre. Il s’agit d’un parcours postfixé, comme le montre l’Algorithme 38.

Entier Hauteur(Nœud * A)
début
si EstVide(A) alors
retourner 0 ;
sinon
Entier hg, hd ;
hg := Hauteur(FilsGauche(A)) ;
hd := Hauteur(FilsDroit(A)) ;
retourner 1 + max{hg, hd} ;
fin
Algorithme 38 : Un algorithme récursif pour calculer la hauteur d’un arbre binaire.

L’évaluation d’une expression Considérons à nouveau un arbre d’expression, et

écrivons un algorithme qui calcule la valeur de l’expression représentée par l’arbre.
Si nous regardons l’exemple 6.6, nous constatons qu’il ne nous est pas possible d’éva-
luer immédiatement la valeur de la multiplication représentée dans la racine. En effet, il
faut d’abord connaître les valeurs des expressions stockées dans les fils gauche et droit.
De même, pour évaluer la valeur de l’addition stockée dans le fils gauche de la racine,
il faut d’abord connaître les valeurs des deux feuilles 3 et 5. Par contre, la valeur d’une
feuille est directement stockée dans son étiquette.
On obtient ainsi un algorithme récursif pour évaluer un arbre d’expression :
1. Si l’arbre est vide, la valeur est 0 ;
2. Si l’arbre est une feuille n, la valeur est Λ (n) ;
3. Sinon, la racine n de l’arbre possède deux fils f g et f d, et la valeur de l’expres-
sion est f g Λ (n) f d (où Λ (n) est l’opérateur stocké dans la racine).
Il s’agit à nouveau d’un parcours postfixé, puisqu’il faut évaluer les fils avant de pou-
voir évaluer la racine. Cet algorithme est donné en détail à l’Algorithme 39

L’affichage d’une expression Regardons maintenant comment nous pouvons affi-

cher (en notation conventionnelle) une expression stockée dans un arbre (en insérant
des parenthèses afin de garantir que la priorité exprimée par l’arbre est respectée).
À nouveau, nous allons analyser le problème sous l’angle récursif. Il est clair que
l’affichage de l’arbre vide, ne produit rien, et que l’affichage d’une feuille revient à
afficher son étiquette. Si, par contre, nous avons affaire à un arbre dont la racine possède
des fils, il convient d’afficher d’abord l’expression correspondant au fils gauche, puis
l’opérateur stocké dans la racine, et enfin l’expression que représente le fils droit. Il
114 CHAPITRE 6. LES ARBRES

Entier ÉvaluationExpression(Nœud * A)
début
si EstVide(A) alors
retourner 0 ;
sinon si EstFeuille(A) alors
retourner InfoRacine(A) ;
sinon
Entier vg, vd ;
vg := ÉvaluationExpression(FilsGauche(A)) ;
vd := ÉvaluationExpression(FilsDroit(A)) ;
si InfoRacine(A) = + alors
retourner vg + vd ;
sinon si InfoRacine(A) = − alors
retourner vg − vd ;
sinon si InfoRacine(A) = ∗ alors
retourner vg ∗ vd ;
sinon
retourner vg/vd ;
fin
Algorithme 39 : Un algorithme récursif pour évaluer un arbre d’expression.

faut prendre garde à entourer cet affichage de parenthèses ouvrantes et fermantes, afin
de s’assurer que la priorité est respectée. En effet, sans cela, l’algorithme afficherait
3 + 5 ∗ 2 quand il est exécuté sur l’arbre de la Fig. 6.6, ce qui n’est pas correct. Avec
les parenthèses, on affiche ((5 + 3) ∗ 2).
Nous obtenons donc une variation du parcours infixe, puisque le contenu de la
racine est affiché, entre les deux appels récursifs qui traitent les fils gauche et droit.
l’Algorithme 40 présente cette solution.

Entier AffichageExpression(Nœud * A)
début
si ¬EstVide(A) alors
si EstFeuille(A) alors
Afficher Info(A) ;
sinon
Afficher ’(’ ;
AffichageExpression(FilsGauche(A)) ;
Afficher Info(A) ;
AffichageExpression(FilsGauche(D)) ;
Afficher ’)’ ;
fin
Algorithme 40 : Un algorithme récursif pour afficher une expression stockée dans
un arbre
Chapitre 7

Algorithmes de recherche

7.1 Introduction
L’objet premier de l’informatique est, comme sont nom le suggère, le traitement de
l’information. Les ordinateurs sont de plus en plus utilisés pour stocker et manipuler
des quantités gigantesques de données, auquel on souhaite un accès rapide et fiable.
Dans ce contexte, les algorithmes de recherche, qui ont pour but de rechercher une
information précise dans une masse d’informations donnée, sont d’une importance ca-
pitale. Il doit être possible de stocker les informations en mémoire de telle manière que
ces algorithmes de recherche soient les plus efficaces possible. Naturellement, l’effica-
cité de ces algorithme dépendra de la manière dont les informations en question sont
structurées.
Dans ce cours, nous avons étudié plusieurs structures de données : les vecteurs, les
listes, les files, les piles et les arbres. Il est clair que les files et les piles ne conviennent
pas à la recherche d’informations, car elles ne permettent d’accéder qu’à un seul des
éléments qu’elles contiennent à la fois (celui au sommet, dans le cas des piles, et celui
au début, dans le cas des files).
Par contre, les vecteurs, les listes et les arbres semblent convenir au stockage et à la
recherche d’information. Il est donc naturel de se demander quels sont les algorithmes
utilisables sur ces structures et quel sont leurs efficacités respectives.

Afin de pouvoir effectuer une comparaison correcte entre ces différentes structures,
nous allons considérer le problème suivant. Nous allons supposer que nous avons à
notre disposition une certaine séquence de valeurs entières1 V1 ,V2 , . . .Vn . En pratique,
ces informations peuvent être lues sur input, sur un fichier, etc. , Nous allons regarder
comment stocker ces informations dans chacune des trois structures considérées de
manière à ce que les algorithmes de recherche soient ensuite aussi efficace que possible.
Dans tous les cas, nous allons évaluer le coût de la construction de la structure, ainsi
que le coût de chaque recherche.

1 Cette hypothèse nous permettra de supposer qu’il existe un ordre sur les valeurs (c’est-à-dire que celles-

ci peuvent être triées). En pratique, on peut en général trouver un tel ordre même si les valeurs ne sont pas
des entiers. Il existe également bien des cas où une clef primaire entière est attachée à chaque donnée. Cette
hypothèse est donc tout à fait réaliste.

115
116 CHAPITRE 7. ALGORITHMES DE RECHERCHE

7.2 Données stockées dans des vecteurs

Comme les valeurs considérées sont entières, nous pouvons choisir de les stocker
de manière triée ou dans l’ordre où elles nous sont fournies. Cela influera naturellement
sur le temps nécessaire pour construire la structure ou pour la consulter.

7.2.1 Recherche linéaire simple

Le cas le plus simple est celui où les k valeurs sont stockées dans un tableau T
de telle manière que, pour tout 1 ≤ i ≤ n, T [i] = Vi . Dans ce cas, la construction du
vecteur est simple dans la mesure où il suffit d’insérer chaque valeur dans la prochaine
case libre. Cette construction est donc en O(n). La recherche s’effectue, elle aussi en
O(n), puisqu’il faut parcourir tout le vecteur au pire cas.

ConstruireVec(Entier T [n])
début
Entier i := 1 ;
tant que i ≤ n faire
T [i] := Vi ;
i := i + 1 ;
fin

Booléen RechercheLinéaireVec(Entier T [n], Entier k)

début
Entier i := 1 ;
tant que i ≤ n et T [i] 6= k faire
i := i + 1 ;
si T [i] = n + 1 alors
retourner faux ;
sinon
retourner vrai ;
fin
Algorithme 41 : La construction et la recherche dans un vecteur non trié

La correction de l’algorithme de recherche peut être établie grâce à l’invariant sui-

vant :
i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] 6= k
qui indique que toutes les cases considérées (jusqu’à la case i − 1) ne contiennent pas
la valeur k recherchée. Autrement dit, la boucle de la fonction RechercheLinéaireVec
parcourt le vecteur case par case en éliminant celles qui ne contiennent pas k. À la fin
de la boucle, on donc la garantie :
1. Soit que toutes les cases ont été passées en revue, et donc que la valeur k n’est
pas présente dans le vecteur ;
2. Soit qu’on a trouvé la valeur en s’arrêtant « au milieu » du vecteur.
Plus formellement, à la fin de la boucle, on sait que :

i ≥ n + 1 ∨ T[i] = k
7.2. DONNÉES STOCKÉES DANS DES VECTEURS 117

En associant ce résultat à l’invariant on obtient :

i ≥ n ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] 6= k
∨
T [i] = k ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] 6= k
ce qui est équivalent à :
i = n + 1 ∧ ∀1 ≤ j < n + 1 : T [i] 6= k
∨
T [i] = k ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] 6= k
La première partie de cette disjonction indique que la valeur k n’est pas dans le
vecteur (et que i = n + 1). La seconde partie indique qu’on a trouvé une occurence de
k dans la case T [i]. Autrement dit, si en fin de boucle i = n + 1, on sait que la valeur
n’est pas présente. Sinon, on a trouvé la valeur k à la position i.

7.2.2 Recherche linéaire dans un vecteur trié

Si les valeurs sont stockées dans le tableau de façon triée, il est possible d’amé-
liorer un peu la recherche, comme nous l’avons vu dans le cas des listes triées à la
Section 4.2.3 du Chapitre 4. En effet, dès qu’on rencontre dans le tableau une valeur
T [ j] telle que T [ j] > k (où k est l’information recherchée), on peut arrêter la recherche,
car on sait que toutes les case T [i] avec i > j contiennent elles aussi des informations
> k. On obtient alors l’Algorithme 42 pour la recherche. Malheureusement celui-ci
reste en O(n) au pire cas.
Il nous reste à voir comment obtenir un vecteur trié, étant donné que nous n’avons
pas la garantie que les informations V1 ,V2 , . . . ,Vn sont données dans cet ordre. Pour
ce faire, on peut utiliser la fonction ConstruireVec de l’Algorithme 41, puis trier le
vecteur. Il existe de bons tris en O(n log(n)) (comme HeapSort, voir, par exemple [3]).
La construction du vecteur trié est donc en O(n + n log(n)) = O(n log(n)).

Booléen RechercheTriéeVec(Entier T [n], Entier k)

début
Entier i := 1 ;
tant que i ≤ n et T [i] < k faire
i := i + 1 ;
si i ≤ n et T [i] = k alors
retourner vrai ;
sinon
retourner faux ;
fin
Algorithme 42 : La construction et la recherche dans un vecteur non trié

Dans ce cas, l’invariant Inv de la boucle de recherche est :

i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] < k
Cette boucle élimine donc toutes les valeurs < k (et non pas 6= k). La négation de la
condition B de la boucle est, cette fois-ci :
i ≥ n + 1 ∨ T[i] ≥ k
118 CHAPITRE 7. ALGORITHMES DE RECHERCHE

Pour des raisons de facilité, nous réécrivons cette assertion en :

i ≥ n + 1 ∨ T[i] = k ∨ T [i] > k

En fin de boucle, nous avons donc (¬B ∧ Inv) :

i ≥ n + 1 ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] < k

∨
T [i] = k ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] < k
∨
T [i] > k ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] < k

Ce qui est équivalent à :

i = n + 1 ∧ ∀1 ≤ j < n + 1 : T [i] < k

∨
T [i] = k ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] < k
∨
T [i] > k ∧ i ≤ n + 1 ∧ ∀1 ≤ j < i : T [i] < k

Autrement dit, trois possibilités s’offrent à nous :

1. Soit i = n + 1, et toutes les valeurs du tableau sont < k. Clairement, dans ce cas,
la valeur n’est pas trouvée.
2. Soit i s’est arrêté sur une case T [i] qui contient k.
3. Soit i s’est arrêté sur une case T [i] qui contient > k, et toutes les cases avant
i sont < k. Ceci implique que k n’est pas dans le vecteur. En effet, le fait que
T [i] contienne une valeur > k et le fait que le vecteur soit trié impliquent que
toutes les cases T [i + 1] . . . T [n] contiennent des valeurs > k. Donc, toutes les
cases T [1] . . . T [i − 1] contiennent des valeurs < k ; T [i] contient une valeur > k ;
et toutes les cases T [i + 1] . . .T [n] contiennent des valeurs > k.
Il convient de donc de s’assurer que i ≤ n et que T [i] = k en fin de boucle pour retourner
vrai.

7.2.3 Recherche dichotomique dans un vecteur trié

Néanmoins, dans le cas où le vecteur est trié, on peut utiliser un algorithme de
recherche plus efficace que la recherche linéaire de l’Algorithme 42. Il s’agit de la
recherche dichotomique.
Celle-ci fonctionne de façon similaire à ce que l’on fait si on recherche un nom dans
un annuaire téléphonique2. La technique habituelle consiste à ouvrir l’annuaire au mi-
lieu. Si la page contient, par chance, le nom de notre correspondant, nous avons trouvé
l’information désirée. Dans le cas contraire, il faut regarder l’initiale des noms sur la
page à laquelle on a ouvert l’annuaire, et comparer cette initiale à celle de notre corres-
pondant pour savoir dans quelle direction il faut continuer la recherche. Par exemple, si
nous avons ouvert l’annuaire à la page des L et que le nom de notre correspondant com-
mence par M, nous devrons chercher dans la partie de l’annuaire qui se trouve après
la page des L, ce qui nous permet d’éliminer immédiatement la moitié de l’annuaire
constituée des pages avant L. Nous pouvons alors recommencer le même traitement
2 Illo tempore, les annuaires en papier étaient encore répandus. . .
7.2. DONNÉES STOCKÉES DANS DES VECTEURS 119

dans la partie restante : nous ouvrons l’annuaire au milieu de sa seconde moitié (soit à
ses trois quarts), et nous comparons l’initiale de la page, et ainsi de suite.
Cette méthode est très rapide en pratique car, à chaque étape, nous séparons la partie
inexplorée de l’annuaire en deux parties (approximativement) égales, et nous éliminons
l’une des deux. Après la première étape, nous avons éliminé la moitié de l’annuaire,
après la seconde, les trois quarts, après la troisième, les 7/8, etc.

On peut transposer cette idée sous la forme d’un algorithme récursif qui fonctionne
sur un vecteur trié. Celui-ci reçoit un vecteur T , une valeur k et deux bornes bi et
bs. Il doit retourner vrai ssi la valeur k est présente dans une des cases T [i] telle que
bi ≤ i ≤ bs. Pour ce faire, il commence par repérer le « milieu » de la partie à traiter.
Cette partie est longueur bs − bi + 1, et son milieu est donc à la case3
 
bs − bi + 1
m = bi +
2
L’algorithme compare alors k à T [m]. Trois cas peuvent se présenter :
1. Si T [m] = k, l’information est trouvée, et l’algorithme retourne vrai.
2. Si T [m] < k, k ne peut se trouver qu’à droite de T [m]. On doit donc effectuer une
recherche dans la portion comprise entre les case m + 1 et bs du vecteur.
3. Si T [m] > k, k ne peut se trouver qu’à gauche de T [m]. On doit donc effectuer
une recherche dans la portion comprise entre les case bi et m − 1 du vecteur.
Les deux derniers cas sont traités à l’aide d’un appel récursif, et l’algorithme doit donc
renvoyer la valeur obtenue à l’aide de l’appel récursif. Si l’information à chercher n’est
pas dans le vecteur, la récursivité s’arrête dès que la portion du vecteur à traiter est
vide, c’est-à-dire ssi bs < bi. Dans ce cas, on retourne faux.
Cet algorithme est donné à l’Algorithme 43 et illustré par l’exemple ci-dessous.
Exemple 26 Considérons le tableau donné à la Fig. 7.1, et cherchons y la valeur k =
53 de manière dichotomique. Le tableau comporte 14 valeurs. À la première itération,
nous avons donc bi = 1, bs = 14 et m = bi+ ⌊(bs− bi+ 1)/2⌋ = 1 + (14 − 1 + 1/2) = 8.
Comme la valeur recherchée 53 est > T [8] = 45, on obtient bi = m + 1 = 9 et bs
reste inchangée. On continue ainsi jusqu’à avoir trouvé 53, ce qui arrive au bout de 4
itérations.

Complexité de la recherche dichotomique Évaluons maintenant la complexité de

cette procédure, afin de nous assurer qu’elle est effectivement plus efficace que la re-
cherche linéaire.
Il est clair que les traitements effectués à l’intérieur de chacun des appels récursif
sont en O(1). La complexité de la recherche dichotomique ne dépendra donc que de
la profondeur des appels récursifs. Le pire cas est obtenu quand la valeur k n’est pas
présente dans le vecteur, ce que l’on détecte en effectuant en appel récursif sur une
portion vide du vecteur. Il nous faut donc trouver une borne supérieure sur le nombre
d’appels nécessaires pour avoir la garantie que le vecteur soit vide. Pour ce faire, nous
allons d’abord prouver le résultat suivant, qui lie la profondeur des appels récursifs et
la taille de la portion du vecteur à explorer. Nous prendrons comme convention que
l’appel principal est de profondeur 0, que le premier appel récursif est de profondeur
1, etc.
3 Le plancher peut être supprimé à condition d’effectuer une division entière.
120 CHAPITRE 7. ALGORITHMES DE RECHERCHE

k =
5 3

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4

1 3 8 1 2 2 4 2 8 3 2 4 5 5 3 6 2 7 9 8 5 9 5 9 8

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4

1 3 8 1 2 2 4 2 8 3 2 4 5 5 3 6 2 7 9 8 5 9 5 9 8

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4

1 3 8 1 2 2 4 2 8 3 2 4 5 5 3 6 2 7 9 8 5 9 5 9 8

1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4

1 3 8 1 2 2 4 2 8 3 2 4 5 5 3 6 2 7 9 8 5 9 5 9 8

F IG . 7.1 – Une illustration de la recherche dichotomique. Les cases grisées délimitent

l’intervalle de recherche

RechercheDichotomique(Entier T [n], Entier bi, Entier bs, Entier k)

début
si bs < bi alors
retourner faux ;
sinon  
Entier m := bi + bs−bi+1
2 ;
si T [m] = k alors
retourner vrai ;
sinon si T [m] < k alors
retourner RechercheDichotomique(T , m + 1, bs, k) ;
sinon
retourner RechercheDichotomique(T , bi, m − 1, k) ;
fin
Algorithme 43 : La recherche dichotomique dans un vecteur trié.
7.2. DONNÉES STOCKÉES DANS DES VECTEURS 121

Proposition 1 Dans la recherche dichotomique, lors du pe appel récursif, nous avons :

n
bs − bi + 1 ≤
2p
où n est la taille de la portion du vecteur passé à la fonction lors du premier appel.

Preuve. La preuve est par induction sur la profondeur p des appels :

Cas de base p = 0 Dans ce cas, nous avons bs − bi + 1 = n, et donc :
n
n = bs − bi + 1 ≤ =n
20
est bien vérifié.
Cas inductif p = ℓ L’hypothèse d’induction suppose qu’on a passé un vecteur de taille
au plus n/2ℓ−1 lors du ℓ − 1e appel. Autrement dit, lors du ℓ − 1e appel, nous
n
avons : bs − bi + 1 ≤ 2ℓ−1 .
Lors du ℓe appel, on calcule m = bi + ⌊ bs−bi+1
2 ⌋. Dans le cas où T [m] < k, on
effectue un appel récursif sur une portion du vecteur de taille bs − (m + 1) + 1 =
bs − m. En remplaçant m par sa valeur on obtient une taille de :
 
bs − bi + 1
bs − bi −
2

Établissons maintenant que cette taille est bien inférieure à n/2ℓ :

bs − bi − ⌊ bs−bi+1
2 ⌋
≤ (bs − bi + 1) − ⌊ bs−bi+1
2 ⌋
bs−bi+1
≤ (bs − bi + 1) − 2
= bs−bi+1
2
≤ 12 · 2ℓ−1
n
Par HI
n
= 2ℓ

La taille du vecteur passé au ℓe appel est donc bien de 2nℓ au maximum.

Dans le cas où T [m] > k, il est facile de voir que la taille du vecteur passé sera la
même.

Nous possédons donc maintenant une borne supérieur sur la taille du vecteur passé
à chaque appel récursif, et nous voyons que le nombre d’éléments à considérer à chaque
étape décroît exponentiellement. Ceci nous permet de conclure que :

Proposition 2 Appelée sur un tableau de n, la recherche dichotomique effectue au plus

log2 (n) + 1 appels récursifs.

Preuve. Comme la récursivité s’arrête lorsque la taille du vecteur passé à la fonction

est nulle, nous avons la garantie que la récursivité s’arrêtera dès que la valeur n/(2k )
devient < 1 (car la taille est nécessairement un entier). Cela arrive dès 2k > n. Le
nombre maximum d’appels récursifs est donc la plus petite valeur k telle que 2k > n. Il
s’agit donc de la plus petite valeur k telle que k > log2 (n). Le nombre d’appels récursifs
est donc au plus de log2 (n) + 1. 
Ceci nous permet dès lors de conclure que :
122 CHAPITRE 7. ALGORITHMES DE RECHERCHE

Théorème 6 La complexité de la recherche dichotomique est O(log(n)), où n = bs −

bi + 1 est la taille du tableau T .

Preuve. Par la Proposition 2, on sait qu’au maximum log2 (n) + 1 appels récursifs
sont effectués. En comptant l’appel « principal » (en d’autres termes, l’appel 0), il y a
au maximum log2 (n) + 2 exécutions de la fonction. Les traitements propres à chaque
appel sont en O(1). La complexité totale est donc en O(log2 (n) + 2) = O(log(n)). 

Exemple 27 Sur l’exemple de la Fig. 7.1, la valeur recherchée 53 est présente dans le
tableau. Quand la valeur est effectivement présente dans le tableau, le cas illustré est le
plus défavorable, puisqu’on est obligé de réduire l’intervalle de recherche à une seule
case. De manière générale, le pire cas se produit quand la valeur n’est pas présente : si
on avait recherché 61, par exemple, une itération supplémentaire aurait été nécessaire
pour rendre l’intervalle de recherche vide.
Sur cet exemple, le nombre d’appels confirme bien la théorie. En effet, log2 (14) +
2 ≈ 5, 81, et le nombre d’appels effectué est bien toujours ≤ 5, quelque soit la valeur k
recherchée.

7.2.4 Tables de hachage

Dans les deux méthodes que nous avons présentées dans les sections précédentes,
les valeurs V1 , . . .Vn de l’ensemble à représenter étaient stockées dans différentes cases
d’un tableau de taille n. Par conséquent, chaque case du tableau contenait une valeur, et
il n’y avait donc pas de case inutilisée (pas de « trou » entre les cases). Cette méthode
est clairement la plus économique en mémoire.
Néanmoins, si nous disposons de suffisamment de mémoire, une méthode beaucoup
plus simple consiste à :
1. Calculer la valeur Max, qui est le maximum de V1 , . . . ,Vn (autrement dit, Max
est la valeur maximale que nous sommes susceptible de devoir stocker dans la
structure).
2. Déclarer un tableau H de booléens de taille Max, initialisé de telle manière que
toutes ses cases contiennent faux.
3. Mettre à vrai toutes les cases H[Vi ] (pour tout 1 ≤ i ≤ n).
On obtient donc un tableau H tel que H[ j] est à vrai si et seulement si la valeur j est
présente dans {V1 , . . . ,Vn }. La construction d’une telle table est en O(Max), mais la
consultation se fait très facilement en O(1), puisqu’il suffit de tester si V [k] vaut vrai
pour savoir si k est présente.
Cette méthode semble donc très intéressante sur le plan du coût de la recherche.
Malheureusement elle est souvent inutilisable en pratique, en raison de la taille de
la table H. En effet, supposons que les valeurs à stocker sont des numéros de cartes
d’identité belges. Ces numéros comportent 12 chiffres, ce qui peut être considéré comme
petit. La valeur maximale est donc de l’ordre de 1012. En supposant qu’on utilise 1 bit
par case de la table, on a besoin de plus 1011 octets pour stocker la table, soit plus de
2Go, et ce, quelque soit le nombre d’informations stockée dans la table. . .

On voit donc que pour pouvoir utiliser cette idée en pratique, et continuer à ex-
ploiter le fait qu’on peut accéder en O(1) à une case d’un tableau, il faut diminuer la
taille de la table. Supposons que nous admettions une table H de taille N ≪ Max. Cette
supposition a deux implications :
7.2. DONNÉES STOCKÉES DANS DES VECTEURS 123

1. On ne peut plus faire correspondre chaque valeur Vi à la case H[Vi ]. Il faudra

donc trouver une fonction f : {V1 , . . . ,Vn } 7→ {1, . . . , N} qui, pour chaque valeur
Vi indique la case de H à utiliser. Une telle fonction sera appelée fonction de
hachage.
2. Comme il y a moins de cases que de valeurs possibles, il sera parfois nécessaire
d’associer plusieurs valeurs à une même case. Autrement dit, comme Max ≫ N,
il existera certainement des paires de valeurs différentes Vi ,V j telles que f (Vi ) =
f (V j ). Ce phénomène est appelé collision. Il faudra donc trouver une manière de
gérer ces collisions.

Choix d’une fonction de hachage

Le choix d’une fonction de hachage est un problème qui a été énormément étudié,
et la littérature sur le sujet est abondante. Nous allons nous contenter de donner ici
quelques idées de base.
Commençons par donner quelques propriétés qu’une bonne fonction de hachage
devrait satisfaire :
1. La fonction doit minimiser les collisions. En effet, la fonction qui envoie toute
valeur sur 1 est une fonction de hachage. Néanmoins, elle ne permet pas une
bonne répartition des valeurs à stocker dans la table, puisqu’elles seront toutes
associées à la première case.
2. La fonction doit être facile à calculer. Dans le cas contraire, on perdrait tout le
bénéfice de l’accès direct des tableaux. De toute manière, la complexité de cette
fonction doit être indépendante de la taille des données (donc en O(1)).
Par ailleurs, remarquons que toute fonction (au sens mathématique du terme) est
déterministe dans le sens où, si f (Vi ) 6= f (V j ), alors Vi 6= V j . La clef de hachage est
donc suffisante pour faire la différence entre deux valeurs. Nous avons déjà vu que
l’implication inverse n’est pas vrai : deux valeurs Vi et V j peuvent donner lieu à la
même valeur f (Vi ) = f (V j ).
En pratique, le choix d’une fonction de hachage dépend grandement du type de
données à traiter. Dans le cadre de ce cours, nous avons fait l’hypothèse que les données
sont entières. Néanmoins, il peut s’agir d’autre type de données, comme des chaînes
de caractères.
Voici deux exemples simples qui illustrent la notion de fonction de hachage.

Une fonction de hachage pour les entiers positifs Si les valeurs considérées sont
des entiers ≥ 0, la fonction :

f (x) = (x mod N) + 1

garantit une valeur comprise entre 1 et N.

Une fonction de hachage pour les chaînes de caractères Écartons nous quelque
peu des hypothèses du chapitre et considérons que les valeurs à traiter sont des chaînes
de caractères de la forme S = α1 α2 · · · αn , où les αi sont les caractères de la chaîne.
Afin de définir une fonction de hachage pour ces données, il est nécessaire de
convertir les chaînes en nombres entiers. Il faut donc associer à chaque caractère un
nombre. Nous supposerons donc que nous disposons d’une fonction v qui reçoit un
124 CHAPITRE 7. ALGORITHMES DE RECHERCHE

caractère et qui renvoie le nombre associé à ce paramètre (en pratique, on peut simple-
ment prendre le code ASCII, par exemple). Nous supposerons que la fonction renvoie
toujours des valeurs dans l’intervalle [0, . . . B − 1], où B sera choisi suffisamment grand
en fonction du nombre de caractères (par exemple 256 pour le code ASCII)
Dans ce cas, une fonction de hachage pour les chaînes des caractères peut être :
! !
n
f (α1 α2 · · · αn ) = ∑ v(αn−i+1 )Bi−1 mod N + 1
i=1

ce qui revient à voir la chaîne α1 α2 · · · αn comme le nombre v(α1 )v(α2 ) · · · v(αn ) en

base B. Ce nombre est ensuite converti en base 10 (grâce à la somme), puis pris modulo
N (on ajoute 1 puisqu’on a supposé que les cases sont numérotées à partir de 1).
Exemple 28 Considérons la chaîne Algo. Les codes ASCII des différents caractères
sont les suivants :
A 65
l 108
g 103
o 111
On voit donc la chaîne comme le nombre en base 256 :
65 108 103 111 = 56 × 2563 + 108 × 2562 + 103 × 2561 + 111 × 2560
soit [Link] en base 10. Si nous supposons une taille N = 101, nous obtenons
la position dans la table :
f (Algo) = ([Link] mod 101) + 1 = 50
Cette définition pose malheureusement des problèmes pratiques. Le premier est
illustré par l’exemple ci-dessus : pour la chaîne Algo qui ne fait que 4 lettres, la valeur
∑ni=1 v(αn−i+1 )Bi−1 est déjà très importante. Si on ajoute un s à cette chaîne, on ob-
tient la valeur [Link] > 100 × 232. Autant dire qu’on dépasse rapidement les
valeurs maximales qu’on peut stocker dans une variable entière en C ou C++. . .
En pratique, on calcule la fonction de hachage de façon itérative, comme illustré
à l’Algorithme 44. On peut montrer (ce que nous ne ferons pas ici) que cette fonction
calcule bien la définition donnée ci-dessus. Cette implémentation a l’avantage de ne
jamais stocker dans r des valeurs plus grandes que N, car on prend le modulo à chaque
tour de boucle.

Le second problème potentiel provient de la relation qu’il peut exister entre la va-
leur de N et la valeur de B. Supposons par exemple que N = B. Dans cas, nous avons :
!
n
∑ v(αn−i+1 )Bi−1 mod N = v(αn )
i=1

En effet, si un nombre est exprimé dans une base B, le reste de la division de ce nombre
par B est simplement son dernier chiffre. Une telle fonction de hachage n’est sûrement
pas satisfaisante, puisqu’elle ne prend en compte que le dernier caractère de la chaîne.
Remarquons que des phénomènes similaires se produisent si N est une puissance de
B : si N = Bℓ , ce sont les ℓ derniers caractères de la chaîne seulement qui sont pris en
compte. Il faut donc veiller à ce que N et B soient mutuellement premiers entre eux
(ce qui signifie qu’ils n’ont pas de diviseur commun, à part 1). En pratique, choisir un
nombre premier pour la valeur de N est une bonne idée (comme 101 dans l’Exemple 28)
7.2. DONNÉES STOCKÉES DANS DES VECTEURS 125

Entier f (Chaine α1 α2 · · · αn )
début
Entier i = 1 ;
Entier r = 0 ;
tant que i ≤ n faire
r := ((r × B) + αi ) mod N ;
retourner r + 1 ;
fin
Algorithme 44 : Le calcul efficace de la fonction de hachage sur les chaînes de
caractères.

6 2 8
1
5

4 3 1
7

6
7 7

F IG . 7.2 – Une illustration du hachage avec chaînage.

Gestion des collisions

Comme nous l’avons vu, il arrive que deux valeurs à stocker soient envoyées dans
le même élément de la table. Nous devons donc trouver une technique pour retenir,
pour chaque élément de la table, quelles sont les valeurs qui y ont été insérées. Ceci
peut se faire aisément en stockant dans chaque élément H[i] de la table la tête d’une
liste constituée d’éléments dans lesquels on stocke les valeurs insérées à la position i.
Ces éléments seront donc de la forme :
struct Elem
Entier info ;
Elem * next ;

Cette politique de gestion des collision est appelée le hachage avec chaînage par
référence aux listes chaînées qui y sont exploitées. Elle est illustrée à la Fig. 7.2.
Finalement, la table de hachage sera donc un vecteur Elem * H[N] de pointeurs
initialisé à NIL (initialement toutes les listes sont vides). On obtient les fonctions don-
126 CHAPITRE 7. ALGORITHMES DE RECHERCHE

nées à l’Algorithme 45 pour manipuler les tables de hachage dans le cas où les données
sont des entiers. Ces fonctions sont aisément transposables dans les autres cas, comme
les chaînes de caractères. Elles sont détaillées ci-dessous :
InitHachage Cette fonction initialise la table de hachage en créant des listes vides
dans toutes ses cases. Cette fonction est en O(N).
InsertionHachage Cette fonction repère la position p dans la table correspondant à la
clef j à l’aide de la fonction de hachage f , et insère cette clef en tête de la liste
dont la tête est en H[p]. Elle est donc en O(1) (en supposant que la fonction f
est elle-même en O(1)).
RechercheHachage Cette fonction booléenne indique si la clef k est présente dans la
table H. Pour ce faire, elle doit simplement rechercher la valeur j dans la liste
dont la tête est en H[ f ( j)]. La complexité de cette fonction dépend donc de la
longueur de la liste à parcourir. Au pire cas, et si la fonction de hachage est
de mauvaise qualité, toutes les informations sont stockées dans la même case.
Cette fonction est donc en O(n). Néanmoins, si la fonction de hachage est « bien
choisie », cette fonction est, en moyenne, en O(1). Nous renvoyons le lecteur à
des ouvrages plus approfondis [4] pour les détails.

InitHachage(Elem * H[N])
début
Entier i := 1 ;
tant que i ≤ N faire
ListeVide(H[i]) ;
fin

InsertionHachage(Elem * H[N], Entier j)

début
Entier p := f ( j) ;
InsèreTête(H[p], j) ;
fin

Booléen RechercheHachage(Elem * H[N], Entier k)

début
Entier p := f (k) ;
Elem * q := Recherche(H[p], k) ;
si q 6= NIL alors
retourner vrai ;
sinon
retourner faux ;
fin
Algorithme 45 : La construction et le recherche dans une table de hachage avec
chaînage.

En pratique, les tables de hachage sont extrêmement efficaces, car la valeur (moyenne)
O(1) pour la recherche est tout à fait réaliste. Naturellement, une table de hachage reste
un tableau, et est donc de taille fixée. Au fur et à mesure que la table se remplit, les
performances se dégradent, car les listes qui résolvent les collisions s’allongent. Par
ailleurs, redimensionner une table de hachage est une opération coûteuse. Nous ver-
rons plus loin que les arbres binaires de recherche balancés offrent l’avantage d’opé-
7.3. DONNÉES STOCKÉES DANS DES LISTES 127

rations assez efficaces (en O(log(n)), où n est le nombre de valeurs stockées), dans une
structure dynamique.

7.3 Données stockées dans des listes

Les fonctions de recherche dans une liste, qu’elle soit triée ou non, ont déjà été
couvertes dans le chapitre sur les listes. Nous renvoyons donc le lecteur au Chapitre 4,
et plus particulièrement aux Sections 4.2.2 et 4.2.3.
Contentons nous de résumer ici les complexités obtenues :
1. Dans le cas des listes non triées : l’insertion peut se faire en tête et est donc en
O(1) par valeur insérée. La recherche est en O(n) au pire cas.
2. Dans le cas des listes triées : l’insertion triée est en O(n) par élément inséré.
On peut donc insérer les n valeurs en O(n2 ) au pire cas, à l’aide de la fonc-
tion InsertionTriée. On peut également réaliser n insertions en tête et effectuer
ensuite un tri en O(n log(n)), ce qui fait O(n log n) au total. La recherche est
également en O(n) (bien qu’elle soit en pratique un peu plus efficace que si la
liste n’est pas triée).

7.4 Données stockées dans des arbres

Considérons maintenant le cas où les données à traiter sont stockées dans un arbre.
Nous allons considérer deux cas : le cas le plus général, où les données étiquettent
simplement les nœuds de l’arbre, sans autre hypothèse ; et le cas où on a réparti les
données de manière à obtenir un arbre binaire de recherche.

7.4.1 Parcours simple

Supposons que nous ayons à notre disposition un arbre A dont l’ensemble des
nœuds est N, et tel que {Λ (n) | n ∈ N} = {V1,V2 , . . . ,Vn } (c’est-à-dire que les étiquettes
des nœuds sont exactement les données V1 ,V2 , . . .Vn ).
Dans ce cas, nous n’avons pas d’autre choix que de parcourir tout l’arbre pour
rechercher une certaine information k. Ce cas est donc similaire à celui rencontré quand
on manipulait un tableau ou une liste non trié, et la structure d’arbre n’apporte rien ici.
Au pire cas, la complexité est donc en O(n).
Le choix du parcours peut quelque peu améliorer l’efficacité en pratique. En effet,
il vaut mieux arrêter la recherche dès que l’information est trouvée, ce qui signifie
que l’information stockée dans un nœuds doit être comparée à k dès que ce nœud est
rencontré. On a donc intérêt à opter pour le parcours préfixé. L’Algorithme 46 présente
cette solution.
Nous n’abordons pas en détail la construction d’un tel arbre. Les fonctions d’inser-
tion présentées à la Section 6.1.4 peuvent être exploitées à cette fin. Remarquons que
la forme de l’arbre importe peu, puisqu’on le parcourt toujours entièrement au pire cas
(dans le cas où l’information n’est pas présente). On peut donc très bien opter pour une
construction où les nouveaux nœuds sont toujours insérés à gauche du nœud le plus
profond. Dans ce cas, on obtient en fait une liste (comme l’arbre illustré à la Fig. 7.8).
128 CHAPITRE 7. ALGORITHMES DE RECHERCHE

RechercheArbre(Nœud * A)
début
si EstVide(A) alors
retourner faux ;
sinon
si [Link] = k alors
retourner vrai;
sinon si RechercheArbre(FilsGauche(A)) alors
retourner vrai ;
sinon si RechercheArbre(FilsDroit(A)) alors
retourner vrai ;
fin
Algorithme 46 : La recherche d’une information k dans un arbre.

7.4.2 Arbres binaires de recherche

Il est possible d’obtenir des algorithmes de recherche plus efficaces dans les arbres
à condition d’ordonner les nœuds de façon intelligente. Si nous examinons à nouveau
l’Algorithme 46, nous constatons qu’un certain gain pourrait être obtenu s’il n’était
pas nécessaire d’effectuer un appel récursif sur les deux fils, mais seulement sur un des
deux (dans le cas où l’info n’est pas dans la racine). Dans ce cas, on pourrait espérer
éliminer à chaque étape la moitié de l’arbre encore inexplorée, en ne passant en revue
que l’autre moitié (en faisant l’hypothèse que les nœuds sont répartis de façon équitable
entre le sous-arbre gauche et le sous-arbre droit).
Cela peut se faire à condition qu’il existe une relation entre, d’une part, l’informa-
tion stockée dans la racine d’un arbre, et, d’autres parts, les informations stockées dans
les nœuds de ses fils. Pour ce faire, nous allons réutiliser l’idée principale de la re-
cherche dichotomique. Pour rappel, dans cet algorithme, nous sélectionnions à chaque
étape une case T [m] du vecteur (trié), et trois possibilités s’offraient à nous :
1. Soit T [m] = k ;
2. Soit T [m] > k, et la recherche devait continuer à gauche de T [m] ;
3. Soit T [m] < k, et la recherche devait continuer à droite de T [m].
L’analogie entre les arbres binaires et la recherche dichotomique devrait maintenant
être claire : le premier cas correspond au cas où l’information stockée dans la racine
est l’information recherchée ; le second correspond au cas où l’on ne continue la re-
cherche que dans le fils gauche ; et le troisième correspond au cas où l’on ne continue
la recherche que dans le fils droit.
Naturellement, pour que cet algorithme soit correct, il est nécessaire que la re-
cherche dans un seul des deux fils nous garantisse de trouver l’information si elle est
dans l’arbre. Dans le cas de la recherche dichotomique, on pouvait certainement élimi-
ner une partie du vecteur car toutes les cases à gauche de T [m] contenaient des infor-
mations < T [m], et toutes celles à droites des informations > T [m]. Cette condition doit
donc être transposée dans le cadre des arbres binaires. On obtient alors la définition d’
arbre binaire de recherche (binary search trees en anglais – abrégé en BST) :
Définition 10 L’arbre vide est un arbre binaire de recherche.
Si A est un arbre dont la racine est r, et dont les sous-arbres gauche et droit sont
respectivement Ag et Ad alors A est un arbre binaire de recherche ssi les quatre condi-
tions suivantes sont remplies :
7.4. DONNÉES STOCKÉES DANS DES ARBRES 129

1 5

2 2
7

2 2
5 1 1 7 5

6 2 3 3 2
5

F IG . 7.3 – Un exemple d’arbre binaire de recherche (équilibré). En pointillés, le chemin

parcouru pour accéder à l’information 23.

1. Tout nœud n de Ag est tel que Λ (n) ≤ Λ (r).

2. Tout nœud n de Ad est tel que Λ (n) > Λ (r).
3. Ag est un arbre binaire de recherche.
4. Ad est un arbre binaire de recherche.

Dans la suite, nous abrégerons souvent arbre binaire de recherche en ABR.

Exemple 29 Un exemple d’ABR est donné à la Fig. 7.3.

Opérations sur les arbres binaires de recherche

Maintenant que nous avons défini les ABR, nous pouvons passer en revue certaines
opérations sur cette structure.

Informations dans l’ordre croissant Regardons d’abord comment nous pouvons

extraire toutes les informations de l’arbre dans l’ordre croissant. En effet, puisque
l’arbre a été construit selon cet ordre, il doit être possible, étant donné un arbre, de
reconstituer une séquence V1′ ,V2′ , . . . ,Vn′ , qui est une permutation croissante (autrement
dit « un tri ») de V1 ,V2 , . . .Vn . Étant donnée la définition d’un ABR, il est clair que tous
les nœuds qui apparaissent dans le sous arbre gauche d’un arbre donné apparaîtront
dans la séquence avant la racine de l’arbre, qui apparaîtra elle-même avant les nœuds
du sous-arbre droit. Ceci nous suggère donc un algorithme récursif pour reconstituer la
séquence triée :
1. Si l’arbre est vide, renvoyer la séquence vide.
130 CHAPITRE 7. ALGORITHMES DE RECHERCHE

F IG . 7.4 – L’ordre sur les nœuds induit par un arbre binaire de recherche (il s’agit de
l’ordre du parcours infixe).

2. Sinon, construire la séquence qui correspond au sous-arbre gauche, ajouter à sa

fin l’étiquette de la racine de l’arbre, puis la séquence qui correspond au sous-
arbre droit.
On voit donc que l’ordre adéquat est en fait l’ordre infixe (voir les Algorithmes 32
et 34). Ceci est illustré par la Fig. 7.4.

Recherche La recherche dans un ABR suit directement ce que nous avons présenté
ci-dessus. Étant donné un arbre A, il y a quatre possibilités :
1. Soit l’arbre A est vide, et l’information n’est pas présente.
2. Soit l’arbre A n’est pas vide, et l’information est dans sa racine.
3. Soit l’arbre A n’est pas vide et l’information recherchée est plus petite que sa
racine. Il faut alors effectuer la recherche dans le sous-arbre gauche.
4. Soit l’arbre A n’est pas vide et l’information recherchée est plus grande que sa
racine. Il faut alors effectuer la recherche dans le sous-arbre droit.
Cet algorithme est correct par la définition d’un ABR. Nous avons également la garantie
qu’il termine car on effectue toujours un appel récursif sur un arbre de hauteur plus
petite. Il est donné à l’Algorithme 47.
7.4. DONNÉES STOCKÉES DANS DES ARBRES 131

Booléen RechercheABR(Nœud * A), Entier k

début
si EstVide(A) alors
retourner faux ;
sinon si InfoRacine(A) = k alors
retourner vrai ;
sinon si InfoRacine(A) > k alors
retourner RechercheABR(FilsGauche(A), k) ;
sinon
retourner RechercheABR(FilsDroit(A), k) ;
fin
Algorithme 47 : La recherche dans un ABR : version récursive.

Il est facile de voir que cet algorithme ne réalise pas un parcours de tout l’arbre,
mais construit un chemin dans l’arbre, partant de la racine, et arrivant dans le nœud
recherché (s’il existe). Le chemin en question est la séquence des nœuds sur lesquels
les appels récursifs successifs sont effectués. La Fig. 7.3 illustre cela : on appelle la
fonction sur la racine, ce qui donne lieu à un appel récursif sur 22, puis sur 25, et enfin
23, auquel cas on retourne vrai.
Cette constatation nous permet d’obtenir aisément un algorithme itératif qui réalise
la recherche (voir Algorithme 48). Celui-ci maintient, à tout moment, un pointeur p
vers un nœud de l’arbre. Initialement p pointe vers la racine. p est ensuite déplacé
vers le nœud qui est à la racine de l’arbre sur lequel l’appel récursif aurait été effectué
dans la version récursive de l’algorithme. On déplace donc p sur le fils gauche si la
racine contient une information plus grande que l’information k recherchée, et sur le
fils droit dans le cas contraire. Ce déplacement s’arrête dès que p pointe vers un nœud
qui contient l’information recherchée, ou si p est NIL.

Booléen RechercheABR(Nœud * A), Entier k

début
Nœud * p := A ;
tant que ¬EstVide(p) et InfoRacine(p) 6= k faire
si [Link] > k alors
p := FilsGauche(p) ;
sinon
p := FilsDroit(p) ;
si EstVide(p) alors
retourner faux ;
sinon
retourner vrai ;
fin
Algorithme 48 : La recherche dans un ABR : version itérative.

Insertion L’insertion dans un arbre binaire de recherche suit le même principe que la
recherche. En effet, le cas de base correspondant à l’arbre vide est simple à traiter : on
crée tout simplement un nouveau nœud qui fera office de racine et qui reçoit l’informa-
tion à insérer. Les cas récursifs suivent également la logique de l’ABR que nous avons
déjà rencontrée dans la recherche : si l’information à insérer est ≥ à la racine, on doit
132 CHAPITRE 7. ALGORITHMES DE RECHERCHE

1 5

2 2
7

5 1 2 1 2 5
7

5 6 1 1 2 3 3 2

C h e m i n s u i v i p o u r l ' i n s e r t i o n d e 1 1

C h e m i n s u i v i p o u r l ' i n s e r t i o n d e 7

F IG . 7.5 – Deux insertions dans un ABR. Les chemins suivis sont indiqués en poin-
tillés. Les comparaisons réalisées sont indiquées le long des chemins, à côté des nœuds
concernés.

réaliser l’insertion dans le sous-arbre gauche. Sinon, on doit réaliser l’insertion dans le
sous-arbre droit.
Il faut simplement prendre garde à ce que l’insertion dans un sous-arbre peut modi-
fier la racine de ce sous-arbre, au cas où celui-ci est vide. On peut gérer cela aisément
en passant la racine par référence. Cette procédure est donnée à l’Algorithme 49 et
illustré à la Fig. 7.5.
En observant attentivement la Fig. 7.5, on constate deux choses :
1. Comme la recherche, cet algorithme construit un chemin dans l’arbre, partant de
la racine, et arrivant dans une feuille.
2. L’insertion consiste toujours à ajouter un nouveau fils à un nœud. L’insertion
consiste donc toujours à créer une nouvelle feuille.
Ces observations nous amènent tout naturellement à une version itérative de l’algo-
rithme d’insertion. Celui-ci procède de façon similaire à l’Algorithme 48 : il maintient
un pointeur qui doit repérer le nœud auquel on viendra ajouter un fils contenant l’infor-
mation à insérer. Pour ce faire, il parcourt un chemin dans l’arbre partant de la racine.
7.4. DONNÉES STOCKÉES DANS DES ARBRES 133

InsertionABR(Nœud * & A, Entier k)

début
si EstVide(A) alors
CréerRacine(A, k) ;
sinon si InfoRacine(A) ≥ k alors
InsertionABR([Link], k) ;
sinon
InsertionABR([Link], k) ;
fin
Algorithme 49 : L’insertion dans un ABR : version récursive.

Dans le cas où le nœud n vers lequel p pointe a une étiquette ≥ à l’information à insérer,
on a deux possibilités :
1. Soit n possède un fils gauche, et il faut alors faire pointer p vers ce fils gauche.
2. Soit n ne possède pas de fils gauche, et on peut alors créer un fils gauche conte-
nant l’information à insérer.
Dans le cas où n a une étiquette < à l’information à insérer, on procède de façon
similaire dans le fils droit.

InsertionABR(Nœud * & A, Entier k)

début
Nœud * p ;
Booléen fin ;
si EstVide(A) alors
CréerRacine(A, k) ;
sinon
p := A ;
fin := faux ;
tant que ¬fin faire
si InfoRacine(p) ≥ k alors
si EstVide(FilsGauche(p)) alors
InsèreGauche(p, k) ;
fin := vrai ;
sinon
p := FilsGauche(p) ;
sinon
si EstVide(FilsDroit(p)) alors
InsèreDroite(p, k) ;
fin := vrai ;
sinon
p := FilsDroit(p) ;

fin
Algorithme 50 : L’insertion dans un ABR : version itérative.

Suppression L’opération de suppression d’une information dans un ABR est un peu

particulière, et mérite qu’on s’y attarde quelques instants. Étant donné une information
134 CHAPITRE 7. ALGORITHMES DE RECHERCHE

k à supprimer de l’arbre, il faut d’abord repérer le nœud qui contient cette information4.
Cela peut se faire de manière similaire à la recherche, en parcourant un chemin dans
l’ABR. Ensuite, il faut effacer le nœud n ainsi trouvé, ce qui sépare l’arbre en trois
parties : le sous-arbre gauche de n ; son sous-arbre droit et le reste de l’arbre. Il faut
donc « recoller les morceaux », et c’est là toute la difficulté de la suppression.
Commençons par les cas les plus simples :
1. Si n est une feuille, n n’a pas de sous-arbres gauche ou droit, et la suppres-
sion est donc terminé dès que n a été effacé. Cette situation est représentée à la
Fig. 7.6 (a).
2. Si n ne possède qu’un seul sous-arbre, il suffit de remplacer n par la racine de ce
sous-arbre. Cette situation est représentée à la Fig. 7.6 (b).
Le cas le plus délicat est celui où n possède deux sous-arbres non-vides. Quel nœud
va-t-on choisir pour remplacer n ? La réponse nous est donnée en considérant l’ordre
naturellement induit par l’arbre sur ses nœuds, qui correspond à l’ordre infixe (cfr.
Fig. 7.4) : il faut sélectionner un nœud qui permet de conserver cet ordre. Ceci cor-
respond sélectionner un nœud n’ qu’on va prélever soit dans le sous-arbre gauche, soit
dans le sous-arbre droit de n ; et dont l’étiquette est à la fois plus grande que ou égale
à toutes les étiquettes des nœuds du sous-arbre gauche, et plus petite que toutes les
étiquettes des nœuds du sous-arbre droit. Deux nœuds répondent à cette propriété : soit
le nœud qui précède directement n dans l’ordre infixe (c’est-à-dire le plus grand nœud
du sous-arbre gauche de n) ; soit le nœud qui suit directement n dans l’ordre infixe
(c’est-à-dire le plus petit nœud du sous-arbre droit de n). Le choix est indifférent.

Exemple 30 Sur l’arbre de la Fig. 7.6 (c), l’ordre infixe est : H, D, K, I, B, E, J, A,

F, C, G. Si on supprime B, on aimerait donc obtenir un arbre représentant l’ordre H,
D, K, I, E, J, A, F, C, G. On peut considérer que cela revient à supprimer B et à le
remplacer soit par I (le maximum du sous-arbre gauche de B), soit par E (le minimum
du sous-arbre droit de B)

L’avantage de cette procédure est que le maximum du sous-arbre gauche (le mi-
nimum du sous-arbre droit) d’un nœud est aisé à obtenir : il s’agit du nœud le plus à
droite (à gauche) dans son sous-arbre gauche (droit).
Dans l’agorithme de suppression que nous allons présenter, nous choisirons de rem-
placer un nœud par le plus grand nœud de son sous-arbre gauche. Nous allons donc
commencer par donner la fonction ExtraireMaxABR, qui réalise un parcours d’un
arbre pour repérer le nœud qui porte l’information maximale dans cet arbre. Il détache
alors ce nœud de l’arbre et renvoie un pointeur vers ce nœud. Afin de pouvoir détacher
un nœud, il est nécessaire d’avoir un pointeur vers le père de ce nœud (s’il existe).
C’est le but du pointeur q, utilisé dans la boucle de parcours. Ce pointeur respecte à
tout moment la propriété suivante (il s’agit d’un invariant de la boucle) :

q = NIL ⇔ p est la racine de l’arbre

∧
q 6= NIL ⇔ q est le père de p

À la fin de la boucle qui recherche le maximum de l’arbre, on a donc la garantie

que :
4 Si plusieurs nœuds contiennent cette même information k, il conviendra d’effectuer plusieurs fois l’opé-

ration de suppression.
 7.4. DONNÉES STOCKÉES DANS DES ARBRES
A

A
A

F
B

E
D

E
(

)
a
A

A
B

C
D

G
H

J
(

)
c
K

135
F IG . 7.6 – Une illustration des trois cas de suppression dans un ABR. Le nœud à supprimer est indiqué en grisé.
136 CHAPITRE 7. ALGORITHMES DE RECHERCHE

2 2
1 5 1 5

2 2
7 7 1 7

2 0
1 6

2 2
5 1 1 7 5 1

2 0
1 1 1 6 1 1

F IG . 7.7 – Le maximum dans un arbre binaire de recherche (indiqué en gris) et l’arbre

obtenu après le détachement de ce nœud (le fils gauche du nœud a remonté).

1. p pointe vers le maximum de l’arbre.

2. Si p n’est pas la racine, q pointe vers le père de p. Autrement, q vaut NIL.
3. Si q n’est pas NIL, p est le fils droit de q.
4. p n’a pas de fils droit (sinon, il ne serait pas le maximum), mais a peut-être un
fils gauche.
Comme p peut encore avoir un fils gauche, il suffit maintenant de remplacer, dans
l’arbre, p par son fils gauche. Cela se fait en modifiant, soit le fils droit de q (si celui-ci
n’est pas NIL), soit la racine. Cette procédure est illustré à la Fig. 7.7.

Nœud * ExtraireMaxABR(Nœud * & A)

début
Nœud * p := A, q := NIL ;
tant que FilsDroit(p) 6= NIL faire
q := p ;
p := FilsDroit(p) ;
si q = NIL alors
A := FilsGauche(p) ;
sinon
[Link] := FilsGauche(p) ;
[Link] := NIL ;
[Link] := NIL ;
retourner p ;
fin
Algorithme 51 : Un algorithme pour extraire le maximum d’un arbre. Il reçoit un
arbre non-vide et renvoie un pointeur vers le nœud contenant l’information maximale.
Ce nœud est détaché de l’arbre.

Nous pouvons maintenant donner l’algorithme de suppresion (cfr. Algorithme 52).

Il consiste en les étapes suivantes :
7.4. DONNÉES STOCKÉES DANS DES ARBRES 137

1. Rechercher le nœud à supprimer, en amenant un pointeur p sur ce nœud. Comme

dans ExtraireMaxABR, nous avons utilisé un second pointeur q pour repérer le
père de p. Nous retenons également, à l’aide de la variable sens si p est le fils
gauche ou le fils droit de q. À la fin de la boucle de recherche, le pointeur q pointe
vers le père de p si p n’est pas la racine. Dans le cas contraire q vaut NIL.
2. Identifier le nœud r qui doit remplacer p :
(a) Si p est une feuille, il n’y a pas de remplacement à effectuer. On peut donc
mettre r à NIL.
(b) Si p n’a qu’un fils (gauche ou droit), c’est ce fils qui doit le remplacer (sans
qu’il soit nécessaire de modifier le fils)
(c) Sinon, on fait appel à ExtraireMaxABR pour rechercher le maximum du
sous-arbre gauche de p. On obtient alors un pointeur vers ce nœud r, qui a
été détaché de l’arbre. Comme r doit remplacer p, on met les fils gauche et
droit de p dans les fils gauche et droit de r.
3. Effectuer le remplacement : cela consiste à modifier soit le pointeur gauche de q
(si p est le fils gauche de q, c’est-à-dire si sens=g) soit le pointeur droit de q (si
sens=d), pour le faire pointer vers r
4. Supprimer p à l’aide de delete.
Comme on le voit, l’opération de suppression est bien plus complexe que les autres
opérations (insertion et recherche). C’est pourquoi, en pratique, on préfère parfois la
solution qui consiste à marquer un nœud comme étant supprimé (tout en le laissant
dans l’arbre). Il faut alors adapter l’opération de recherche, afin qu’elle soit poursuivie
quand on trouve un nœud portant l’information désirée, mais marqué comme supprimé.
Cette solution permet d’éviter le remplacement du nœud à supprimer par un autre, et
est satisfaisante en pratique si peu de suppressions ont lieu.

Complexité des opérations

Insertion Comme nous l’avons vu au moment où nous avons étudié l’algorithme d’in-
sertion, celui-ci parcourt un et un seul chemin dans l’arbre, qui part de la racine
et arrive dans une feuille. Le traitement de chacun des nœuds de ce chemin est
effectué en temps constant. La complexité de l’insertion est donc en Ode la lon-
gueur du plus long chemin de l’arbre, c’est-à-dire de sa hauteur.
Recherche La recherche d’un nœud fonctionne sur le même principe que l’insertion :
construction d’un chemin dans l’arbre partant de la racine et arrivant au pire cas
dans une feuille. Les traitements appliqués à chaque nœud sont également en
temps constant et la complexité est donc elle aussi en Ode la hauteur de l’arbre.
Suppression La suppression commence par rechercher le nœud à supprimer, ce qui se
fait en parcourant un chemin π1 dans l’arbre. Puis, on effectue le remplacement
de ce nœud, et sa suppression. Le remplacement et la suppression à proprement
parler sont en temps constant. Par contre, la recherche du nœud r qui sert à ef-
fectuer le remplacement donne, elle aussi, lieu au parcours d’un chemin π2 dans
l’arbre (au pire cas, c’est-à-dire quand on fait appel à ExtraireMaxABR). Il
n’est pas difficile de voir que la somme des longueurs de π1 et π2 est toujours
≤ à la hauteur de l’arbre, car π1 mène de la racine au nœud p à supprimer, et
π2 commence dans le nœud à supprimer et se termine dans r. Au total, π1 π2 est
donc un chemin allant de la racine à r et est donc ≤ à la hauteur de l’arbre. On
138 CHAPITRE 7. ALGORITHMES DE RECHERCHE

SuppressionABR(Nœud * A, Entier k)
début
Nœud * p := A, q := NIL, r ;
Caractère sens ;
/* Re her he du n÷ud à supprimer p et de son père q. */
tant que ¬EstVide(p) et InfoRacine(p) 6= k faire
q := p ;
si InfoRacine(p) > k alors
p := FilsGauche(p) ;
sens := g ;
sinon
p := FilsDroit(p) ;
sens := d ;

si EstVide(p) alors
Afficher « Information non trouvée » ;
sinon
/* Re her he du n÷ud r qui va rempla er p. */
si EstFeuille(p) alors r := NIL ;
sinon si EstVide(FilsGauche(p)) alors r := FilsDroit(p) ;
sinon si EstVide(FilsDroit(p)) alors r := FilsGauche(p) ;
sinon
r := ExtraireMaxABR(FilsGauche(p)) ;
[Link] := FilsGauche(p) ;
[Link] := FilsDroit(p) ;

/* Rempla ement de p par r. */

si ¬EstVide(q) alors /* p n'est pas la ra ine. */
si sens = g alors
[Link] := r ;
sinon
[Link] := r ;
sinon
A := r ;

delete p ;
fin
Algorithme 52 : L’algorithme de suppression dans un arbre binaire de recherche.
7.4. DONNÉES STOCKÉES DANS DES ARBRES 139

F IG . 7.8 – Un exemple d’arbre dont la hauteur est en O du nombre de nœuds. Il s’agit

en fait d’une liste.

conclut que la suppression s’effectue, comme la recherche et l’insertion en Ode

la hauteur de l’arbre.

Théorème 7 Étant donné un arbre binaire de recherche A, les opérations d’insertion,

de recherche et de suppression sont en O (hauteur(A)).

Malheureusement, dans le pire des cas, la hauteur d’un arbre binaire de recherche
est en O du nombre de nœuds qu’il contient, comme montré sur le Fig. 7.8. Dans ce
cas, l’arbre construit est en fait une liste. Un tel arbre s’obtient par exemple en insérant
successivement des valeurs en ordre décroissant.
Théorème 8 Étant donné un arbre binaire de recherche A contenant n nœuds, les opé-
rations d’insertion, de recherche et de suppression sont en O(n).

Néanmoins, nous avons vu au Chapitre 6 que la hauteur d’un arbre binaire balancé,
est en O(log(n)), où n est le nombre de nœuds dans l’arbre. Donc :
Théorème 9 Étant donné un arbre binaire de recherche balancé A contenant n nœuds,
les opérations d’insertion, de recherche et de suppression sont en O (log(n)).
Il nous reste à comprendre comment nous pouvons garantir qu’un ABR soit ba-
lancé. En effet, il n’est pas difficile de voir que l’insertion peut rendre non-balancé un
140 CHAPITRE 7. ALGORITHMES DE RECHERCHE

arbre qui était balancé avant l’insertion. Considérez par exemple l’arbre à deux nœuds
ayant 3 comme information dans sa racine et 2 dans son fils gauche. Cet arbre est
balancé. L’ajout du nœud portant l’information 1 à gauche de 2 fait qu’il n’est plus
balancé, car le fils gauche de 3 est maintenant de hauteur 2, alors que son fils droit est
de hauteur 0. Le même phénomène peut apparaître avec la suppression.
Nous n’expliquerons pas en détail dans ce cours comment résoudre ces problèmes
(ils seront abordés dans un cours ultérieur). Nous pouvons néanmoins indiquer que :
1. Il existe des structures d’arbres binaires balancés, dans lesquels l’insertion et
la suppression maintiennent le caractère balancé de l’arbre, tout en gardant une
complexité en O(log(n)). On peut citer par exemple les AVL, les arbres rouge-
noir, etc. [4].
2. La solution qui consisterait à reconstruire complètement l’arbre de façon ba-
lancée après chaque insertion n’est pas satisfaisante, car elle serait en O(n), ce
qui fait perdre l’avantage du O(log(n)). Par contre, si on commence par insé-
rer toutes les valeurs, puis qu’on se contente de consulter très fréquemment la
structure, il peut être intéressant de réaliser toutes les insertions de façon non-
balancée dans un premier temps, puis de reconstruire l’arbre de façon balancée
(une seule fois : le coût est alors négligeable).
3. Si les données V1 ,V2 , . . .Vn sont fournies dans un ordre aléatoire, alors la proba-
bilité que l’arbre résultant des n insertions (sans balancement) soit balancé est
très grande.
Nous renvoyons le lecteur vers les ouvrages de référence [4, 9], et vers des cours
ultérieurs pour un traitement approfondi de ces structures essentielles en informatique.
Chapitre 8

Conclusion : aux limites de

l’algorithmique

Dans ce cours, nous avons tenté de poser les bases de l’algorithmique, et ce, de
façon scientifique et rigoureuse. Ce cours reste donc une introduction à l’algorithmique,
et de nombreux sujets restent à couvrir, comme :
– Les nombreuses variantes d’arbres balancés ;
– Les graphes ;
– Les méthodes d’analyse plus fines que la complexité au pire cas (comme la com-
plexité amortie) ;
– Les algorithmes de compression, ou de chiffrage des données ;
– ...
Tous ces domaines trouvent de nombreuses applications en pratique, et font encore
l’objet d’une recherche active. . .

Dans ce cours, nous nous sommes posés de nombreux problèmes. Par exemple, le
Chapitre 7 a été entièrement consacré à présenter différentes solutions au problème :
« comment stocker des données de façon à pouvoir les consulter de manière efficace ? »
À chaque fois, nous avons apporté des solutions qui ont pris la forme de structures de
données et surtout d’algorithmes qui manipulent ces structures. Nous avons également
utilisé des outils rigoureux (les invariants, les preuves par induction, la complexité,. . .)
pour raisonner sur ces algorithmes, prouver leur correction, et évaluer leur efficacité.
Bref, pour chacun des problèmes étudiés dans ces pages, nous avons pu apporter une
réponse satisfaisante, tant sur le plan théorique que pratique.
Le potentiel de l’algorithmique semble donc illimité.

En guise de conclusion, il semble légitime de se demander si cette démarche cou-

ronnée de succès pourra être appliquée dans tous les cas. Autrement dit, peut-on affir-
mer que tous les problèmes sont solubles algorithmiquement ?
Malheureusement la réponse est non : il existe des problèmes qu’aucun algorithme
ne peut résoudre. Attention, cela ne signifie pas qu’on ne connaît pas (encore) l’algo-
rithme pour résoudre tel ou tel problème. Cela signifie qu’il est possible de démontrer à
l’aide d’un raisonnement rigoureux qu’il n’existe aucun algorithme pour résoudre cer-
tains problèmes ! Autrement dit, certains problèmes sont tout simplement trop difficiles
pour un ordinateur.

141
142 CHAPITRE 8. CONCLUSION : AUX LIMITES DE L’ALGORITHMIQUE

Ce résultat très profond trouve sa source dans des problèmes de mathématiques po-
sés bien avant l’invention de l’ordinateur. En 1900, le mathématicien allemand David
H ILBERT1 pose ses célèbres 23 problèmes au congrès international de mathématiques
(Paris). Le 10e problème demande de trouver une méthode systématique (c’est-à-dire
un algorithme) déterminant si une équation diophantine2 possède une solution. La ré-
ponse à ce problème sera apporté par le mathématicien anglais Alan Mathison T U -
RING 3 et le mathématicien américain Alonzo C HURCH 4 en 1936 : il n’existe pas de tel
algorithme.

Néanmoins, il ne s’agit pas du seul problème pour lequel il n’existe pas d’algo-
rithme. À titre d’illustration, nous allons maintenant donner les idées principales de la
preuve qui montre qu’il n’existe aucune algorithme pour résoudre le problème du test
d’arrêt. Celui-ci est défini comme suit :
Étant donné un programme P et une input I pour P, P s’arrête-t-il quand
on l’exécute sur l’input I ?

Exemple 31 L’Algorithme 53 présente un exemple de programme (en fait, une fonc-

tion) qui ne s’arrête pas pour tout input. Celui-ci incrémente une variable j initialisée
à i (la valeur d’input), jusqu’à ce que j atteigne 5. Malheureusement, si la valeur i
fournie au programme est > 5, cela ne se produira jamais et le programme cyclera. Le
programme s’arrête par contre pour toute valeur i ≤ 5.

FonctionMalÉcrite(Entier i)
début
Entier j := i ;
tant que j 6= 5 faire
Afficher j ;
j := j + 1 ;
fin
Algorithme 53 : Un exemple de programme qui ne s’arrête pas toujours.

Il est donc important de bien comprendre que nous ne posons pas une question en
général sur le programme (« le programme cycle-t-il ? »), mais bien sur une exécution
particulière du programme (« le programme cycle-t-il pour une certaine input ? »). Ce
que nous désirons, c’est un algorithme A, unique, qui est capable de répondre à cette
question quelque soit le programme P et quelque soit l’input I. Nous allons démontrer
que cela n’est pas possible :

Théorème 10 Il n’existe pas d’algorithme pour résoudre le problème du test d’arrêt.

1 Né en 1862 à Königsberg et décédé en 1943 à Göttingen.
2 Il s’agit d’une équation de la forme p = q où p et q sont deux polynômes à coefficients entiers, d’un
nombre arbitraire de variables.
3 Né en 1912, Turing est considéré comme un des pères fondateurs de l’informatique. Ses travaux per-

mettent de poser les bases de l’informatique théorique, tel qu’on la conçoit encore aujourd’hui. Il aide les
alliés pendant la seconde guerre mondiale en découvrant le code de la machine Enigma utilisée par les nazis
pour chiffrer leurs messages secrets. Condamné pour homosexualité, il se suicide en 1952, en croquant une
pomme trempée dans du poison. La légende veut que le logo de la société californienne Apple Computers a
été choisi en hommage à Turing.
4 Né en 1903 et décédé en 1995.
 143

Preuve. La preuve fonctionne par contradiction. Cela signifie que nous allons supposer
que la théorème est faux, et nous allons en dériver une contradiction, ce qui prouvera
que notre hypothèse « le théorème est faux » est elle-même fausse (et donc, le théorème
est vrai).
Supposons donc qu’il existe un algorithme A qui résolve le problème de l’arrêt. Cet
algorithme peut être exprimé sous la forme d’une fonction qui reçoit :
1. Un programme P encodé sous forme d’une chaîne de caractères ;
2. Une input I pour le programme P ;
et qui renvoie vrai si et seulement si P s’arrête quand il est exécuté sur I. Dans la suite,
nous dénoterons par P(I) l’exécution de P sur I.
Afin de rendre la preuve plus aisée nous allons supposer que l’input I est toujours
une chaîne de caractère. On pourrait croire que cela contredit notre desiderata stipulant
que A doit fonctionner pour n’importe quel programme. Ce n’est en fait pas le cas. En
effet, si P n’a pas une chaîne de caractères pour input, il est facile de le transformer en
un programme P′ qui a une chaîne de caractères pour input et qui convertit la chaîne
dans le bon format avant d’appeler P sur le résultat de la conversion. Clairement, P′
s’arrête si et seulement si P s’arrête, donc on peut appliquer A sur P′ pour savoir si P
s’arrête.
Par exemple, si P reçoit deux entiers en input, on construit le programme P′ qui
reçoit une chaîne des caractères qui représente les deux entiers séparés par une virgule
(ainsi, 5 et 24 sont représentés par la chaîne 5,24). On peut alors facilement extraire
les entiers de la chaîne, et appeler P.

Nous avons donc à notre disposition un algorithme A, qui reçoit une chaîne de
caractères P (le programme) et une chaîne de caractères I (l’input) et qui est tel que :

Pour tout P et pour tout I : A(P, I) = vrai

ssi
P(I) ne cycle pas

Nous arrivons maintenant au point central de la preuve, qui tient dans l’observation
suivante :
Comme I est une chaîne de caractères, rien ne nous empêche de choisir un
programme (qui est aussi une chaîne de caractères) comme input.
On peut donc construire une fonction Paradoxe qui reçoit un programme (donc une
chaîne de caractères) en input et se comporte ainsi :
Booléen Paradoxe(Chaine P)
début
si A(P, P) = vrai alors
tant que vrai faire
Afficher « Bonjour » ;
retourner faux ;
sinon
retourner vrai ;
fin
Que fait la fonction Paradoxe ? Elle appelle l’algorithme qui teste l’arrêt du pro-
gramme P quand il est exécuté avec son propre code pour input. Si A renvoie vrai,
c’est-à-dire si P(P) ne cylce pas, Paradoxe entre alors dans une boucle infinie. Dans
144 CHAPITRE 8. CONCLUSION : AUX LIMITES DE L’ALGORITHMIQUE

le cas contraire, Paradoxe renvoie faux. Autrement dit, l’exécution de Paradoxe(P)

cycle uniquement si P appelé sur lui-même ne cycle pas. Par ailleurs, Paradoxe(P) ne
cycle pas à la seule condition que P exécuté sur lui-même cycle. Bref :

Pour tout P : Paradoxe(P) cycle

ssi (8.1)
P(P) ne cycle pas

Comme nous l’avons vu, Paradoxe peut être appelée sur n’importe quel programme.
Donc, en particulier, Paradoxe peut être appelée sur elle-même ! Voyons ce que cela
signifie. Clairement, il y a deux possibilités : soit Paradoxe cycle quand on l’appelle
sur elle-même, soit elle ne cycle pas. Considérons cela plus en détail. Nous allons utili-
ser l’information donnée par (8.1) ci-dessus, en remplaçant P (le programme sur lequel
Paradoxe est appelée) par Paradoxe :
1. Si Paradoxe(Paradoxe) cycle, nous déduisons de (8.1) que P(P) ne cycle pas,
c’est-à-dire que Paradoxe(Paradoxe) ne cycle pas. . .
2. Par contre, si Paradoxe(Paradoxe) ne cycle pas, l’équation (8.1) nous apprend
que Paradoxe(Paradoxe) doit cycler. . .
Nous concluons donc que Paradoxe(Paradoxe) est une fonction qui cycle si et seule-
ment si elle ne cycle pas ! Clairement, une telle fonction ne peut pas exister. Or, cette
fonction ne contient rien d’autre qu’un appel à A (l’algorithme qui résout le problème
du test d’arrêt) et une boucle infinie. Donc, si Paradoxe n’existe pas, c’est nécessaire-
ment parce que A n’existe pas. 
Ce simple raisonnement nous prouve qu’il existe au moins un problème qu’aucun
algorithme ne peut résoudre. Par le même genre de raisonnement, on peut prouver :
– qu’il n’existe pas d’algorithme pour savoir si un programme donné atteint tou-
jours une ligne de code donnée ;
– qu’il n’existe pas d’algorithme pour savoir si une certaine variable peut contenir
une certaine valeur dans un certain programme ;
– qu’il n’existe pas d’algorithme pour savoir si un programme ne cycle jamais
(quelque soit son input) ;
– ...
À vrai dire, toutes les propriétés un tant soit peu intéressantes des programmes ne
peuvent pas être vérifiées par un algorithme.
Néanmoins, les limites précises de l’algorithmique restent encore à définir. Entre les
problèmes insolubles et ceux pour lesquels on connaît des algorithmes, il reste encore
beaucoup de questions ouvertes (voir, pour plus de détails, des ouvrages de référence
comme [10, 6]). Par ailleurs, le fait qu’il existe un algorithme pour un problème donné
ne signifie pas que tout est dit sur cette matière : il reste certainement de nombreux
algorithmes à améliorer, tant sur le plan théorique que pratique.

Pour conclure, nous espérons que ces quelques exemples auront suscité la curiosité
du lecteur, qui trouvera dans ces questions un sujet de réflexions intéressant et toujours
renouvelé. . .
Bibliographie

[1] Alfred V. Aho and Jeffrey D. Ullman. Foundations of Computer Science. Com-
puter Science Press, 1992.
[2] Gilles Brassard and Paul Bratley. Fundamentals of Algorithmics. Prentice-Hall,
1996.
[3] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to
Algorithms. MIT Press/McGraw-Hill, 1990.
[4] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction
à l’Algorithmique. Dunod, deuxième edition, 2002. ISBN : 9782100039227.
Traduction de [3].
[5] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathema-
tics : A Foundation for Computer Science. Addison-Wesley Longman Publishing
Co., Inc., Boston, MA, USA, 1994.
[6] Harry R. Lewis, Christos H. Papadimitriou, and Christos Papadimitriou. Elements
of the Theory of Computation. Prentice Hall PTR, Upper Saddle River, NJ, USA,
1997.
[7] Olivier Markowitch. Algorithmique I. Presses de l’Université Libre de Bruxelles.
Syllabus du cours dispensé en première bachelier Informatique, Faculté des
Sciences, ULB.
[8] Robert Sedgewick. Algorithms in C. Addison-Wesley, 1990.
[9] Robert Sedgewick. Algorithmes en langage C. Dunod, 1991. ISBN :
2100492977. Traduction de [8].
[10] Pierre Wolper. Introduction à la calculabilité, 3e édition. Dunod. ISBN :
9782100499816.

145