Chapitre 1 Arbres de Recherche
Chapitre 1 Arbres de Recherche
Chapitre 1 Arbres de Recherche
ALGORITHMIQUE AVANCÉE
2019-2020
Prérequis Algo2-S3
Coefficient 2 3
2
Crédit 4 6
OBJECTIFS DU COURS
3
CONTENU DU COURS
I. Arbres de Recherche
III. NP-Complétude
4
Université Blida 1
Faculté des Sciences
Département d’Informatique
Master IL (Ingénierie Logiciel), SIR (Systèmes Informatiques et
Réseaux) & SSI (Sécurité des Systèmes d’Information)
Semestre 1
CHAPITRE I:
ARBRES DE RECHERCHE
2019-2020
Partie I: Introduction
TAS)
Introduction
Définitions et Terminologies
Topologie
Parcours
8
I. INTRODUCTION
Les arbres sont des structures de données fondamentales
9
I. INTRODUCTION
Leur usage est multiple, car il capte l’idée de hiérarchie; à
paragraphes…,
Livre
C1 C2 C3
S2.1.1 S2.1.2
I. INTRODUCTION
Leur usage est multiple, car il capte l’idée de hiérarchie; à
Hiérarchies de fichiers,
11
I. INTRODUCTION
Leur usage est multiple, car il capte l’idée de hiérarchie; à
Expressions Arithmétiques
L’expression A - (B + C * (D - E)) * F A *
se représente facilement par un arbre + F
où apparaît clairement la priorité des
B *
opérations:
C -
12
D E
I. DÉFINITIONS & TERMINOLOGIES
Un arbre est une structure de données (souvent dynamique)
représentant un ensemble de valeurs organisées
hiérarchiquement (non linéaire). Chaque valeur est stockée dans
un nœud. Les nœuds sont connectés entre eux par des arêtes
qui représentent des relations parent/fils.
Arêtes Nœuds
A
B C D
E F G H I
13
J K L
I. DÉFINITIONS & TERMINOLOGIES
Racine: est le nœud qui n'a
Racine
pas de prédécesseur (parent) et
A
possède zéro ou plusieurs fils. La Nœud interne
racine constitue la caractéristique B C D
d'un arbre.
E F G H I
Feuille : est un nœud qui n'a
pas de successeur (fils). Une
J K L
feuille est aussi appelée un nœud
externe. Feuilles
A-B-E
A-C J K L
A-D-F
A-D-G-J 16
…..
I. DÉFINITIONS & TERMINOLOGIES
Descendants d’un nœud :
sont tous les nœuds du sous arbre
de racine nœud. Dans l'exemple,
A
les descendants de D sont F, G,
H, I, J, K et L. B C D
Ascendants d’un nœud :
sont tous les nœuds se trouvant E F G H I
1 .…………………………………………….......
B C D
2 E F
………………..…………………………………………….......
G H I
19
3 …..…………..…………………………………………….......
J K L
I. DÉFINITIONS & TERMINOLOGIES
La profondeur (hauteur) d'un arbre : est le plus grand
niveau, c-à-d la distance entre la racine et la feuille la plus
lointaine. Dans l'exemple, la profondeur de l'arbre est égal à 3
Niveaux Racine
0 ………………………………....... A
1 .…………………………………………….......
B C D
2 E F
………………..…………………………………………….......
G H I
20
3 …..…………..…………………………………………….......
J K L
I. DÉFINITIONS & TERMINOLOGIES
Forêt : est un ensemble d'arbres.
B C D
E F H I
G L
J K
21
I. TYPOLOGIE
Les arbres sont classifiés selon:
leur degré m≥2: On trouve les arbres binaires (m = 2), ternaires
(m=3), quaternaires (m = 4) ,…….., m-aire (m>2).
la priorité d’ordre: entre le nœud père et ses fils, où :
le nœud père possède au moins une clé, les valeurs de sous
arbre gauche (droit resp.) de la clé sont strictement inférieures
(supérieures ou égales resp.) à la valeur de la clé. On parle ici
des arbres binaires de recherche (où chaque nœud possède
une clé) et des arbres m-aire de recherche (où chaque nœud
possède (m-1) clé),
la valeur du nœud père est supérieure (inférieure resp.) à la
22
valeur de ses fils. On parle ici du TASmax (TASmin)
I. TYPOLOGIE
Les arbres sont classifiés selon:
La propriété d’équilibrage: où les feuilles se situent aux
derniers niveaux. On trouve les arbres binaires de recherche
équilibrés (e.g: AVL, TAS, rouge et noir, 2-3-4, …..) et les arbre m-
aire de recherche équilibré (B-arbres, B-arbre*, B-Arbre+, …..)
23
I. PARCOURS
Le parcours d’un arbre consiste à passer par tous ses
nœuds.
Les parcours permettent d’effectuer tout un ensemble de
traitement sur les arbres.
On distingue deux types de parcours :
Des parcours en profondeur (depth-first) explorent
l'arbre branche par branche. Parmi lesquels: le Préordre,
l‘Inordre et le Postordre.
Des parcours en largeur (breadth-first) explorent
24
l'arbre niveau par niveau
I. PARCOURS
Dans un parcours en profondeur, on descend le plus
profondément possible dans l’arbre puis, une fois qu’une
feuille a été atteinte, on remonte pour explorer les autres
branches en commençant par la branche « la plus basse »
parmi celles non encore parcourues.
Le parcours en profondeur peut se faire en :
Préordre (Préfixe) : où on affiche la racine avant ses fils,
Postordre(Postfixe) : où on affiche les fils avant leur racine.
Inordre (Infixe) : où, dans le cas d’un arbre binaire, on affiche le
fils gauche avant sa racine et son frère droit,
25
PARTIE II:
ARBRES BINAIRES DE
RECHERCHE (ABR)
PLAN DE LA PARTIE II
Définitions
Parcours
Suppression
27
II. DÉFINITION
Un Arbre Binaire est un arbre de degré 2, c’est-à-dire que
chaque nœuds a au plus deux fils. Ainsi, le premier fils d'un nœud
est appelé Fils-Gauche (FG) et le deuxième fils est appelé Fils-
Droit (FD).
28
II. DÉFINITION
Un Arbre Binaire de Recherche (ABR) est un arbre
binaire ordonné tel que pour tout nœud « i »:
Toutes les valeurs du sous arbre gauche de « i » sont strictement
inférieures à la valeur de « i », et
29
II. PARCOURS PREORDRE
Le parcours préordre d’un arbre binaire R consiste à
visiter le nœud racine (R) ensuite parcourir récursivement
en préordre les sous arbres T1 (sous arbre gauche) puis T2
(sous arbre droit) ce qui donne : [ R , T1 , T2 ou RGD]
T1 T2
30
31
T1 T2
32
Propriété: Le parcours
inordre d’un ABR visite
les nœuds par ordre
croissant des clés. 33
T1 T2
34
35
Élément trouvé
3 10 33
55
8 38
52
II. OPÉRATION D’INSERTION
L'insertion d'une clé « x » se fait toujours au niveau d'une
39
II. OPÉRATION D’INSERTION
+ 25
20
15 59
5 27 71
3 10 25 33
55
RechercherPosition (25) 8
Rechercher (FD(20)) 52
Rechercher (FG(59))
soit « i » ce nœud
41
II. OPÉRATION DE SUPPRESSION
Cas 1: Suppression d'une feuille
Il suffit de l'enlever de l'arbre vu qu'elle n'a pas de fils.
1. Rechercher(8)
2. Libérer le nœud « i » 20
15 59
5 27 71
3 10 33
«i» 12 55
8 42
52
II. OPÉRATION DE SUPPRESSION
Cas 2: Suppression d'un nœud avec un fils
Il suffit de l'enlever de l'arbre en liant son père avec son fils.
1. Rechercher(10)
3. Libérer le nœud « i » 15 59
5 27 71
3 10 33
«i»
12 55 43
52
II. OPÉRATION DE SUPPRESSION
Cas 2: Suppression d'un nœud avec un fils
Il suffit de l'enlever de l'arbre en liant son père avec son fils.
1. Rechercher(27)
3. Libérer le nœud « i » 15 59
5 «i» 27 71
3 10 33
55
8 44
52
II. OPÉRATION DE SUPPRESSION
Cas 3: Suppression d'un nœud avec deux fils
Etape 1: On échange le nœud à supprimer avec son successeur
le plus proche (le nœud le plus à gauche du sous-arbre droit) ou
son plus proche prédécesseur (le nœud le plus à droite du
sous-arbre gauche). Cela permet de garder la propriété d’ordre
d‘ABR. 34
22 66
8 29 50 71
Le plus proche 56 70 81
17 25 prédécesseur
9 23 32 55 69
45
Le plus proche
successeur
II. OPÉRATION DE SUPPRESSION
Cas 3: Suppression d'un nœud avec deux fils
Etape 1 Cas A: On échange le nœud à supprimer avec son
successeur le plus proche (le nœud le plus à gauche ou le plus
petit du sous arbre droit)
Racine: 71
22 66
8 29 50 71
17 25 56 70 81
46
9 23 32 55 69
II. OPÉRATION DE SUPPRESSION
Cas 3: Suppression d'un nœud avec deux fils
Etape 1 Cas A: On échange le nœud à supprimer avec son
plus proche prédécesseur (le nœud le plus à droite ou le plus
grand du sous-arbre gauche).
Racine: 50
34
22 66
8 29 50 71
17 25 56 70 81
47
9 23 32 55 69
II. OPÉRATION DE SUPPRESSION
Cas 3: Suppression d'un nœud avec deux fils
Etape 2: on applique à nouveau la procédure de suppression qui
est maintenant une feuille ou un nœud avec un seul fils.
22 66
69
8 29 50 71
17 25 56 70 81
9 23 32 55 69
48
II. OPÉRATION DE SUPPRESSION
Cas 3: Suppression d'un nœud avec deux fils
Puis on applique à nouveau la procédure de suppression qui est
maintenant une feuille ou un nœud avec un seul fils.
22 66
56
8 29 50 71
56 70 81
17 25
55 69
9 23 32
49
II. OPÉRATION DE SUPPRESSION
En conclusion, pour supprimer le nœud « i » d’un ARB, on
rencontre une des situations suivantes :
«i»
Cas Action
FG FD
Feuille Nil Nil Libérer le nœud « i »
Avec un Nil ≠Nil Chaîner le père au fils de « i » (FG(i) ou
fils ≠Nil Nil FD(i)) ensuite libérer le nœud « i »
1. Rechercher le plus proche
Avec prédécesseur ou successeur de « i »,
deux ≠Nil ≠Nil soit « P ».
fils 2. Remplacer Info(i) par Info(P)
50
3. Supprimer le nœud « P »
PARTIE III:
ARBRES BINAIRES
ÉQUILIBRÉS
PLAN DE LA PARTIE III
AVL
Introduction
Définition
Techniques d’équilibrage
TAS
Définition
Implémentation 52
Exemples d’Application
III. AVL: INTRODUCTION
Intérêt des ABR équilibrés est de diminuer la complexité
temporelle des opérations de la recherche, de l’insertion
et de la suppression dans un ABR quelconque.
87 ?
53
+1 10 0 40
5 0
arbre déséquilibré
III. AVL: TECHNIQUES D’ÉQUILIBRAGE
L’opération d’équilibrage, appelée rotation, s’applique à
tous les ABR dans le but de pouvoir les rééquilibrer:
+2
0 ou -1
R P
Rotation droite
+1 ou 0 P 0 ou 1
R
Z
(hauteur
h/h-1)
X
Y (hauteur
h+1/h)
X
(hauteur
h/h)
Y Z
(hauteur (hauteur 58
(hauteur
h+1/h) h/h) h/h-1)
Déséquilibre gauche
III. AVL: TECHNIQUES D’ÉQUILIBRAGE
Rotation simple : Rotation gauche
-2 Rotation gauche 0 ou +1
R P
-1 ou 0 0 ou -1 R
P
X
(hauteur
h/h-1) Z
Y (hauteur
(hauteur Z X Y h+1/h)
h) (hauteur (hauteur h)
(hauteur h/h-1)
h+1/h) 59
Déséquilibre droit
III. AVL: TECHNIQUES D’ÉQUILIBRAGE
Rotation double : double rotation gauche-droite
D D
Q (h) P (h)
A A
(h) C B C D
(h) (h)
A B
B C (h)
60
((A, P, (B, Q, C)), R, D) → (((A, P, B), Q, C), R, D) → ((A, P, B), Q, (C, R, D))
III. AVL: TECHNIQUES D’ÉQUILIBRAGE
Rotation double : double rotation droite-gauche
C’est une rotation droite sur le sous arbre-droit du nœud R suivie
d’une rotation gauche sur le nœud R
Rotation droite Rotation gauche
-2 R R
Q
-2
0
P Q
A R P
+1
A (h)
(h) Q P
D B
(h)
A B C D
(h) (h)
B C C D
(h)
61
(A, R, ((B, Q, C), P, D)) → (A, R, (B, Q, (C, P, D))) → ((A, R, B), Q, (C, P, D))
III. AVL: OPERATIONS DE BASE
La recherche est identique à celui des ABR car les
arbres AVL sont avant tout des ABR équilibrés.
63
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7)
2 10 12 4 16 8 6 14 2 10 12 4 16 8 6 14
0 -2
2 2
-1
10
2 10 12 4 16 8 6 14
Rotation simple
2 -1 12 0
0
10 0 10
64
2 0 12 0
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7)
2 10 12 4 16 8 6 14 2 10 12 4 16 8 6 14
1
10 10 0
2 -1 12 0 2 -1 12 -1
4 0 4 0 16 0
65
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7 )
2 10 12 4 16 8 6 14 9 1 7
1
10
0
10
-1
2 -2 12
Rotation 4 0
12 -1
simple
-1
4 16 0
0 2 8 0 16 0
66
8 0
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7)
2 10 12 4 16 8 6 14 9 1 7
1
10
-1
4 -1 12
0 2 8 1 16 0
67
6 0
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7)
2 10 12 4 16 8 6 14 9 1 7
1
10 0 10
4 12 -2 4 -1 14 0
-1
Rotation
double
0
2 8 1 16 1 2 8 1 12 16
0
0 0
6 14 0 6 0 68
0
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7)
2 10 12 4 16 8 6 14 9 1 7
2
10
10
4 -1 14 0
4 14 Insertion
du 7 1
2 8 1 12 16
0 0
2 8 12 16
0
1 6 -1 9 0
1 6 9
7 69
0
Nœud inséré
III. AVL: INSERTION
Exemple: soit la série de nombres à insérer dans un
arbre AVL (2 10 12 4 16 8 6 14 9 1 7)
2 10 12 4 16 8 6 14 9 1 7
2 0
10 8
4 -1 14 0
Rotation 0 -1
4 10
double
1
2 8 1 12 16
0 0
14 0
1
2 6 -1 9 0
0
1 6 -1 9 0
0 12 16 700
1 7 0 0
7
0 Nœud inséré
III. AVL: INSERTION
Après insertion à gauche Avant Après insertion à droite
+1 R 0 R -1 R
h+1 h h h h h+1
+2 R Cas A +1 R 0 R
0 -1 R -2 Cas B
R R
72
+2 R Cas A
III. AVL: INSERTION
h+2 h
Avant
+1 R
0 P
h
+2 R h h +2 R
+1 P -1 P
h h
h+1 h h h+1
0 P
h
h h
-2 R -2 R
+1 P -1 P
h h
h+1 h h h
inférieur ou supérieur.
rééquilibrer.
III. AVL: SUPPRESSION
S’il y a déséquilibre, la rotation appliquée peut diminuer
76
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 10:
Remplacer par
0 0
8 le successeur 8
0 -1 0 -1
4 10 4 12
14 0 14 -1
1
2 6 -1 9 0 1
2 6 -1 9 0
0
1 12 16 0 0
1 16 0
7 0 0 7 0
77
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 8:
Remplacer par
0 0
8 le successeur 9
0 -1 0 -2
4 12 4 12
14 -1 14 -1
1
2 6 -1 9 0 1
2 6 -1
0
1 16 0 0
1 16 0
7 0
7 0
78
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 8:
1
0
9 9
RSG
0 0
4
0 -2 4 14
12
0 0
14 -1 1
2 6 12 16
1
2 6 -1
-1
0
1 16 0
0
1 7 0
7 0
79
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 12 puis 16:
1
9 9
+2
0 0
4 14 4
0
14
0
0 0
1
2 6 -1 12 16 1
2 6 -1
0
1 7 0 0
1 7 0
80
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 12 puis 16:
+2
9 -1
4
RSD
0 0
4 14 1
2 1
9
1
2 6 -1
1 0 6 -1
14 0
0
0
1 7 0 7
81
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 30:
-1 -1
50 50
+1
Remplacer par +2 +1
30 100
+1
le successeur 40 100
0
-1 -1
-1
10 40 80 +1 200 -1
10 80 +1 200
+1 0
0
0 0
0
20 70 90 300 0
20 70 90 300
+1
0
60 82
60 0
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 30:
-1
50 -2
50
+2 +1
RDG-D
40 100 0 +1
20 100
-1 0
-1
10 80 +1 200 0
-1
10 40 80 +1 200
+1 0
0
0
20 70 90 300
70 90 0 300 0
+1
0
60 83
0
60
III. AVL: SUPPRESSION
Exemple: soit l’arbre suivant. Donner le résultat après la
suppression de 30:
-2 0
50 80
RDD-G
0 +1 0
20 100 50 100
-1
0 0
-1 -1
0 +1
10 40 80 +1 200 20 70 90 200
0
70 90 0 300 0
10 40 60 300
0
+1
0 0 0
84
0
60
PLAN DE LA PARTIE III
AVL
TAS
Définition
Implémentation
Exemples d’Application
85
III.TAS: DÉFINITION
Propriété d’ordre :
5 6
15 9 7 20
87
16 25 14 12 11 8
Maximum
III.TAS: DÉFINITION
Exemple d’un TASmax
35 26
15 19 17 20
88
1 13 14 12 11 8
Minimum
III.TAS: INSERTION
Pour insérer une valeur « v » dans un TASmin [ou
TASmax]
6
9
15 10 7 20
16 25 14 12 11 8
90
III.TAS: INSERTION
Exemple: Soit le TASmin suivant.
Insertion 5
6
9
15 10 7 20
16 25 14 12 11 8 5
91
III.TAS: INSERTION
Exemple: Soit le TASmin suivant.
Insertion 17
5
9
15 10 7 6
16 25 14 12 11 8 20 17
92
III.TAS: INSERTION
Exemple: Soit le TASmin suivant.
Insertion 3
5
9
15 10 7 6
16 25 14 12 11 8 20 17
93
3
III.TAS: INSERTION
Exemple: Soit le TASmin suivant.
Insertion 18
5
4
9 10 7 6
15 25 14 12 11 8 20 17
94
16 18
III.TAS: INSERTION
Exercice: Construire un TASmin et un TASmax à partir
des valeurs suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
95
III.TAS: INSERTION
Solution: Construire un TASmin à partir des valeurs
suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
20 15 10 10
15 20 20 19
10 15 15
35 19 35 20 13
10
3
19 13
5 10
5
35 20 15 5
19 19 10
20 15 13
96
35 12 35 20 15 13
3
INSERTION
Solution: Construire un TASmin à partir des valeurs
suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
3 3
5 10 5 10
12 20 15 13 12 7 15 13
35 19 35 19
7 20 16 40 25 38
97
III.TAS: INSERTION
Solution: Construire un TASmax à partir des valeurs
suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
35
20
15 10 20 10
35
15 19
13
98
III.TAS: INSERTION
Solution: Construire un TASmax à partir des valeurs
suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
35
20 13
15 19
10 5
3 7 40
12 16 40
20 35
15 19 13 5 99
3 12 7 16 10
25
III.TAS: INSERTION
Solution: Construire un TASmax à partir des valeurs
suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
40
20 35
15 19 25 5
3 12 7 16 10
13 38
100
III.TAS: INSERTION
Solution: Construire un TASmax à partir des valeurs
suivantes:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
40
20 38
15 19 25 35
3 12 7 16 10
13 5
101
III.TAS: RECHERCHE
niveau)
102
III.TAS: RECHERCHE
Exemple: Soit le TASmin suivant.
7?
6
9
15 10 7 20
16 25 14 12 11 8
103
La valeur existe, fin de recherche
III.TAS: RECHERCHE
Exemple: Soit le TASmin suivant.
8?
6
9
15 10 7 20
16 25 14 12 11 8
104
La valeur existe, fin de recherche
III.TAS: RECHERCHE
Exemple: Soit le TASmin suivant.
3?
6
9
15 10 7 20
16 25 14 12 11 8
105
La valeur n’existe pas , fin de recherche
III.TAS: RECHERCHE
Exemple: Soit le TASmin suivant.
30 ?
6
9
15 10 7 20
16 25 14 12 11 8
106
Fin de recherche, la valeur n’existe pas
III.TAS: SUPPRESSION
Pour supprimer une valeur « v » dans un TASmin [ou
TASmax]
père.
6
9
15 10 7 20
16 25 14 12 11 8
109
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 9.
6
9
15 10 7 20
16 25 14 12 11 8
110
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 9, 16.
6
8
15 10 7 20
16 25 14 12 11
111
SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 16.
6
8
15 10 7 20
11 25 14 12
112
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 6.
6
8
11 10 7 20
15 25 14 12
113
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 6.
12
8
11 10 7 20
15 25 14
114
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 4.
7
8
11 10 12 20
15 25 14
115
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 4.
14
7
8
11 10 12 20
15 25
116
III.TAS: SUPPRESSION
Exemple: Soit le TASmin suivant.
Suppression de 4.
12
8
11 10 14 20
15 25
117
III.TAS: IMPLÉMENTATION
Un TAS se représente naturellement par un tableau:
Les sommets sont numérotés par un parcours en largeur, de
gauche à droite.
15 9 7 20
8 9
16 25 14 12 11 8
10 11 12 13
118
1 2 3 4 5 6 7 8 9 10 11 12 13
4 5 6 15 9 7 20 16 25 14 12 11 8
III.TAS: IMPLÉMENTATION
On parle ici de la représentation statique
séquentielle d’un arbre binaire
La case 0 est vide
Indice(racine)=1
Indice(FG)=2*Indice(Père)
Indice(FD)=2*Indice(Père)+1
0 1 2 3 4 5 6 7 8 9 10 11 12 13
?? 4 5 6 15 9 7 20 16 25 14 12 11 8
119
III.TAS: EXEMPLES D’APPLICATION
Les TAS sont très utiles entre autre pour le tri et pour
120
EXEMPLE D’APPLICATION
TRI PAR TAS
Étant donné un tableau d’entiers T (n: sa taille), dire
Exemple:
20 15 10 35 19 13 5 3 12 7 16 40 25 38
121
III.TAS: EXEMPLE D’APPLICATION
TRI PAR TAS
20 15 10 35 19 13 5 3 12 7 16 40 25 38
5 10
12 7 15 13
35 19 20 16 40 25 38
122
III.TAS: EXEMPLE D’APPLICATION
TRI PAR TAS
5 10
12 7 15 13 5
35 19 7 10
20 16 40 25 38
12 16 15 13
35 19 20 38 40 25
3 5 123
III.TAS: EXEMPLE D’APPLICATION
TRI PAR TAS
12 10
19 16 15 13
10
35 25 20 38 40
12 13
19 16 15 40
35 25 20 38
3 5 7 10 124
III.TAS: EXEMPLE D’APPLICATION
TRI PAR TAS
16 15
16 13
19 20 38 40
19 20 15 40
35 25
35 25 38
15
16 25
19 20 38 40
35
125
3 5 7 10 12 13 15
III.TAS: EXEMPLE D’APPLICATION
TRI PAR TAS
16 19
19 25 20 25
35 20 38 40 35 40 38
35 25 20
38 40 35 40 35 25
38 38 40
38
40
40
126
3 5 7 10 12 13 15 16 19 20 25 35 38 40
III.TAS: EXEMPLE D’APPLICATION
IMPLÉMENTATION D’UNE FILE AVEC PRIORITÉ
Une file d’attente avec priorité est une collection d’éléments
dans laquelle l’ajout ne se fait pas toujours à la queue (fin).
Tout nouvel élément est ajouté dans la file, selon sa
priorité.
Le retrait se fait toujours du début.
Dans une file avec priorité, un élément prioritaire prendra la
tête de la file même s’il arrive le dernier.
L’implémentation de ces files d’attente peut être par tableau
(décalage ou circulaire) ou LLC ordonnée, mais
127
l’implémentation la plus efficace et la plus répandue utilise les
TAS.