PLAN

1. Concept d’abstraction
2. Concept général de Type Abstrait de Données
3. Type Abstrait de Données
4. Implémentation d’un Type Abstrait de Données
A. Tableau
B. Liste Chaînée
C. Pile
D. File d’Attente
E. Graphe
F. Arbre
5. Complexité des Algorithmes
6. Aspects Généraux et Basiques de Tri
BIBLIOGRAPHIE

The Art of computer programming - Donald E. Knuth - Ed. Addison Wesley - 1970

Techniques fondamentales de programmation - Sébastien ROHAUT - Ed. Eyrolles - 2003

Introduction à l'algorithmique - Thomas [Link] , Charles [Link] , Ronald L. Rivest,

Clifford Stein - Ed. Eyrolles - 2007
1. CONCEPT D’ABSTRACTION

Construction des machines abstraites  expression d’une seule action (à la limite)

pour exprimer une spécification complexe

Une machine abstraite = {principes qui cachent des spécificités et détails

d’une machine réelle (ou d’une machine abstraite)}
en vue d’augmenter la portabilité et la facilité de développement,
d’utilisation et de maintenance des logiciels.

Ce concept d’abstraction  définition d’objet quelconque en termes d’actions que l’on

peut y effectuer et non en termes de son implémentation.
Les raisons qui ont conduit au fait qu’il n’est pas nécessaire de connaître
ni la représentation interne ni les algorithmes qui implémentent les opérations
des types primitifs (tels que entier, réel, booléen) sont les mêmes que celles qui guident
la construction de n’importe quel autre type plus complexe et ce, indépendamment de tout
langage de programmation.

Outils se servant des notions d’abstraction : TAA (Type Abstrait Algébrique),

TAD (Type Abstrait des Données),
notion de classe des langages OO.
2. CONCEPT GENERAL DE TYPE ABSTRAIT DE DONNEES

Type de donnée détermine le genre de contenu d’une donnée et les opérations pouvant être
effectuées sur la variable correspondante.

Type abstrait de donnée (TAD)  spécification mathématique d’un ensemble de données et

de l’ensemble des opérations qu’elles peuvent effectuer,
 cahier des charges qu’une structure réelle de données doit
implémenter.
 décrit sans préciser la représentation interne de cette
donnée.

Par exemple : - la notion d’ensemble,

- le mécanisme des classes abstraites qui permet de définir des méthodes qui

devront être implémentés par les classes filles, mais sans nécessairement
implémenter ces méthodes, de cette façon, on a l'assurance que les classes
filles respecteront le contrat (interface de programmation) défini par la classe
mère abstraite.
Un TAD met au même niveau les données et les opérations, et permet l’élaboration des
algorithmes :
1. d’abord d’une manière abstraite en faisant appel aux données et à des opérations
abstraites du TAD (couche supérieure),
2. ensuite relativement à un choix de représentation du TAD en mémoire
(couche inférieure).

De cette façon, le codage de la couche supérieure donnera lieu à des

programmes abstraits de haut niveau, stables, aisément compréhensibles et réutilisables.

Le codage de la couche inférieure implémentera un choix de la représentation du TAD en

mémoire sur base de ces programmes abstraits.

La couche supérieure est ainsi une référence qui restera inchangée quelle que soit la
modification apportée à la couche inférieure.
Toute donnée a besoin d’une représentation en mémoire, qui doit être en adéquation
± exacte avec sa nature.

Rôle d’une structure de données  fournir une implémentation de ces données en mémoire.

Une structure de données = modèle logique qui correspond à l’implémentation d’un TAD et
qui permet d’organiser les données d’une manière particulière
dans une machine afin de pouvoir être utilisées efficacement.

Lorsque la relation entre la nature d’une donnée et la structure de sa représentation est

lâche, cela peut impacter négativement :
- la structure du programme qui l’utilise,
- la consommation en temps et en espace dudit programme.
Une structure de données spécifie donc un ou plusieurs algorithmes pour chaque opération
du TAD et éventuellement un ensemble des données spécifiques pour la gestion de cette
structure de données.

Chaque algorithme doit en fait être un module, une composante logique qui spécifie un seul
thème en encapsulant solidement ses fonctionnalités et ses types.

Un même TAD peut fournir plusieurs structures de données avec

des performances différentes.

Le choix d’une structure de donnée pour une donnée dépend de :

- sa richesse structurelle à refléter plus ou moins correctement les relations effectives de
cette donnée dans le monde réel,
- sa simplicité à permettre une manipulation (accès, traitements, …) assez aisée de cette
donnée.
L’organisation de l’algorithmique (la partie active) d’un logiciel est fonction
de la structure de ses données (l’organisation de ses données, la partie passive).

Donc, une abstraction dans l’organisation des données définit un espace de raisonnement,
dénué des détails inutiles, où l’algorithmique correspondante peut s’exprimer
plus efficacement et plus rapidement.

 Un module ne vaut rien s’il ne dispose pas de structures de données appropriée pour
manipuler (lire, stocker, écrire, …) ses données.

L’organisation des données et l’organisation de l’algorithmique d’un programme déterminent

largement l’efficacité, la stabilité et la complexité de ce programme.
3. TYPE ABSTRAIT DE DONNEES

Un TAD est caractérisé essentiellement par :

1. sa signature qui définit la syntaxe du type et des opérations.

Elle spécifie, via les mots-clés Type, Utilise et Opérations le nom du TAD,
les noms des types des objets utilisés et
l’énoncé des types des objets que le TAD reçoit et qu’il renvoie pour chaque opération,

2. sa sémantique qui définit les propriétés des opérations (primitives).

Elle spécifie, via les mots-clés Préconditions et Axiomes
les domaines de définition des opérations et les propriétés des opérations.
Il peut y avoir 4 catégories d'opérations dans un TAD :
- opération de construction, où seul le résultat est doté du type spécifié,
- opération d’observation, où seul l’argument est doté du type spécifié,
- opération de transformation, où l’argument et le résultat sont dotés du type spécifié,
- opération constante, qui n’a pas d’argument.

Une opération peut être partielle,

c’est-à-dire, une opération qui n’est pas, dans son domaine de définition, partout définie.

Les axiomes sont comme des règles d’inférence logiques qui régissent les opérations du type
défini.
Ce système d'axiomes doit être non contradictoire (consistance) et
d’une complétude suffisante.
Exemples :

Type Booléen
Opérations vrai : → Booléen
faux : → Booléen
non : Booléen → Booléen
et : Booléen × Booléen → Booléen
ou : Booléen × Booléen → Booléen
Préconditions
Ø
Axiomes soient a, b : Booléen
non (vrai) = faux
non (non (a)) = a
vrai et a = a
faux et a = faux
a ou b = non (non (a) et non (b))
Type Ensemble
Opérations
créer : → Ensemble
vide : Ensemble → Booléen
ajouter : Élément x Ensemble → Booléen
supprimer : Élément x Ensemble → Booléen
appartient : Élément x Ensemble → Booléen
cardinal : Ensemble → Entier
Préconditions Ø
Axiomes soient A, B : Ensemble,
si A = B alors A a les mêmes éléments que B et
B a les mêmes éléments que A,
si A = B alors cardinal(A) = cardinal(B),
si cardinal(A)=0 alors A= Ø (A est vide),
si A Ո B = Ø alors il n’existe aucun élément qui
appartient à la fois à A et à B.
Type Segment
Utilise Entier, Elément
Opérations
seg : Entier → Segment
changer_ième : Segment x Entier x Elément → Segment
ième : Segment x Entier → Elément
taille : Segment → Entier
Préconditions
seg (i) est_défini_ssi i ≥ 0
ième (s,i) est_défini_ssi 0 ≤ i < taille (s)
changer_ième (s,i,e) est_défini_ssi 0 ≤ i < taille (s)
Axiomes
soient i, j : Entier, e : Elément, s : Segment
si 0 ≤ i < taille (s) alors ième (changer_ième (s,i,e),i) = e
si 0 ≤ i < taille (s) et 0 ≤ j < taille (s) et i ≠ j alors ième (changer_ième (s,i,e),j) = ième (s,j)
taille (seg (i)) = i
taille (changer_ième (s,i,e)) = taille (s)
Le type Segment qui est défini ci-avant réutilise (via le mot-clé Utilise) des types déjà définis

(Entier et Elément).

La signature de Segment est donc l'union des signatures des types utilisés
(Entier et Elément) et qui est enrichie des nouvelles opérations.

Le type Segment hérite donc des propriétés des types qui le constituent.
4. IMPLEMENTATION D’UN TAD

L’implémentation d’un TAD en structure de données (concrète) exige de :

- déclarer et spécifier la(les) structure(s) de données retenue(s) pour représenter le TAD
via une interface (qui doit être conforme à la spécification du TAD),
- produire les algorithmes de toutes les opérations (et éventuellement les traduire dans un
langage particulier) en veillant sur la complexité en temps et en espace de
ces algorithmes.

2 grandes catégories des structures de données :

- structures de données linéaires,
- structures de données non linéaires.
TABLEAU

Structure linéaire et statique de n éléments homogènes de données

(de même taille et même type), dans laquelle les éléments sont repérés au moyen de
positions d’emplacement adjacentes, séquentielles et contigües (indices) en mémoire vive.

Allocation d’un tableau simple : tab[i1:i2]

Accès à un élément de ce tableau : tab[exp] où exp est une expression censé retourner
une valeur d’indice
L’adresse en mémoire de n’importe quel élément tab[i] = base(tab) + (i-i1) * k
avec base(tab)= adresse du 1er élément de tab[i1:i2]
Opérations (soit un tableau tab[1:m]) :

1. Suppression d’éléments
Complexité défavorable (en temps) = O(m),
Composante principale = nombre de déplacements

2. Insertion d’éléments
Complexité défavorable (en temps) = O(m),
Composante principale = nombre de déplacements

3. Tri d’éléments (sur base d’une relation d’ordre)

Complexité (en temps) = O(m2)
Composante principale = nombre de comparaisons

4. Accès séquentiel
Complexité défavorable (en temps) = O(m),
Composante principale = nombre d’accès
5. Recherche
tab[1:m] non trié  recherche séquentielle
Complexité défavorable (en temps) = O(m),
Composante principale = nombre de comparaisons

tab[1:m] trié  recherche séquentielle ou recherche dichotomique (binaire)

Complexité défavorable (en temps) = O(log2m),
Composante principale = nombre de comparaisons

6. Fusion
Si 2 tableaux a[1:n] et b[1:m] à fusionner,
Complexité maximale en temps = O(n+m),
Composante principale = nombre d’accès.
Tableaux Multidimensionnels

Un tableau multidimensionnel est 1 tableau non simple tab[d1:f1,d2:f2,d3:f3, …, di:fi, …, dn:fn]

de taille m1*m2*m3*…*mi*…*mn, dans lequel chaque élément est repéré par n indices (n>1)

Physiquement, ce sont les lignes ou les colonnes du tableau multidimensionnel qui sont
logées dans des blocs de mémoire successifs et contigus par le système d’exploitation.

Si donc w est la taille des éléments d’un tel tableau, alors l’adresse de l’élément
tab[k1,k2,k3, … ,kn] en mémoire est :
- en stockage colonnes : base(tab) + w * (((…(en tn-1 + en-1 )tn-2 + … + e3)t2 + e2)t1 + e1),
- en stockage lignes : base(tab) + w * (((… (e1 t2 + e2) t3 + e3) t4 + … + en-1) tn + en),

où ti = fi - di + 1,
ei = ki - di (indice effectif qui exprime le déplacement de ki par rapport à l’indice à la
position 1 et relativement dans l’intervalle (di:fi)).
Tableaux Parallèles

Les tableaux parallèles sont une collection des tableaux de même dimension et
de même taille où l’ensemble des éléments situés à la même position sur chacun de
ces tableaux spécifient une sémantique particulière et déterminée.

Ainsi, les n tableaux de dimension 1 t1[d1:f1], t2[d2:f2], …, tn[dn:fn] peuvent constituer des
tableaux parallèles s’ils sont de même taille. Dans ce cas, l’ensemble des éléments situés à
la même position relative i sur chacun de ces tableaux t1[i], t2[i], …, tn[i] définissent un
objet ou un concept particulier.

Par exemple, soient les 3 tableaux Nom[1:n] de type String, DNaiss[1:n] de type Date et
Pds[1:n] de type Réel, l’ensemble des données Nom[k], DNaiss[k] et Pds[k] désignent une
personne dont le nom est Nom[k], la date de naissance est DNaiss[k] et le poids est Pds[k].
Sous forme des tableaux parallèles, les informations concernant l’objet ou le concept
particulier sont donc éparpillées sur plusieurs tableaux.

Pour éviter cet éparpillement, on fait parfois appel à la notion d’enregistrement, un méta-type
complexe hiérarchique qui peut regrouper dans une seule structure un ensemble d'éléments
(champs) de types différents.

Le tableau est une structure de données basique qui peut permettre d’implémenter la plupart
des autres structures de données.
LISTE

Structure linéaire et dynamique d’une suite de données (nœuds) homogènes ou non,

contiguës ou non, dont chacune est dotée d’un ou de plusieurs liens ou pointeurs
(informations spéciales permettant de relier ces données entre elles).

Dans ces conditions, les données successives (ordonnées) de la liste n’ont plus besoin
d’occuper des positions adjacentes en mémoire vive.
La liste supporte aisément et naturellement les opérations d’insertion et de suppression de
données.

base(lst) = adresse du 1er élément (tête) de la liste dont le nom est lst
taille d’une liste = nombre de ses nœuds.

Une liste peut être représentée sous forme symbolique (ou mathématique),
native (ou abstraite) ou sous forme de tableaux parallèles (et dynamiques).
Exemple, la liste sous forme symbolique anl = (Lion,Oiseau,Chien,Canard) peut,
sous forme native, être :

Lion 45 Canard nil Chien 87

59 87 36

base(anl)=59
Oiseau 36
45

et, sous forme des tableaux parallèles, être une configuration où l’on aura réservé 2
tableaux de même taille (NomAl[1:p] pour stocker le nom de chaque animal et
Suivant[1:p] pour stocker l’indice de l’animal suivant, avec p très grand), ainsi chaque
animal k est représenté par la paire NomAl[k] et Suivant[k].
liste monodirectionnelle = liste simple qui permet de chaîner ses éléments dans un seul sens
(p. ex, du premier élément que l’on a inséré dans la liste vers le
dernier élément)

liste multidirectionnelle = liste qui permet de chaîner ses éléments dans plusieurs sens
(p. ex, liste bidirectionnelle qui permet de chaîner ses éléments
dans 2 sens, particulièrement, de gauche à droite et de
droite à gauche)
Opérations - Soit une liste monodirectionnelle sous forme native dotée d’1 seul type de nœud

avec la configuration :

p info suiv

1. Construction de liste
Quelle que soit la forme, une liste est construite de proche en proche via des opérations
d’insertion (en début, en fin ou au milieu de la liste).
Complexité en temps d’une opération d’insertion en début de liste = O(constante).
2. Affichage de contenu d’une liste
Un algorithme possible permettant d’accéder successivement (par un accès séquentiel) à
chaque nœud de la liste est :

début
p ← base ()
tant que p≠nil faire afficher [Link]
p ← [Link]
fin

Composante principale de la complexité (en temps) = taille de la liste

3. Calcul de la taille d’une liste
Un algorithme possible d’une telle opération qui doit nécessairement parcourir toute
la liste (par un accès séquentiel) en commençant, par exemple, par son élément de tête,
est :

début
p ← base ()
t←0
tant que p≠nil faire t ← t+1
p ← [Link]
afficher t
fin

Composante principale de la complexité (en temps) = taille de la liste

4. Recherche d’une donnée dans une liste
Il s’agit d’accéder à un ou plusieurs nœuds de liste qui sont dotés des critères c de la
recherche.
Si la recherche doit se terminer dès que le 1er nœud a été trouvé et si la liste n’est pas
triée sur base de ces critères c, alors la seule possibilité est la recherche séquentielle à
l’image de l’algorithme :

début
p ← base ()
tant que (p≠nil) et ([Link]≠c) faire p ← [Link]
si p=nil alors afficher «aucun nœud ne possède les critères c»
sinon afficher «noeud trouvé»
fin

Aucun nœud ne possède les critères recherchés  complexité défavorable en temps =

O(taille de la liste).
5. Insertion d’une nouvelle donnée dans une liste info suiv
Soit la liste X (avec base(X)=s) où le nouveau nœud suivant : q
doit être inséré (après avoir initialisé [Link] avec l’information nécessaire I : [Link] ← I) :

Au milieu de la liste X, il faut :

a. trouver dans la liste X, par une recherche séquentielle, l’adresse p du nœud qui sera devant le nouveau nœud
à insérer,
b. [Link] ← [Link]
c. [Link] ← q

En fin de la liste X, il faut :

a. trouver dans la liste X, par un accès séquentiel, l’adresse p de l’actuel dernier nœud et lui signifier qu’il n’est
plus le dernier : [Link] ← q
b. signifier au nouveau qu’il devient le dernier nœud de la liste X : [Link] ← nil

En début de la liste X, il faut :

a. désigner au nouveau nœud son nœud suivant : [Link] ← base(X)
b. signifier au nouveau nœud qu’il devient le 1er nœud de la liste X : base (X) ← q
6. Suppression d’une donnée d’une liste
Soit la liste X (avec base(X)=s) et procédons à la suppression d’un nœud donné qui se
trouve :

Au milieu de la liste X, il faut :

trouver dans la liste X, par une recherche séquentielle, l’adresse p du nœud qui est devant celui qui doit être
supprimé et lui signifier son nouveau suivant : [Link] ← ([Link]).suiv

En fin de la liste X, il faut :

trouver dans la liste X, par un accès séquentiel, l’adresse p du nœud qui est devant le dernier nœud et lui
signifier qu’il devient le dernier nœud : [Link] ← nil

En début de la liste X, il faut :

signifier au nœud 1er nœud de la liste X qu’il n’en fait plus partie : base (X) ← base (X).suiv
Liste Circulaire à Entête

Liste qui contient, en plus de nœuds ordinaires de l’application, un nœud spécial

(le nœud d’en-tête) situé en tête de la liste et qui est pointé par le dernier nœud de cette
liste (adresse du 1er nœud ordinaire = base ().suiv).

Une liste circulaire X à en-tête vide est telle que base (X).suiv = base (X).

L’avantage principal d’une telle liste est d’accélérer certaines opérations et de les rendre
moins complexes, car :
- l’utilisation du pointeur nil n’est plus nécessaire,
- chaque nœud (ordinaire) possède un précédent et un suivant, et 1er nœud de la liste ne
constitue plus obligatoirement un cas particulier.
Liste Inversée

La notion de la liste inversée permet de généraliser l’utilisation de la liste en permettant à

des nœuds d’une liste principale de partager des informations avec d’autres nœuds
(via la manipulation des sous-listes).

Dans une liste inversée, chaque sous-liste est généralement représentée par un tableau de
pointeurs accessible à partir de chaque nœud de la liste principale.

Une liste inversée est en fait une structure qui peut ainsi porter plusieurs dynamiques.

Remarque : Toutes les opérations qui ont été exécutées ci-dessus sur une
liste monodirectionnelle peuvent être8 aisément s’envisager, mutatis mutandis,
sur une liste circulaire à en-tête, sur une liste multidirectionnelle et
sur une liste inversée.
Gestion dynamique de la mémoire

Les diverses manipulations sur une liste (suppressions, désaffectations, allocations abusives)

génèrent des «ordures» (nœuds invalides, inaccessibles, inutilisés ou inactifs occupant

inutilement de la place mémoire)  situations où aucune mémoire disponible.

Afin de contrôler et de gérer l’espace de mémoire vive, il faut une gestion dynamique de la
mémoire.

Cette gestion (qui peut être totalement prise en charge par le système d’exploitation ou
par le programme d’application qui manipule des listes) doit pouvoir :
1. marquer les nœuds encore utiles, au sein des listes, et
2. libérer tous les nœuds non marqués afin de libérer l’espace de mémoire qu’ils occupent.

De manière pratique, cette opération devrait se faire périodiquement et lorsque l’occupation

de la mémoire dépasse un certain seuil.
PILE

Structure linéaire et dynamique d’une suite de données homogènes ou non, à laquelle il n’est
possible d’ajouter et de retirer des données qu’à une seule des extrémités (le sommet).

La pile est une queue lifo (Last In First Out) dans laquelle le dernier élément ajouté doit être
le premier à en être retiré.

Il existe des situations fréquentes dans la vie, dans la gestion, … où il est souhaitable de
restreindre les insertions et les suppressions de données à un seul bout de la structure de
gestion utilisée et pas ailleurs, sinon il apparaît instantanément une situation chaotique ou
indésirable (implémentation des appels de sous-programmes,
calcul des expressions arithmétiques, gestion de la récursivité, …).

Une pile peut être logiquement ou physiquement implémentée sous forme native,
sous forme d’une liste monodirectionnelle ou sous forme d’un tableau simple (et dynamique).
Par exemple, la pile sous forme native : pile contenant 5 cellules,
où chaque cellule de la pile est constituée d’un champ de
d données et d’un pointeur vers la cellule précédente,
a opérations natives : push, pop et nil pour une pile vide,
z
y
x

peut être représentée sous la forme d’un tableau simple par : un tableau pile[i:k]
adéquatement alloué, une variable qui doit servir à contenir l’adresse relative (indice) de
l’élément au sommet de la pile (p. ex, top) et une variable qui doit servir à indiquer le
nombre maximum d’éléments qui peuvent être accommodés par la pile (p. ex, max),
comme suit :
… x y z a d …
i j j+1 j+4 k

avec top=j+4 et max=k-i+1

Opérations (considérons que la pile manipulée est sous la forme d’un tableau simple)

1. Test pour savoir si une pile est vide

Pour tester si une pile (accommodée par la portion pile[i:k] du tableau simple qui
implémente cette pile) est vide, il suffit d’exécuter l’instruction :

si top≤i-1 alors afficher «la pile est vide»

sinon afficher «la pile n’est pas vide»

2. Empilage d’un élément

Il s’agit d’ajouter un nouvel élément x au sommet de la pile (accommodée par la portion
pile[i:k] du tableau simple qui implémente cette pile).
Un algorithme possible d’empilement (push) doit contenir l’instruction suivante :

si top<max alors top ← top + 1

pile[top] ← x
sinon envoyer «erreur overflow»
3. Dépilage de l’élément (au sommet de la pile)
Il s’agit de supprimer l’élément qui est au sommet de la pile (accommodée par la portion
pile[i:k] du tableau simple qui implémente cette pile).
Un algorithme possible de dépilement (pop) doit contenir l’instruction suivante :

si top≥i alors x ← pile[top]

top ← top-1
sinon envoyer «erreur underflow»

4. Récupération de l’élément (au sommet de la pile)

Il s’agit d’accéder à l’élément qui est au sommet de la pile (accommodée par la portion
pile[i:k] du tableau simple qui implémente cette pile).
Un algorithme possible d’accès à cet élément doit contenir l’instruction suivante :

si top≥i alors x ← pile[top]

sinon envoyer «erreur underflow»
5. Vidange du contenu de la pile
Pour vider la pile (accommodée par la portion pile[i:k] du tableau simple qui implémente
cette pile), il suffit d’exécuter l’instruction : top ← i-1.
FILE D’ATTENTE

Structure linéaire et dynamique d’une suite de données homogènes ou non, dans laquelle les
insertions ne se font qu’à une extrémité (queue de la file) et les suppressions ne se font qu’à
l’autre extrémité (tête de la file). Elle permet de mettre en attente des données dans le but
de les récupérer plus tard, dans leur ordre d’arrivée (processus en attente pour exécution,
accès à un périphérique, …).

La file d’attente est une queue fifo (First In First Out) dans laquelle le premier élément ajouté
doit être le premier à en sortir. Elle ne donne accès qu’à un seul élément, la tête de la file.

Une file peut être logiquement ou physiquement implémentée sous forme native (ou
abstraite), sous forme d’une liste monodirectionnelle ou sous forme d’un tableau simple
(et dynamique).
Par exemple, la file suivante (avec 5 cellules), sous forme native :

tête d a z y x queue

avec comme opérations natives défiler (dequeue), enfiler (enqueue), nil pour une file vide,
où chaque cellule de la file est constituée d’un champ de données et d’un pointeur vers la
cellule suivante,
peut être représentée sous la forme d’un tableau simple par un tableau file[i:k]
adéquatement alloué, une variable qui doit servir à contenir l’adresse relative (indice) de
l’élément de tête de la file (p. ex, tête) et une variable qui doit servir à contenir l’adresse
relative (indice) de l’élément de queue de la file (p. ex, queue), comme suit :

… d a z y z …
i j j+1 j+4 k

avec tête=j et queue=j+4

Sous la forme d’un tableau simple, la suppression de l’élément à la tête  tête ← tête + 1,
l’insertion d’un élément en queue  queue ← queue + 1

Donc, après n insertions, le dernier élément de la file occupera une place file[j], même si
toutes les places devant ce dernier élément sont vides ou occupées par des données
obsolètes.
Si donc un nouvel élément doit être inséré dans une file qui n’est pas pleine mais pour
laquelle i<tête, il faudra :
- déplacer toute la file vers le début du tableau file[i:k],
- modifier, de façon adéquate, les variables tête et queue,
- insérer ce nouvel élément.

Cela nécessite donc un déplacement qui peut augmenter la complexité de l’opération de

l’insertion.
Pour éviter ce déplacement, on peut considérer que le tableau file[i:k] est «circulaire»,
c’est-à-dire qu’après avoir occupé la place file[k], l’insertion suivante se fera sur file[1]
(donc queue=1).
Opérations (considérons que la file manipulée est sous la forme d’un tableau simple)

1. Test pour savoir si une file est vide

Pour tester si une file (accommodée par la portion file[i:k] du tableau simple qui
implémente cette file) est vide, il suffit d’exécuter l’instruction :

si queue<tête alors afficher «la file est vide»

sinon afficher «la file n’est pas vide»

2. Enfilement d’un élément

L’algorithme d’enfilement d’un nouvel élément x en queue de la file accommodée par la
portion file[i:k] du tableau simple qui implémente cette file et qui n’est pas «circulaire»
(et où queue<k) doit contenir la séquence suivante :

queue ← queue + 1
file[queue] ← x
3. Désenfilement d’un élément
Il s’agit de supprimer l’élément de tête de la file (accommodée par la portion file[i:k] du
tableau simple qui implémente cette file). Un algorithme possible de désenfilement doit
contenir la séquence suivante :

x ← file[tête]
tête ← tête+1

4. Récupération de l’élément (en tête de la file)

Un algorithme possible d’accès à l’élément qui est en tête de la file (accommodée par la
portion file[i:k] du tableau simple qui implémente cette file) doit contenir l’instruction
suivante : x ← file[tête]

5. Vidange d’une file

Pour vider la file (accommodée par la portion file[i:k] du tableau simple qui implémente
cette file), il suffit d’exécuter l’instruction : queue ← tête - 1.
File d’attente à niveaux de priorité

File d’attente dans laquelle un niveau de priorité (relatif à l’opération de défilement) est
affecté à chacun de ses éléments dans la file
(ex : file d’attente à niveaux de priorité d’un système d’exploitation multiprogrammé à temps
partagé).

Généralement, ce niveau de priorité conditionne le retrait de ces éléments selon les principes
suivants :
- un élément de priorité supérieure est traité avant tout élément de priorité inférieure,
- deux éléments de même priorité sont extraits et traités selon l’ordre dans lequel ils ont été
insérés dans la file d’attente.
File (d’attente) à niveaux de priorité

File d’attente dans laquelle les éléments peuvent être ajoutés ou supprimés à l’une ou
à l’autre extrémité (file dotée donc de 2 queues ou 2 têtes).

Variantes de deque :
- deque à entrée restreinte, qui n’accepte des insertions qu’à une seule de ses extrémités,
mais permet des extractions à ses 2 extrémités,
- deque à sortie restreinte, qui n’accepte des extractions qu’à une seule de ses extrémités,
mais permet des insertions à ses 2 extrémités.

Remarque : Toutes les opérations qui ont été exécutées ci-dessus sur une file peuvent,
mutatis mutandis, aisément s’envisager sur une file à niveaux de priorité et
sur une deque.
GRAPHE

Structure de données non linéaire, formellement notée G=(V,E), où :

- V est un ensemble de nœuds u0, u1, u2, …, un,
- E est un ensemble d’arêtes ou arcs (arêtes pourvues de sens) qui relient les nœuds de la
structure.
Exemple : G=(villes, routes), graphe qui représente les routes connectent les villes d’un
espace donné

Chemin = suite quelconque d’arêtes ou d’arcs d’un graphe, notée p=(u0, u1, u2, …, un), dont
les extrémités sont u0 et un, et telle que ui et ui+1 sont des nœuds adjacents pour
tout i (0 ≤ i ≤ n-1)

Longueur de chemin = nombre d’arêtes ou d’arcs constituant ce chemin

Chemin simple = chemin dont les nœuds sont tous distincts

Chemin orienté = chemin dont les arcs sont tous orientés dans le même sens
Cycle = chemin p=(u0, u1, u2, …, un) fermé dans lequel u0 = un

k-cycle = cycle de longueur k

Boucle est une arête ou un arc x=(ui,uk) où ui=uk.

Graphe non orienté = graphe dans lequel, étant donné 2 nœuds, ui et uk, si x=(ui,uk) ∈ E,
alors x est une arête qui constitue une paire non ordonnée et, ui et uk

sont des nœuds adjacents et sont des extrémités de x

deg(ui) = degré du nœud ui = nombre d’arêtes attachées à ce nœud

Graphe orienté (diagraphe) = graphe composé d’arcs, chaque arc étant est repéré par une
paire ordonnée x=(ui,uk), ( (ui,uk) ≠ (uk,ui) ).
Dans l’arc x=(ui,uk), ui est l’origine (extrémité initiale) de x,
uk est la destination (extrémité terminale) de x,
ui est le prédécesseur de uk, uk est le successeur de ui.

D+(ui) = degré extérieur du nœud ui = nombre d’arcs dont l’origine est ui

D-(ui) = degré intérieur du nœud ui = nombre d’arcs dont la destination est ui

Nœud ui est source si D+(ui) > 0 et D-(ui) = 0

Nœud ui est puits si D+(ui) = 0 et D-(ui) > 0
Graphe fortement connecté = graphe orienté dans lequel 2 nœuds ui et uk, quels qu’ils soient,
sont tels qu’il existe un chemin orienté de ui vers uk et
de uk vers ui.

Graphe unilatéralement connecté = graphe orienté dans lequel 2 nœuds ui et uk, quels qu’ils
soient, sont tels qu’il existe un chemin orienté de
ui vers uk ou de uk vers ui.

Graphe étiqueté = graphe dans lequel chaque arête ou arc porte un poids

Graphe connecté = graphe dans lequel 2 nœuds ui et uk, quels qu’ils soient, sont toujours
reliés par un chemin simple

Graphe arborescent = graphe connecté ou fortement connecté sans cycles

Multigraphe = graphe dans lequel il existe des arêtes ou des boucles multiples,
2 arêtes x et y sont dites «arêtes multiples», si elles connectent les mêmes
extrémités, c’est-à-dire que x=(ui,uk) et y=(ui,uk)

Graphe connexe = graphe non orienté dans lequel tout nœud peut être relié à tout autre
nœud par une arête ou par un chemin, un tel graphe tient donc d’un seul
tenant.
Un graphe peut être logiquement ou physiquement implémenté (représenté) sous forme
native (ou abstraite), sous forme d’un tableau à 2 dimensions
(matrice d’adjacence ou matrice de contigüité),
sous forme d’une liste où chaque nœud ui est dotée de l’ensemble de ses nœuds successeurs
(liste simple, liste inversée ou tableaux parallèles).
Par exemple, le graphe orienté sous forme native suivant : a d
e
b c

peut être représenté sous forme de tableaux parallèles, à l’aide de :

- 5 tableaux parallèles articulés en 2 groupes (relatifs aux nœuds et aux arcs) :
nœud [1..10] pour décrire les nœuds du graphe,
suiv [1..10] pour pointer sur le nœud suivant du graphe,
succ [1..10] pour pointer sur le 1er successeur de chaque nœud,
dest [1..12] pour spécifier chacun des premiers successeurs de chaque nœud,
lnk [1..12] pour lier tous les autres successeurs de chaque nœud,
- départ, variable qui garde l’indice de début des nœuds,
- «/», qui est une marque adéquatement choisie par l’application pour désigner la fin des
nœuds ou des arcs au sein des tableaux suiv, succ et lnk.

Tous les nœuds d’un chemin dont l’origine est uk (c’est-à-dire tous les successeurs de uk) sont
chaînés en une seule suite derrière dest(succ(k)).
Ainsi, si départ=4, sous forme de tableaux parallèles, le graphe ci-dessus peut être implémenté
comme suit :
indice dest lnk

indice noeud suiv succ

1 2 7
1 2
2 c 9 / 3 7 10
3 4 9 /
4 a 7 3 5
5 6 2 /
6 e / 11 7 6 /
8
7 b 2 6
9
8
10 2 4
9 d 6 1 11 2 /
10 12
Opérations
Soit un graphe implémenté sous forme des tableaux parallèles (nœud[:], suiv[:], succ[:],
dest[:], lnk[:] tels que définis ci-avant) pour illustrer ces opérations.

1. Recherche de nœud
Si z sont des critères de recherche, alors un algorithme possible de recherche du 1er nœud
du graphe qui répond à z est :

RechercheNoeud ()
début
i ← départ
tant que (i≠/) et (nœud[i] ne contient pas «z») faire i ← suiv[i]
si i=/ alors retourner «aucun nœud trouvé»
sinon retourner i
fin
2. Recherche d’arc
Afin de connaître l’emplacement ou de vérifier l’existence de l’arc (ui,uk), il faudra, étant
donné l’indice i du nœud ui et l’indice k du nœud uk, chercher uk parmi les successeurs
de ui. Un algorithme possible de recherche de cet arc est :

RechercheArc ()
début
i ← RechercheNoeud () (1)
k ← RechercheNoeud () (2)
si (i=/) ou (k=/) alors retourner /
sinon retourner s ← RechercheNoeud () (3)
fin

L’instruction (1) cherche l’indice du nœud i dans le tableau nœud[:],

l’instruction (2) cherche l’indice du nœud k dans le tableau nœud[:],
l’instruction (3) cherche l’indice du nœud succ[i] dans la suite issue de dest[succ[k]].
3. Insertion de nouveau noeud
L’insertion d’un nouveau nœud uk isolé (n’appartenant à aucun arc) en un indice libre
du tableau nœud[:] peut s’accomplir de la manière suivante :

InsertionNoeud ()
début
i ← ChercherIndiceLibre (nœud[:]) (1)
si i = / alors renvoyer «Insertion impossible du nœud»
sinon nœud [i] ← uk
suiv [i] ← départ
succ[i] ← /
départ ← i
renvoyer «Insertion accomplie»
fin

L’instruction (1) cherche le premier indice libre dans le tableau nœud[:].

4. Insertion de nouvel arc
L’insertion d’un nouvel arc (ui,uk) dans le graphe revient à trouver l’indice i du nœud ui
(origine de l’arc) et l’indice k du nœud uk, et d’insérer k dans l’ensemble de successeurs
de ui (soit, [Link], comme 1er successeur de ui) selon la philosophie suivante :

InsertionArc ()
début
i ← RechercheNoeud ()
k ←RechercheNoeud ()
j ← ChercherIndiceLibre (dest[:]) (1)
si j=/ alors renvoyer «Insertion impossible de l’arc»
sinon dest (j) ← k
lnk (j) ← succ (i)
succ (i) ← j
renvoyer «Insertion accomplie»
fin

L’instruction (1) cherche le premier indice libre dans le tableau dest[:]

5. Suppression de nœud dans un graphe
Soit la procédure Nettoyage(nœud[:],suiv[],départ,uk,z) qui supprime le nœud uk
du tableau nœud[:] en commençant la recherche de ce nœud uk à partir de l’indice départ
et qui indique l’issue de cette opération de suppression dans la variable z :

Nettoyage (nœud[:],suiv[],départ,uk,z)
début
z ← faux
si départ≠/
alors si nœud[départ] = uk alors p ← départ; départ ← suiv[départ]; z ← vrai
sinon p ← suiv[départ]; s ← départ
tant que (p≠/) et (z=faux) faire si nœud [p] = uk
alors suiv [s] ← suiv [p]
z ← vrai
s←p
p ← suiv [p]
fin
alors pour supprimer le nœud uk du graphe, il suffit de :
- trouver l’indice k de ce nœud uk,
- supprimer tous les arcs dont le nœud uk est la destination (c’est-à-dire supprimer le nœud uk
dans la suite des successeurs de chaque nœud du graphe),
- supprimer tous les arcs qui sont sur les chemins dont le nœud uk est l’origine
(c’est-à-dire trouver l’indice d du 1er successeur du nœud uk et l’indice f du dernier
successeur du nœud uk de tous ces chemins),
comme suit :
 SuppressionNoeud ()
début
z ← faux
k ← RechercheNoeud ()
si k≠/ alors p ← départ
tant que p≠/ faire Nettoyage (dest[:],lnk[:],succ[p],k,z) (1)
p ← suiv[p]

si succ[k] ≠/ alors d ← succ[k] (2)

f ← succ[k]
p ← lnk[f]
tant que p≠/ faire f ← p
p ← lnk[p]

Nettoyage (nœud[],suiv[],départ,uk,z) (2)

fin

(1) : suppression du nœud[k] du tableau dest[:] en commençant la recherche de ce nœud[k] à partir de la position
succ[p]. Tous les arcs dont le nœud uk est la destination seront ainsi supprimés
(2) : suppression de tous les arcs qui sont sur les chemins dont le nœud u k est l’origine
6. Parcours séquentiel de graphe
Opération pour accéder séquentiellement à tous ou à une grande partie de nœuds d’un
graphe afin d’y appliquer un (même) traitement.
2 manières principales d’exécuter ce parcours :
- parcours par contagion, qui utilise une file d’attente pour ranger les nœuds qui sont en
attente du traitement,
- parcours par sondage, qui utilise une pile.

Quel que soit le parcours, tout nœud uk du graphe sera dans l’un des 3 états :
- état «prêt» : état initial de uk,
- état «attente» : état d’attente de uk dans la file d’attente ou dans la pile,
- état «traîté» : état final d’un noeud uk traité.
Un algorithme possible du parcours par sondage est :

début
mettre tous les nœuds de G à l’état «prêt»,
empiler le nœud de départ uk dans la pile Q et faire passer son état à «attente»,
tant que pile Q non vide faire désempiler le nœud um,
traiter le nœud um,
faire passer l’état du nœud um à «traité»,
empiler les nœuds voisins du nœud um (ceux qui sont à l’état «prêt») dans la pile,
et faire passer leur état à «attente»
fin
Exemple : soit un graphe orienté représentant les vols quotidiens d’une compagnie
aérienne entre diverses villes,
w

f c b

d z g

j k

dont la matrice d’incidence est :

w f, c, b
b g, c
c f
d c
z d, c, j
f d
g c, z
j d, k
k z, g
Supposons que l’on désire trouver toutes les villes accessibles à partir de la ville représentée
par le nœud j, cela revient à accomplir un parcours séquentiel de ce graphe.
Si nous considérons un parcours par sondage, ses différentes étapes seront :

- empiler j  Q : j
- désempiler j, traiter j et empiler ses voisins  Q : d, k
- désempiler k, traiter k et empiler ses voisins  Q : d, z, g
- désempiler g, traiter g et empiler ses voisins  Q : d, z, c (le nœud voisin z du nœud g a déjà été empilé)
- désempiler c, traiter c et empiler ses voisins  Q : d, z, f
- désempiler f, traiter f et empiler ses voisins  Q : d, z
- désempiler z, traiter z et empiler ses voisins  Q : d (les nœuds voisins c et j du nœud z ont déjà été traités)
- désempiler d, traiter d et empiler ses voisins  Q : nil.

La pile Q est vide, les nœuds du graphe accessibles à partir du nœud j sont :
j, k, g, c, f, z et d
Tri Topologique

Soit un graphe G=(V,E) dans lequel chaque arc exprime une relation hiérarchique, de
précédence ou de préséance.
Par exemple, un graphe dans lequel chaque nœud uk représente une tâche et chaque arc
(ui,uk) spécifie une relation de précédence signifiant que l’achèvement de la tâche ui est un
préalable (représenté par ‘<‘) pour que la tâche uk démarre.

Un tel graphe ne peut donc comporter ni cycles ni boucles, il vient que :

- ui < ui est impossible  non réflexivité,
- si ui < uk alors uk < ui est impossible  asymétrie,
- si ui < uk et uk < um alors ui < um  transitivité.

Une telle relation permet de trier topologiquement le graphe G qui est alors comparable à un
ensemble partiellement ordonné.
Un tri topologique de G fournit donc un ordonnancement linéaire de ses nœuds.
Si le graphe G est un graphe orienté fini sans circuit alors il existe un tri topologique T de G
dont l’idée principale tourne itérativement autour de 2 opérations basiques :
- trouver un nœud uk tel que D-(uk)=0, et
- supprimer le nœud uk et ses arcs.

Une procédure de tri topologique dans laquelle une file d’attente est utilisée pour ranger
temporairement les nœuds dont le degré intérieur D-()=0 est :

Procedure TriTopologique ()
début
pour tout nœud uk, calculer D-(uk),
mettre dans queue tout nœud ui dont D-(ui) = 0,
tant que queue non vide faire extraire nœud um de queue
pour chaque voisin up de um répéter
D-(up) ← D-(up) - 1
si D-(up) = 0 alors mettre up dans queue
fin
ARBRE

Graphe G=(V,E), simple non orienté, connexe et sans cycle, dans lequel :
- l’ajout d’une arête quelconque crée un cycle,
- G n’est plus connecté si l’on retire n’importe qu’elle arête,
- tout couple de nœuds de G sont reliés par un chemin unique.

Formellement, un arbre est une structure des données non linéaire qui est surtout utilisée
pour des informations dont les éléments sont liés par des relations hiérarchiques
(tables de matières, index, répertoires, arbres généalogiques, …).
Mathématiquement, un arbre T = ensemble fini, éventuellement vide, de nœuds (dont un
nœud particulier ur appelé racine) dans lequel :
- tout nœud ui (sauf la racine) possède un nœud parent (prédécesseur) up d’où est
directement issu ui,
- tout nœud ui peut avoir des nœuds enfants (successeurs) us qui proviennent
directement de ui.

Les nœuds qui n’ont pas de nœud enfant sont des feuilles.
Tous les autres nœuds de l’arbre (sauf sa racine) sont des nœuds descendants de ur,
c’est-à-dire qu’ils sont issus directement ou indirectement de ur.

Nœuds frères (Nœuds voisins) = nœuds issus du même nœud parent.

Chemin = séquence d’arrêtes consécutives (succession de nœuds enfants), s’il existe

un chemin de uk à ud, le nœud uk est l’ancêtre de ud.
Longueur de chemin = nombre d’arrêtes constituant ce chemin.

Branche = tout chemin qui se termine par une feuille.

Profondeur (Hauteur) = longueur de chemin la plus grande dans un arbre.
Forêt = ensemble d’arbres distincts (ou d’arbres connexes différents).

2 arbres T et V sont similaires s’ils ont la même structure avec le même nombre et le même
type d’enfants à chaque sous arbre.
2 arbres T et V sont des copies, s’ils sont similaires et s’ils présentent le même contenu
aux nœuds correspondants.
Arbres Remarquables

* Arbre Binaire
T est un arbre binaire si, étant donné la racine ur de T, les autres nœuds forment une paire
ordonnée de sous-arbres disjoints T1 et T2 avec
T1 = sous-arbre de gauche de ur et T2 = sous-arbre de droite de ur.
La racine de T1, si elle existe, est le successeur gauche de ur,
la racine de T2, si elle existe, est le successeur droit de ur.

Tout nœud uk d’un arbre binaire T possède donc 2 successeurs au maximum, et tout nœud
doté d’un ou de 2 enfants est un nœud interne, tout nœud sans enfant est
un nœud externe.
Exemple : l’expression algébrique e=(a-b) / ((c*d)+e) peut être représentée par un arbre
binaire où les opérateurs sont dans les nœuds internes et les opérandes sont des
nœuds externes :

- +

a b * e

c d
* Arbre Binaire Complet
Arbre binaire où : - chaque niveau, sauf éventuellement le dernier, comporte 2 nœuds,
- tous les nœuds terminaux qui apparaissent au dernier niveau et qui
sont seuls, sont à gauche.
Donc, il n’existe qu’un seul arbre complet T comportant exactement n nœuds.
Profondeur d’un arbre binaire complet doté de n nœuds = (log2n) +1.

Exemple : le seul arbre binaire complet comportant 12 nœuds se présente comme suit :

2 3

4 5 6 7

8 9 10 11 12
* Arbre Binaire Ordonné
Arbre binaire complet où tout nœud ui possède une des propriétés suivantes :
- la valeur de ui est supérieure ou égale à celle de chacun de ses enfants (et donc à celle de
tous ses descendants)  arbre binaire ordonné est une maxipile,
- la valeur de ui est inférieure ou égale à celle de chacun de ses enfants (et donc à celle de
tous ses descendants  arbre binaire ordonné est une minipile.

Exemple d’une maxipile :

97

88 95

77 55 95 48

77 35 48 55 62
* Arbre Binaire Etendu (Pair)
Arbre binaire dans lequel chaque nœud possède 0 ou 2 enfants (dans un tel arbre binaire
chaque nœud interne est doté de 2 enfants).
Tout arbre binaire peut être transformé en arbre binaire étendu :
- en remplaçant chaque sous-arbre vide par un nœud nouveau,
- en ajoutant 2 nœuds externes aux nœuds terminaux.

Exemple : l’arbre binaire peut être transformé en l’arbre binaire étendu en ajoutant des nouveaux arcs (en pointillé)

et des nouveaux artificiels (N)

9 9

1 5 1 5

4 7 4 N 7 N

3 N N N 3

N N
Soit T un arbre binaire étendu où :
x = nombre de nœuds externes,
i = nombre de nœuds internes,
li = somme de toutes les longueurs de chemin j allant de la racine vers chaque
nœud interne,
le = somme de toutes les longueurs de chemin j allant de la racine vers chaque
nœud externe,
alors x = i + 1 et le = li + (2 * i).

Lorsque l’on affecte un poids (non négatif) wi à chaque nœud externe, on peut calculer
la longueur p de chemin pondérée en vue de résoudre efficacement une classe de
problèmes de recherche modélisés à l’aide de l’arbre binaire.
Le problème de recherche des arbres ayant une longueur de chemin pondérée minimum se
pose dans beaucoup de domaines et l’algorithme de Huffman, dans la plupart de cas, a été
une réponse à ce problème.

La valeur de p sera alors la somme des longueurs de chemin pondérées

w1le1 + w2le2 + … + wnlen où wi est le poids du chemin vers le nœud externe i et
lei est la longueur du chemin du nœud externe i.
* Arbre de Recherche Binaire
Un arbre binaire dans lequel tout nœud uk est tel que :
- la valeur du nœud uk est supérieure à toute valeur de nœud contenu dans le sous-arbre
qui est gauche de uk, et
- la valeur du nœud uk est inférieure à toute valeur de nœud contenu dans le sous-arbre qui
est droite de uk.

Le parcours d’un tel arbre dans un certain ordre fournira une liste ordonnée de ses nœuds.
* Arbre Généralisé
Un arbre généralisé est simplement un arbre T, un ensemble non vide de nœuds ayant :
- une racine, et
- des sous-arbres disjoints T1, T2, …, Tm, et où il n y a ni enfant de gauche,
ni enfant de droite.

Ainsi donc, les arbres : 60 60

50 et 50

22 30 22 30

considérés comme des arbres binaires, ces 2 arbres sont différents,

mais considérés comme des arbres généralisés, ces 2 arbres sont identiques.
Un arbre généralisé peut être logiquement ou physiquement implémenté sous forme native,
sous forme d’un tableau à 2 dimensions (matrice d’adjacence ou matrice de contigüité),
sous forme d’une liste où chaque nœud ui est dotée de l’ensemble de ses nœuds successeurs
(liste simple, liste inversée ou tableaux parallèles).

Un arbre binaire peut être logiquement ou physiquement implémenté efficacement

sous forme native, sous forme d’un tableau unique ou sous forme de tableaux parallèles.

Par exemple, pour implémenter un arbre binaire T sous la forme de tableau unique, on peut
allouer le tableau arbre[1:n] où :
- la racine ur de l’arbre binaire sera rangée en arbre[1],
- si un nœud est en arbre[k], alors son enfant de gauche sera rangé en arbre[2k] et son
enfant de droite sera rangé en arbre[2k+1].

La représentation d’un arbre de profondeur d sous cette forme nécessite un tableau dont la
taille est 2d.
Par exemple, pour implémenter un arbre binaire T sous la forme de tableaux parallèles,
on peut allouer les tableaux :
- info[1:n], pour contenir les informations des nœuds,
- left [1:n], pour contenir les indices des enfants qui sont à gauche,
- right [1:n], pour contenir les indices des enfants qui sont à droite.
- rac, une variable pour contenir l’indice de la racine de l’arbre.

Ainsi chaque nœud uk de l’arbre binaire correspond à un indice k tel que :

info[k] contient l’information de uk,
left[k] contient l’indice de l’enfant à gauche de uk, s’il existe,
right[k] contient l’indice de l’enfant à droite de uk, s’il existe.
Par exemple, pour implémenter un arbre généralisé T sous la forme de tableaux parallèles,
on peut allouer les tableaux info[1:n], enfant[1:n] et frère[1:n] où :
- info[k] contiendra l’information du nœud k,
- enfant[k] contiendra la position du premier enfant du nœud k (les autres enfants étant
mentionnés à la suite de ce premier enfant),
- frère[k] contiendra l’adresse du premier frère du nœud k (les autres frères étant
mentionnés à la suite de ce premier frère),
et la variable, root, qui contiendra l’adresse de la racine de T.
Opérations
La plupart des opérations proposées ci-après le sont pour un arbre binaire implémenté sous
forme des tableaux parallèles info[1:n], left [1:n] et right [1:n]
(la variable rac contenant l’indice de la racine de l’arbre).

Ces opérations peuvent être aisément étendues, mutatis mutandis, sur n’importe quelle autre
implémentation et pour n’importe quel arbre généralisé.
1. Parcours séquentiel
Lorsqu’il faut appliquer un traitement à tous les nœuds ou à une grande partie des nœuds
d’un arbre binaire T de racine ur, on peut utiliser 3 accès séquentiels standardisés :

pré-ordre : accès où, itérativement, on :

a. traite la racine ur,
b. parcourt le sous-arbre à gauche de ur,
c. parcourt le sous-arbre à droite de ur,

in-ordre : accès où, itérativement, on :

a. parcourt le sous-arbre à gauche de ur,
b. traite la racine ur,
c. parcourt le sous arbre à droite de ur,

post-ordre : accès où, itérativement, on :

a. parcourt le sous-arbre à gauche de ur,
b. parcourt le sous-arbre à droite de ur,
c. traite la racine ur.
Ces 3 parcours sont essentiellement récursifs et font défiler les feuilles dans le même
ordre.

Par exemple, soit l’arbre binaire : *

+ :

a - - -

b c d e + h

f g

son parcours pré-ordre correspond à l’expression en notation polonaise préfixée * + a - b c : - d e - + f g h

son parcours in-ordre correspond à l’expression en notation infixée (a+(b-c))*((d-e):(f+g-h))
son parcours post-ordre correspond à l’expression en notation polonaise postfixée a b c - + d e - f g + h - : *
Un algorithme possible de parcours en pré-ordre est :

début
empiler ‘/’ sur la pile Q
p ← rac
tant que p ≠ / faire traiter info [p]
si right [p] ≠ / alors empiler right [p]

si left [p] ≠ / alors p ← left [p]

sinon p ← désempiler Q
fin
2. Vidange (Nettoyage)
Pour vider un arbre de ses nœuds (quelle que soit son implémentation), il suffit d’exécuter
l’instruction :
rac ← / (rac est la variable qui représente l’adresse du nœud racine de l’arbre).
3. Recherche dans un arbre binaire de recherche
Il s’agit de chercher l’indice du nœud up qui contient les critères de recherche x au sein
d’un arbre T de recherche binaire.
L’algorithme qui détermine l’adresse lc de up et l’adresse pt de son parent peut être :

Recherche (info[], left[], right[], rac, x, lc, pt)

début
t ← faux
si rac = / alors lc ← /; pt ← /; t ← vrai
sinon si x = info [rac] alors lc ← rac; pt ← /; t ← vrai
sinon si x < info [rac] alors p ←left [rac]; s ←rac
sinon p ←right [rac]; s ←rac
tant que p ≠ / et t = faux faire si x = info [p] alors lc ←p; pt ← s; t← vrai
sinon si x < info [p] alors s ← p; p ← left[p]
sinon s ← p; p ← left [p]
si p = / alors lc ← /; iu pt ← s
fin
Lors d’une recherche dans un arbre de recherche binaire de n nœuds, le déplacement se
fait le long des chemins, le temps consacré sera alors proportionnel à la profondeur de
l’arbre avec une complexité de O(log2n), n = nombre de nœuds dans l’arbre.
4. Insertion dans un arbre binaire de recherche
Il s’agit de chercher l’indice du nœud up qui contient les critères x au sein d’un arbre T de
recherche binaire et d’y insérer ce nœud up dans le cas où il n’est pas trouvé.
Un algorithme possible peut avoir l’allure suivante :

Insertion (info[], left[], right[], rac, x, lc, pt)

début
Recherche (info[], left[], right[], root, x, lc, pt)
si lc = / alors info [k] ← x le nœud u p n’a pas été trouvé dans l’arbre, et
lc ← k soit k l’indice où il faut insérer ce nouveau nœud u p
left [k] ← /
right [k] ← /
si pt = / alors rac ← k
sinon si x < info [pt]
alors left [pt] ← k
sinon right [pt] ← k
fin
Soit, par exemple, l’arbre de recherche binaire :
10

6 20

dans lequel, il faut insérer 8,

Il n y a qu’un seul endroit possible où cette insertion peut s’effectuer et le nouvel arbre de
recherche binaire sera : 10

6 20

8
5. Suppression dans un arbre binaire de recherche
La manière dont le nœud uk doit être supprimé d’un arbre binaire de recherche T dépend
du nombre d’enfants de ce nœud uk :
a. si uk n’a pas d’enfants, uk est alors supprimé de l’arbre, et l’adresse de uk dans le nœud
parent de uk est remplacée par /,
b. si uk a 1 seul enfant ue, uk est supprimé de l’arbre, et l’adresse de uk dans
le nœud parent de uk est remplacée par celle de l’enfant unique ue,
c. si uk a 2 enfants, soit alors us le successeur en parcours in-ordre de uk
(ce qui signifie que us n’a pas d’enfant à sa gauche), il faut alors :
- écarter temporairement ce nœud successeur us (en appliquant le cas 1 ou le cas 2
ci-dessus),
- remplacer le nœud uk par us.
L’algorithme de suppression de nœud dans un arbre de recherche binaire peut donc être
efficacement spécifié comme 2 procédures :

- procédure SuppressionZeroOuUn de suppression du nœud uk qui est en info[k] et

qui n’a pas 2 enfants, où
pt est l’indice du parent du nœud uk (si pt = / alors uk est la racine),
ef est l’indice de l’enfant unique du nœud uk (si ef = / alors uk n’a pas d’enfant),

- procédure SuppressionDeux de suppression du nœud uk qui est en info[k] et

qui a 2 enfants, où
pt est l’indice du parent du nœud uk (si pt = / alors uk est la racine),
sc est l’indice du nœud successeur du nœud uk en parcours in-ordre,
psc est l’indice du parent de ce nœud successeur.
SuppressionZeroOuUn (info[], left[], right[], rac, k, pt)
début
si left [k] = / et right [k] = / alors ef ← /
sinon si left [k] ≠ / alors ef ← left [k]
sinon ef ← right [k]

si pt ≠ nil alors si left [pt] = k alors left [pt] ← ef

sinon right [pt] ← ef
sinon rac ← ef
fin
SuppressionDeux (info[], left[], right[], rac, k, pt)
début
p ← right [k] dans le parcours in-ordre, c’est dans ce sous-arbre que l’on peut trouver le successeur
s←k du nœud uk à supprimer
tant que left [p] ≠ / faire s ← p recherche du successeur ‘in-ordre’ du nœud u k,
p ← left [p] à la sortie de la boucle, p contiendra le successeur
sc ← p ‘in-ordre’ du nœud uk et
psc ← s s, le parent de ce successeur

SuppressionZeroOuUn (info[], left[], right[], rac, sc, psc) suppression temporaire du successeur
‘in-ordre’ du nœud uk
si pt ≠ nil alors si left [pt] = k alors left [pt] ← sc
sinon right [pt] ← sc
sinon rac ← sc

left [sc] ← left [k] les 2 anciens enfants du nœud uk deviennent les nouveaux enfants de son
right [sc] ← right [k] successeur
fin
Finalement, l’algorithme de suppression du nœud uk, présentant un critère donné x, dans
un arbre de recherche binaire peut alors formellement s’écrire :

Suppression (info[], left[], right[], rac, x)

début
Recherche (info[], left[], right[], rac, x, lc, pt)

si lc = / alors renvoyer «aucun nœud ne présente ce critère»

si right [lc] ≠ / et left [lc] ≠ /

alors SuppressionDeux (info[], left[], right[], rac, lc, pt)
sinon SuppressionZeroOuUn (info[], left[], right[], rac, lc, pt)

fin
6. Construction d’arbre
Tout arbre se construit par insertion de nœuds.
Tout arbre binaire ordonné se construit par insertion, migration et permutation de nœuds
en gardant l’arbre complet.
Par exemple, soit la maxipile : 60 dans laquelle le nœud 77 doit être inséré. Les étapes 3 sont :

50 55

22 30 44

 insertion : 60

50 55

22 30 44 77

 migration et permutation de 77 avec 55 : : 60

50 77

22 30 44 55

 migration et permutation de 77 avec 60 : : 77

50 60

22 30 44 55
5. CONCEPT D’ABSTRACTION

Implémentation du cahier des charges d’un TAD  écriture des algorithmes performants et
efficaces.

Performance et efficacité d’un algorithme  maîtrise de la complexité en temps et en espace

de cet algorithme.

Complexité en temps et en espace des algorithmes = fonction f(n1, n2, … ), où n1, n2, …
sont les tailles des données à traiter
supposées croître indéfiniment.

Complexité des algorithmes = élément critique pouvant servir d’outil d’évaluation,

de comparaison et de calcul du coût d’utilisation des algorithmes.

Comme la fonction f(n1, n2, … ) doit tenir compte de la distribution des données et d’autres
paramètres statistiques  de manière pratique, cette fonction f est comparée à
une fonction de référence via la fonction O( ), qui se lit «Ordre de».
6. ASPECTS GENERAUX ET BASIQUES DE TRI

Tri = opération vitale pour des processus de recherche et de traitement en masse exigeant
que les données à traiter soient triés (respect des spécifications, garantie des temps de
réponse et des performances acceptables).

2 Classes d’algorithmes de tri :

- tri par comparaison, classe qui ne tient pas compte de la structure des éléments à trier et
qui se base uniquement sur une relation d’ordre définie pour trier,
via des comparaisons, ces éléments,
 complexité minimale en temps de O (n log2n) pour trier n éléments,

- tri non comparatif, classe qui tient compte de la structure des éléments qui sont complexes

(tels que des chaînes de caractères, des arbres, des graphes,

des tableaux complexes, des éléments appartenant à un
ensemble ordonné fini) et qui utilise des propriétés de cette structure
dans le processus de tri
 complexité linéaire pour trier n éléments.
2 Méthodes de tri :
- tri interne : dans lequel toutes les données à trier sont en mémoire vive (RAM),
- tri externe : dans lequel les données à trier transitent ou résident, pendant l’opération
de tri, sur des supports externes (disques, bandes, …).
 Techniques (Algorithmes) de tri les plus connus :
- tri Bulle (tri simple), qui applique les comparaisons directement sur la structure de base
(tableau) où sont stockés les éléments à trier,
- tri de Base, qui utilise des sceaux (espèces de pile) pour contenir les éléments simples que
l’on trie pendant le processus, sceaux qui seront finalement concaténés pour
fournir la séquence triée voulue,
- tri Rapide (QuickSort), qui repose essentiellement sur une gestion des piles et utilise une
technique de «diviser pour régner»,
- tri Fusion, qui essaye d’améliorer certains problèmes de performances du tri Bulle et
du tri de Base en divisant les éléments à trier en plusieurs sous-séquences,
en triant chaque sous-séquence via n’importe quelle technique, et
en fusionnant les sous-séquences triées en une seule triée,
- tri Topologique, qui (ré)organise les éléments à trier dans un graphe G=(V,E)
- tri Vertical (HeapSort), qui organise les éléments à trier dans un arbre
(maxipile ou minipile),
- tri Lexicographique, qui se base sur les principes du tri de Base pour trier des éléments plus
complexes (tels que des chaînes de caractères).