Les types abstraits de données (TAD)
LES ARBRES
LES STRUCTURES NON LINÉAIRES
Les types abstraits de données (TAD)
LES GRAPHES …
Les Graphes
• Un graphe est un couple G = (S,A) où :
• S est un ensemble fini non vide dont les
éléments sont appelés sommets
• A est un ensemble de paires de sommets
appelées arêtes.
• Si a = {x,y} est une arête, on note aussi a
= xy.
• On dit alors que x et y sont voisins ou
adjacents dans le graphe G, on a xy = yx.
3
Les Graphes
• L’ordre : d’un graphe G = (S,A) est le cardinal de S ;
• La taille : d’un graphe G = (S,A) est le cardinal de A ;
• Le degré : d’un sommet x de G est le nombre de ses voisins
ce degré vaut 0 si le sommet est isolé.
4
Les Graphes
• Un graphe peut être orienté : une arête est
alors un couple (x,y) et non une paire {x,y}
de sommets.
• Un graphe peut être valué aux sommets ou
aux arêtes : à chaque sommet ou arête, est
associé une valeur qui permet de définir une
valuation (application de l’ensemble des
sommets ou arêtes vers N).
• Un graphe peut être coloré aux sommets ou
aux arêtes : à chaque sommet ou arête, est
associée une couleur.
5
Les Graphes
• Représentation : Matrice d’incidences
Soit G(X,E) un graphe,
X : {} sommets d’indice {1,2,3,…,n}
E : {} arcs {(1,2),(1,3),(2,2),(2,4),(3,2),…,(5,3),… }
Représentation du graphe par la matrice d’adjacence :
Graphe = Enreg 1 2 3 4 5
Sommet a b c d e
Sommet:tableau[1..Max] de Valeur
m:tableau[1..Max,1..Max] de Booléenne
n:entier j
1 2 3 4 5
FinEnreg i
1 F V F F F
a c e
2 F V V V F
3 F F F V V
4 F F V F F b d
5 F F F F F
6
Les Graphes
• Représentation : Liste chaînée
Graphe : ^sommet
G @
sommet = enreg
A
@ @ x y
val : valeur @ @ @ Ø
succ : ^Successeur (lst_Succ) B
A
next : ^sommet (Graphe)
B
@ @ z
Fenreg
@ Ø
C D
C
@ Ø
lst_Succ : ^Successeur D
Ø @ x
@ Ø
Successeur = enreg
next_som : ^sommet (Graphe)
next_succ : ^ Successeur (lst_Succ)
Fenreg 7
Les types abstraits de données (TAD)
LES ARBRES …
Définition
• Arbre = structure non linéaire
• Tout élément possède 0 ou plusieurs
successeurs
• 1 seul élément avec 0 prédécesseur
• Les autres éléments possèdent
chacun 1 seul prédécesseur
Terminologie
• Elément : Nœud
• 1 unique relation : PÈRE – FILS
• Racine de l’arbre : l’unique nœud
sans père
• Feuille : nœud sans fils
• Nœud interne : nœud avec 1 père
et au moins 1 fils
Terminologie
• Degré d’un nœud : nombre de ses fils
• Degré d’un arbre : Max (Degrés de ses nœuds)
• Niveau d’un nœud :
– Niveau de la racine = 1
– Soit i le niveau d’un nœud
ses fils ont le niveau (i+1)
• Hauteur d’un arbre :
– Max (niveaux de ses nœuds)
Terminologie
Exemple 1 Exemple 2
• Degré de l’arbre : 2 • Degré de l’arbre : 3
• Hauteur de l’arbre : 5 • Hauteur de l’arbre : 3
1 1
2
2
3
3
4
5
Terminologie
Exemple 1 Exemple 2
• Degré de l’arbre : 2 • Degré de l’arbre : 3
• Hauteur de l’arbre : 5 • Hauteur de l’arbre : 3
Racine de l’arbre
Feuilles de l’arbre
Terminologie
Exemple 1 Exemple 2
• Degré de l’arbre : 2 • Degré de l’arbre : 3
• Hauteur de l’arbre : 5 • Hauteur de l’arbre : 3
Nœuds interne
Représentation
Représentation Dynamique
Arbre = ^nœud
A
1
noeud = enreg
val : valeur
lv : Arbre lien vertical
lh : Arbre lien horizontale
fenreg
Représentation
Représentation Dynamique
Exemple 1
A
20
5 25
21 28
3 12
8 13
6
Représentation
Représentation Dynamique
Exemple 2
A
1
2 3 4
7 8 9
5 6
Les types abstraits de données (TAD)
LES ARBRES BINAIRES
AB : Définition
• Dans un arbre binaire tout nœud a au
maximum 2 fils.
• Un arbre binaire est défini
récursivement par :
– l’arbre vide (^) est un arbre
binaire
– l’arbre A = <A1,x,A2> est un arbre
binaire si et seulement si A1 et
A2 sont des arbres binaires.
AB : Définition
• On distingue 2 type de fils :
– Fils gauche : fg
– Fils droit : fd
(E)
Exemples :
A
(A) (B) (C) (D)
A A A A B
C B B C D E
AB : Définition
Exemples :
• Une expressions arithmétiques
-
(2 + 4) * 3 - 2 * 2
+ 3
2 4
Arbres binaires particuliers
• Arbre binaire étendu = Arbre (D)
binaire où chaque nœud possède (D)
A
0 ou 2 fils, A C
B C F G
(D)
• Arbre binaire complet = Arbre
A
binaire étendu où toutes les (D)
feuilles sont au même niveau,
A B C
B C D E F G
AB : Représentation
Représentation Dynamique
AB = ^nœud
A
1
noeud = enreg
val : valeur
fg : AB fils gauche
fd : AB fils droit
fenreg
AB : Représentation
Représentation Dynamique
Exemple 1
A
20
5 25
3 12 21 28
8 13
6
AB : Représentation
Représentation Dynamique
Exemple 2
A
10
8 5
3 15 4
8
AB : Parcours
Principe :
Exemple 2
• Recherche !!! Père 10
• Calcul !!! fils gauche 8 5
• Décision !!! fils droit 3 15 4
20
Père fils gauche fils gauche
fils gauche Père fils droit
fils droit fils droit Père
Préfixé Infixé Postfixé
AB : Parcours en Préfixé
Parcours en Préfixé :
Exemple 2
Père Père
(1) 10
fils gauche fils droit
fils droit fils gauche (2) 8 (6) 5
(3) 3 (4) 15 4 (7)
(5) 20
10 8 3 15 20 5 4
AB : Parcours en Préfixé
Parcours en Préfixé :
Père Père
Prefixe(A : AB)
fils gauche fils droit
Début
fils droit fils gauche Si A <> NIL Alors
Traiter (A^.val)
Prefixe (A^.fg)
Prefixe (A^.fd)
Fsi
Fin
AB : Parcours en Infixé
Parcours en Infixé :
Exemple 2
fils gauche fils droit
(5) 10
Père Père
fils droit fils gauche (2) 8 (7) 5
(1) 3 (4) 15 4 (6)
(3) 20
3 8 20 15 10 4 5
AB : Parcours en Infixé
Parcours en Infixé :
fils gauche fils droit
Infixe(A : AB)
Père Père
Début
fils droit fils gauche Si A <> NIL Alors
Infixe (A^.fg)
Traiter (A^.val)
Infixe (A^.fd)
Fsi
Fin
AB : Parcours en Postfixé
Parcours en Postfixé :
Exemple 2
fils gauche fils droit
(7) 10
fils droit fils gauche
Père Père (4) 8 (6) 5
(1) 3 (3) 15 4 (5)
(2) 20
3 20 15 8 4 5 10
AB : Parcours en Postfixé
Parcours en Postfixé :
fils gauche fils droit
Postfixe(A : AB)
fils droit fils gauche
Début
Père Père Si A <> NIL Alors
Postfixe (A^.fg)
Postfixe (A^.fd)
Traiter (A^.val)
Fsi
Fin
AB : Autres opérations
Exemple 2
Insertion A
10
10
Suppression
8 5
Recherche 8 5
3 15 4 3 15 4
8 20
l
3 4 5 8 10 15 20
AB : Autres opérations
Exemple 2
Insertion A
10
10
Suppression
4 20
Recherche 4 15
3 8 20 3 8 15
Dichotomie !!! 5 5
l
3 4 5 8 10 15 20
Les types abstraits de données (TAD)
ARBRE BINAIRE DE RECHERCHE
ABR : Définition
• Un ABR est arbre binaire,
• Un Arbre Binaire de Recherche est
défini récursivement par :
– l’arbre vide (^) est un ABR,
– l’arbre A = <A1,x,A2> est un ABR si
et seulement si :
– A1 et A2 sont des ABR
– A1 ≤ x < A2
ABR : Exemples
(A) (B) (C)
5 7 4
3 7 3 3 5
4 6 5 6 7
(ABR) 4 6 (ABR)
(ABR)
ABR : Exemples - Ordre
Parcours en Infixé d’un ABR :
(A) (B)
fils gauche fils droit
(3) 5 (5) 7
Père Père
fils droit fils gauche (1) 3 7 (5) (1) 3
(2) 4 6 (4) (3) 5
(2) 4 6 (4)
Liste Triée en ordre croissant (décroissant)
ABR : Représentation
Représentation Dynamique
ABR = ^nœud
A
1
noeud = enreg
val : valeur
fg : ABR fils gauche
fd : ABR fils droit
fenreg
ABR : Opération - Recherche
la Recherche d’un élément x dans un ABR A !!!
(A)
(5) 10
(2) 6 (7) 13
(1) 3 (4) 9 11 (6)
Dichotomie !!! (3) 7
3 6 7 9 10 11 13
ABR : Opération - Recherche
Recherche_ABR (A:ABR; x:valeur; var ptx:ABR)
Début
si A = NIL Alors
ptx := NIL
sinon
si A^.val = x alors
ptx := A
sinon
si x < A^.val Alors
Recherche_ABR(A^.fg,x,ptx)
sinon
Recherche_ABR(A^.fd,x,ptx)
fsi
fsi
fsi
Fin
ABR : Opération - Insertion
L’insertion d’un élément x dans un ABR A !!!
(A)
Insérer 8 10
6 13
Insérer 12
3 9 11
7 12
8
ABR : Opération - Insertion
Insère_ABR (var A:ABR; x:valeur)
Début
si A = NIL Alors
créer( A )
A^.val := x
A^.fg := NIL
A^.fd := NIL
sinon
si x ≤ A^.val Alors
Insère_ABR(A^.fg, x)
sinon
Insère_ABR(A^.fd, x)
fsi
fsi
Fin
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 20
5 25
3 12 21 28
8 13
6
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 20
Supprimer 12 5 25
3 12 21 28
6
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 20
Supprimer 12 5 25
Supprimer 20
3 8 21 28
Remplacer 20 par soit :
6
la plus grande valeur sous son fils gauche
la plus petite valeur sous son fils droit
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 8
Supprimer 12 5 25
Supprimer 20
3 8 21 28
6
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 8
Supprimer 12 5 25
Supprimer 20
3 6 21 28
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 21
Supprimer 12 5 25
Supprimer 20
3 8 21 28
6
ABR : Opération - Suppression
La suppression d’un élément x dans un ABR A !!!
(A)
Supprimer 13 21
Supprimer 12 5 25
Supprimer 20
3 8 28
6
ABR : Opération - Suppression
Supprime_ABR (var A:ABR; x:valeur)
Début
si A <> NIL Alors
si A^.val = x Alors
delete_noeud(A)
sinon
si x < A^.val Alors
Supprime_ABR(A^.fg, x)
sinon
Supprime_ABR(A^.fd, x)
fsi
fsi
fsi
Fin
ABR : Opération - Suppression
Delete_noeud (var A:ABR)
Début
p := A
si A^.fg = NIL Alors
A := A^.fd
liberer(p)
sinon
si A^.fd = NIL Alors
A := A^.fg
liberer(p)
sinon
upd_noeud(A, A^.fg)
fsi
fsi
Fin
ABR : Opération - Suppression
upd_noeud (var A:ABR; ptrF:ABR)
Debut
si ptrF^.fd <> NIL Alors
upd_noeud(A, ptrF^.fd)
sinon
A^.val := ptrF^.val
p := ptrF
ptrF := ptrF^.fg
liberer(p)
fsi
Fin
ABR : la recherche est-elle optimale?
Exemple 1
1 2 3 4 5 6 7
1
2 Arbre Dégénéré
3
5
Recherche lente
6
7
Recherche Séquentielle
ABR : la recherche est-elle optimale?
Exemple 1
1 2 3 4 5 6 7
1
5
ABR de 2 Arbre Dégénéré
hauteur 3
2 7
minimale
4
1 4 6
5
3
6
7
Optimisation sur les ABR
Arbres Equilibrés