View
110
Download
4
Category
Preview:
Citation preview
LOGO
Algorithmique et Structures de
données évoluées
Algorithmique et Structures de
données évoluées
Responsable du coursMlle Amina GHRAB : amina.ghrab@live.fr
1ère année IAG2009 - 2010
Institut Supérieur de Gestion de Tunis
Objectifs
Être capable de choisir la structure adéquate à chaque problème.
Savoir manipuler les structures arborescentes;
Pouvoir implémenter les structures de données arborescentes;
Connaître les avantages et les inconvénients de chaque structure arborescente;
Connaitre l’utilité des structures de données arborescentes;
L’étudiant devra :
2
Références
Michel Divay : Algorithmes et structures de données génériques;
Abdelali Guerid, Pierre Breguet, Henri Röthlisberger : Algorithmes et structures de données avec C++ et Java;
XU Philippe, VENANT Antoine: Arbres binaires de recherche;
Cours Mme Nahla Ben Amor : Algorithmes et structures de données , http://isgprog2.ifrance.com/
3
Plan
4
Les arbres binaires de recherche2
Exercices33
Définition et terminologie
Algorithmes de parcours
Définition
Opérations sur les ABRs
Structures de données arborescentes1
Les AVLs
Définition et terminologie(1)
5
Une arborescence est une structure en forme d'arbre qui permet d'organiser les données en mémoire ou sur disque, de manière logique et hiérarchisée.
Dictionnaire arborescent;
Organisation d’un répertoire;
Définition et terminologie(2)
Père :prédécesseur direct d’un nœud;
Fils: successeur direct d’un nœud;
Feuille: un nœud sans fils;
Degré d’un nœud: le nombre de ces fils;
Génération: les nœuds d’un même niveau;
Branche: un chemin qui commence par la racine et se termine par une feuille;
Sous-arbre: un nœud accompagné de toute sa descendance;
6
Définition et terminologie(3)
Taille: le nombre de nœud de l’arbre;
Profondeur: le nombre de nœud de la branche la plus longue;
Ordre d’un arbre: le degré maximum parmi tous ses nœuds;
Arbre binaire: un arbre d’ordre 2;
Arbre binaire complet: chaque nœud autre qu’une feuille admet deux descendants et toutes les feuilles sont au même niveau;
Arbre binaire dégénéré: tous les nœuds de cet arbre ont au plus un descendant.
7
Définition et terminologie(3)
IllustrationA
E
DB
L
F
N
G
MK
Taille:?Profondeur:?Ordre:?
Taille:10Profondeur:4Ordre:2
8
Définition et terminologie(4)
A
E
DB
L
C
H
F
N
G
MK
9
Parcours en largeurParcours en profondeur
Algorithmes de parcours
10
Algorithmes de parcours
A
E
DB
L
C
H
F
N
G
MK
1
2 43
65
8
7
11109 12
A,B,C,D,E,F
G,H,K,L,M,N
Largeur
11
Algorithmes de parcours
A
E
DB
L
C
H
F
N
G
MK
1
2
3
4 5 6
7 8
9 10
11 12
A,B,E,H,K,L,C,D
F,G,M,N
Profondeur
12
Algorithmes de parcours
Parcours en profondeur
parcours_profond(AB:arbre)DebutSi nonVide(AB) alors Afficher Racine(AB) parcours_profond(SAG(AB)) parcours_profond(SAD(AB))Fin siFin
13
Algorithmes de parcours
TAF:
Ecrire l’algorithme du parcours en profondeur pour un arbre n-aire;
Ecrire l’algorithme du parcours en largeur
14
Plan
15
Les arbres binaires de recherche2
Exercices(Quiz)33
Définition et terminologie
Algorithmes de parcours
Définition
Operations sur les ABRs
Structures de données arborescentes1
Les AVLs
Définition
Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque nœud possède une clé d’identification, et tel que chaque nœud du sous-arbre gauche a une clé inférieure à celle du nœud considéré, et que chaque nœud du sous-arbre droit a une clé supérieure à celle-ci.
Utiles pour ranger des valeurs ordonnées;
permettent de rechercher et de trouver un nœud de façon rapide et simple.
16
Opèrations sur les ABRs: insertion
Exemple:44,77,55,22,33
Insérer 44 44 Insérer 77
55
Insérer 5544
Insérer 22
77
Insérer 3322
44
77
55
44
77
22
55
44
77
33
17
0 fils1 seul fils
Opérations sur les ABRs: Suppression
2 fils
18
Opérations sur les ABRs: Suppression 1er cas: le nœud a 0 fils
On supprime le nœud et on remplace son adresse par NULL
Supprimer 33
22
55
44
77
33
22
19
Opérations sur les ABRs: Suppression 2éme cas: le nœud a un seul fils
On supprime le nœud et on remplace son adresse dans son père par l’adresse de son fils
Supprimer 22
22
55
44
77
33
33
20
Opérations sur les ABRs: Suppression 3eme cas: Le nœud a deux fils
o On supprime N et on le remplace par l’élément maximal de son sous arbre gauche puis on le supprime;
o On supprime N et on le remplace par l’élément minimal de son sous arbre droit puis on le supprime
22
55
44
77
3312
Supprimer 22
147
14
55
44
77
3312
7
21
Opérations sur les ABRs: Suppression
Algorithme
Delete(n:nœud)
Debut
n,q:nœud,racine:noeud;test,Supp:boolean;
Si
(n.compareto(ref-racine)==0;
Supp=vrai;test=vrai;
Fin si
Tant que(racine<>null)&&(!test)
Si
(n.compareto(racine)<0) alors q=racine;racine=racine.fils-gauche;
Sinon (si n.compareto(racine)>0) q=racine;racine=racine.fils-droit fin si;
Sinon test=vrai;
Fin si
22
Opérations sur les ABRs: Suppression
Si test=vrai alors
Si((racine.fils-droit<>null)&&(racine.fils-gauche<>null))
alors
Z=chercherMin(racine.fils-droit)
Racine=z;
Z=supprimermin(racine.fils-droit);
Fin si
Fin si
Fin tant que
23
Opérations sur les ABRs: Suppression
TAF
Terminer le traitement du premier et du deuxième cas de la suppression dans un arbre de recherche.
24
ABRs
Très éfficaces pour la recherche, les insertions et les suppressions;
24
Les AVLs
ABR Dégénéré !!!!!!!
Complexité est en O(n)
Il faut les équilibrer
25
Les AVLs
26
Un AVL est un arbre binaire de recherche tel que, pour tout nœud de l’arbre, les hauteurs des sous-arbres gauches et des sous-arbres droits diffèrent d’au plus de 1;
Remédier au problème de déséquilibre dans les arbres binaires de recherche;
Ce sont des arbres de recherche équilibrés dont les opérations de recherche, d'insertion et de suppression ne sont pas coûteuses en terme de complexité.
Les AVLs
FG Info BAL FD
BAL=hauteur(SAD)-hauteur(SAG)
BAL =0BAL=1BAL=-1
Principe
Nœud
28
AVLs
22
55
44
77
33
56
12 44
1
0 -1
0 0 0
0
22
55
44
77
33
56
12 44
-1
-2 -1
2 0 0
0
14
13-1
0
1
29
Questions
30
Recommended