Upload
pavel
View
40
Download
0
Embed Size (px)
DESCRIPTION
COURS DE PROGRAMMATION ORIENTEE OBJET :. Types Abstraits de Données TAD. Types Abstraits de Données(TAD). Les TAD sont nés des problèmes liés au développement d’applications: maîtriser la complexité -> modularité - PowerPoint PPT Presentation
Citation preview
1
COURS DE PROGRAMMATION ORIENTEE OBJET :
Types Abstraits de DonnéesTAD
2
Types Abstraits de Données(TAD) Les TAD sont nés des problèmes liés au
développement d’applications:– maîtriser la complexité -> modularité– réutiliser du code existant -> fournir des
solutions pour des familles de problèmes (bibliothèques à usage générale).
– traiter des problèmes de haut niveau en s’affranchissant des problèmes de niveau inférieur déjà résolus -> abstraction des données.
3
Les principes de conception
– Modularité
– Abstraction des données
– Encapsulation
Types Abstraits de Données(TAD)
4
Idée directrice– Parallèle avec les types primitifs
• Le type int : représente un entier,• est fourni avec des opérations : + - /
* %.• Il n’est pas nécessaire de connaître la
représentation interne ou les algorithmes de ces opérations pour les utiliser.
Types Abstraits de Données(TAD)
5
Idée directrice– Faire de même pour des types plus
complexes indépendamment d’un langage de programmation
• Créer un type, dont la représentation interne est cachée.
• Offrir les opérations de haut niveau nécessaires.
Types Abstraits de Données(TAD)
6
Définition Un TAD est • un type de données • l’ensemble des opérations
permettant de gérer ces donnéesles détails de l’implantation restant
cachés
Types Abstraits de Données(TAD)
7
Exemple : le TAD listeType LISTEUtilise Element, Boolean, PlaceLes opérations :
– Constructeurs• Creer: =>Liste (crée une liste vide)
• Ajouter: Element × Liste => Liste
• AjouterPos: Element × Liste × Place => Liste
Types Abstraits de Données(TAD)
8
Exemple : le TAD liste– Selecteurs
• tete : Liste => Element• queue : Liste=>Liste• longueur : Liste=> Element• estVide : Liste => Boolean
– Modificateurs• Enlever : Liste × Place => Liste
• Modifier : Liste × Place × Element => Liste
Types Abstraits de Données(TAD)
9
Réalisation d’un TADDéfinition : Une structure de données est une construction du langage de programmation permettant de représenter un TAD.
Exemple : On peut utiliser comme structure de données un tableau pour implanter une liste.
Types Abstraits de Données(TAD)
10
Intégration du principe de l’encapsulation:On pourra construire plusieurs structures de données pour un même TAD.
Un TAD peut être vu comme un fournisseur de services sur un sujet précis (vecteurs, listes…) concrétisé par une structure de données appropriée
Types Abstraits de Données(TAD)
11
Réalisation d’un TAD en Java
Java fournit les mécanismes suivants:• Classes• Exceptions• Généricité
Types Abstraits de Données(TAD)
12
Réalisation d’un TAD en Java– Classes
Masquage de la structure interne du TAD :– Visibilité privée pour les attributs de la classe
décrivant la structure de donnée choisie.– Visibilité publique pour les méthodes.
– ExceptionsPermettent une gestion de erreurs pouvant survenir lors de l’utilisation d’un TAD.
Types Abstraits de Données(TAD)
13
Réalisation d’un TAD en Java– Généricité
• Avant la JDK5.0, la généricité consiste à écrire du code en utilisant la classe Object.Inconvénient : possibilité d’ajouter à la structure des éléments de différents types -> structures de données non homogènes.
• Depuis la JDK5.0, Java propose une gestion de types « génériques » permettant de contrôler le type de éléments insérés.
Types Abstraits de Données(TAD)
14
Spécification d’un TAD en Java– Java propose le concept d’interface
• Degré d’abstraction plus élevé.• Définition formelle d’un TAD.• Déclaration des méthodes de manière
abstraite.• La classe qui implante l’interface
– encapsule la structure de données choisie et– fournit le code des méthodes déclarées dans
l’interface.
Types Abstraits de Données(TAD)
15
Il existe différentes familles de types de données abstraits.
Nous allons nous intéresser aux Types Abstraits de Données décrivant les organisations complexes (containers).
Types Abstraits de Données(TAD)
16
Exemples:1. Gestion d’un annuaire :
– Insertion de personnes– Suppression de personnes– Recherche de personnes suivant leur nom
2. Gestion d’une file d’attente:– Ajouter des personnes en fin de file– Traiter la personne en début de file
Types Abstraits de Données(TAD)
17
Les objectifs : Définir les différents types d’ensembles
dynamiques.
Présenter les techniques permettant de les implanter efficacement en fonction du problème.
Types Abstraits de Données(TAD)
18
Les opérations sur un TAD sont de quatre types :
– Constructeurs– Modificateurs– Sélecteurs– Itérateurs
Autres dénominations : Constructeurs/Extenseurs
Types Abstraits de Données(TAD)
19
Plan d’étudeA) Les structures linéairesB) Les arbresC) Les ensemblesD) Les tables
Types Abstraits de Données(TAD)
20
A – Les structures linéaires1. Les listes2. Le TAD liste3. Le TAD pile4. Le TAD file5. Le TAD file de priorités6. Implémentation en Java
21
1 - Les listes Généralités
Définition: Une liste est formée d’une séquence d’éléments d’un type donné, dont le nombre peut être borné ou illimité.
Exemples : liste de passage à un examen, file d’attente à un guichet.
Une liste pourra être triée ou non.
22
1 - Les listes
Deux structures de données pour implémenter une liste:
1. Implémentation statique par un tableau2. Implémentation dynamique par une liste
chaînée
23
1 - Les listes Implémentation par un tableau
– Représentation
– Oblige à faire une estimation du nombre maximum d’éléments dans la liste.
– Entraîne des temps de calculs importants pour réaliser les insertions et les suppressions [ou tableau chainage]
tailleinfo1 info2 info31 2 3
début fin
24
1 - Les listes Implantation par une liste chaînée
– Une liste chaînée est une structure de données dans laquelle les objets sont arrangés linéairement.
– Chaque élément de la liste devra indiquer l’adresse de l’élément suivant.
– Un élément est donc représenté par un couple composé d’une information et d’une adresse, appelé cellule.
25
1 - Les listes Implantation par une liste chaînée
– Une liste chaînée est constituée d’un ensemble de cellules chaînées entre elles.
– C’est l’adresse de la première cellule qui détermine la liste
ba c
liste
26
1 - Les listes Implantation par une liste chaînée
– Allocation dynamique à la demande. Les éléments sont dispersés en mémoire centrale.
– Pas de déplacement des éléments en cas d’insertion ou de suppression.
a dcb
Suppression de l’élément c
a dcb
Insertion d’un élément x x
27
1 - Les listes Accès aux éléments d’une liste
– Comment caractériser les opérations sur les listes?
• La recherche d’un élément dont on connaît une partie de l’information : pas d’ambiguïté
• L’insertion, la suppression et la consultation nécessitent la mention de la position où s’effectue l’opération.
28
1 - Les listes Accès aux éléments d’une liste
Il existe plusieurs TAD classiques suivant les typesd’insertion et de suppression choisis :1. Liste : rien de défini2. Pile (LIFO) : insertion et suppression à la fin.3. File (FIFO) : suppression au début, insertion à la fin.4. File de priorité : insertion suivant un critère
d’ordre, suppression au début.
29
2 – TAD liste Les opérations
– Constructeur• Créer une liste vide
– Modificateurs• Insérer une valeur au début d’une liste• Supprimer un élément d’une liste• Supprimer tous les éléments d’une liste
30
2 – TAD liste
Les opérations– Sélecteurs
• Savoir si une liste est vide• Obtenir la longueur d’une liste• Déterminer la valeur du début d’une liste• Rechercher un élément dans une liste• Vérifier si une liste est égale à une autre liste
31
3 - TAD pile Définition: Une pile est une liste pour laquelle
l’insertion et la suppression ont lieu toutes les deux au sommet.
Analogie avec la pile d’assiettes Applications :
– Analyse des expressions par un compilateur– Allocation de la mémoire pour les variables locales lors
de l’exécution des procédures
Sommet de la pile
Dépiler [POP](supprimer)
Empiler [PUSH] (insérer)
32
3 - TAD pile Les opérations
– Constructeur• Créer une pile vide
– Modificateurs• Empiler une valeur au sommet de la pile (push)• Désempiler (pop)• Supprimer tous les éléments
33
3 - TAD pile
Les opérations– Sélecteur
• Savoir si une pile est vide• Obtenir la longueur d’une pile• Déterminer la valeur du sommet d’une pile• Vérifier si une pile est égale à une autre pile
34
3 - TAD pile Application 1:Ecrire un algorithme qui vérifie qu’un texte contenant
des caractères standards est syntaxiquement correct du point de vue des parenthèses.
Les parenthèses sont de trois types : (, {, [ et leurs parenthèses fermantes correspondantes sont respectivement ), }, ].
La correction syntaxique implique qu’à chaque parenthèse ouvrante corresponde une parenthèse fermante du même type, plus loin dans le texte.
Le texte compris entre ces deux parenthèses devra également être correct du point de vue des parenthèses.
35
3 - TAD pile Application 1: SolutionDonnées : c un tableau de N caractères qui contient le texte.Algorithme : créer une pile de caractères p vide.pour i = 0 à N-1 faire
si (c[i] est une parenthèse ouvrante) alors p.empiler(c[i])sinon si (c[i] est une parenthèse fermante) {
si (p.estVide()) {stop « erreur : il manque une parenthèse ouvrante
»}si (p.sommet() est du même type que c[i]) {
p.depiler()} sinon {
stop « erreur : la parenthèse fermante n’est pas du bon type »
}finsi
finsifinsi
finPoursi (p.estVide()) alors afficher « la syntaxe est correcte »sinon afficher « il manque une parenthèse fermante »finsi
36
3 - TAD pile Application 2:
– Les piles sont utilisées pour implémenter la récursivité par les langages de programmation.
– Chaque langage, autorisant la récursivité,utilise une pile «d’enregistrements actifs » pour enregistrer les informations relatives à chaque procédure active du programme.
37
3 - TAD pile Application 2: Utilisation des piles par la
JVM en cas d’appels récursifs d’une méthode: La JVM garde en mémoire la chaîne des méthodes
actives dans une pile. Quand une méthode est appelée, la JVM empile
un cadre contenant les variables locales, les valeurs à retourner et l’adresse de retour, i.e. le point où cette méthode a été appelée par la méthode appelante.
Quand une méthode est terminée, son cadre est retiré de la pile et le contrôle est passé à la nouvelle méthode du haut de la pile au point indiqué par l’adresse de retour.
38
4 - TAD File Définition : Une file est une liste pour laquelle
l’insertion a lieu à la fin (dépôt) et la suppression ( prélèvement) au début.
Analogie avec une file d’attente Applications :Une file sera utilisée quand il
faudra gérer l’allocation d’une ressource à plusieurs clients.
– File d’impression– Simulation de files réelles (guichet, trafic
automobile…)
déposerprélever
tête de la file fin de la file
39
4 - TAD File Les opérations
– Constructeur• Créer une file vide
– Modificateurs• Déposer une valeur à la fin de la file • Prélever la valeur de début de la file• Effacer tous les éléments de la file
40
4 - TAD File
Les opérations– Sélecteur
• Savoir si une file est vide• Obtenir la longueur d’une file• Déterminer la valeur du début d’une file• Vérifier si une file est égale à une autre file
41
5 - TAD File de priorités Définition : Une file de priorités est une
file pour laquelle – le dépôt a lieu en fonction d’un critère
d’ordre appelé priorité de la file.– Le prélèvement est tel que l’élément avec
la priorité la plus élevée est le premier à sortir.
La file est donc toujours triée selon le critère de priorité.
42
5 - TAD File de priorités Applications: Ce type de file est
largement utilisé dans les systèmes informatisés. Si plusieurs ordinateurs connectés à une même imprimante lancent des tâches d’impression en même temps, on peut décider d’établir un ordre de passage suivant la taille du document.
43
5 - TAD File de priorités
Les opérations : Par rapport à une file,– seul le dépôt change.– l’élément de fin peut être supprimé car il
ne joue aucun rôle particulier.
44
5 - TAD File de priorités Complexité :
Comme le dépôt dépend des éléments déjàprésents dans la file de priorités, la complexité
est O(n2).
Cette complexité peut être abaissée à O(nlog(n))en utilisant un tas qui est une structure de
données arborescente.
45
6 – Implémentation en Java Spécification du TAD liste
package listes;public interface Liste { //modificateur
void insererAuDebut(Object element);void effacer();boolean effacerElement(Object element);
//selecteursboolean estVide();int longueur();Object tete() throws ListeVideException;boolean rechercher (Object element);boolean equals(Object o);
}
46
6 – Implémentation en Java
Le TAD liste peut être implanter à l’aide de deux structures de données :
– Un tableau– Une structure chaînée
47
6 – Implémentation en Java Implantation avec une structure chaînéepackage listes;class Noeud{ protected Object valeur; protected Noeud suivant; public Noeud(){ } public Noeud (Object o){ this.valeur = o; this.suivant=null; }
//construire un noeud par copie public Noeud (Noeud n){ this.valeur = n.valeur; this.suivant=n.suivant; }}
48
6 – Implémentation en Javapublic class ListeChainee implements Liste{ private Noeud tete; private int longueur; //constructeurs public ListeChainee() { tete = null; longueur =0; } public ListeChainee(ListeChainee listeSource){ tete = listeSource.tete; longueur =listeSource.longueur; }
...
49
6 – Implémentation en Java//modificateurs
public void insererAuDebut (Object element) { Noeud nouveau = new Noeud (element); nouveau.suivant = tete; tete = nouveau; longueur ++;}
public void effacer () { tete = null; longueur=0;}
50
6 – Implémentation en Java public boolean effacerElement( Object element ) { Noeud courant = this.tete; Noeud precedent = null; while (courant != null){ if ((courant.valeur).equals(element)){
longueur--; if (courant == tete){ tete = courant.suivant; return true;
} else { precedent.suivant = courant.suivant; return true;
}} else {
precedent = courant; courant = courant.suivant;} } return false; //élément non trouvé }
51
6 – Implémentation en Java //sélecteurs public boolean equals(Object o) { if (o==this) return true; if (o==null) return false;
if (o.getClass() != this.getClass()) return false; ...
52
6 – Implémentation en JavaListeChainee liste = (ListeChainee) o;if (liste.longueur() != this.longueur())
return false; Noeud courant1 = liste.tete;Noeud courant2 = this.tete;while (courant1 != null){
if(!courant1.valeur.equals(courant2.valeur))
return false; courant1 = courant1.suivant; courant2 = courant2.suivant; } return true;}//fin de la méthode equals
53
6 – Implémentation en Javapublic boolean rechercher(Object o) { Noeud courant = this.tete; while (courant != null){ if ((courant.valeur).equals(o)) return true; else courant = courant.suivant; } return false; }
54
6 – Implémentation en Java public boolean estVide() { return (this.tete == null); } public int longueur() { return longueur; } public Object tete()
throws ListeVideException { if (estVide())
throw new ListeVideException();
return tete.valeur; }
55
6 – Implémentation en Java public String toString(){ String s ="["; Noeud courant = this.tete; if (courant !=null) s = s+""+courant.valeur; while (courant !=null){ s = s +","+ courant.valeur; courant = courant.suivant; } return s + "]";}
}
}
56
6 – Implémentation en Javapackage listes;
public class ListeVideException extends
RuntimeException{
public ListeVideException() { super("Votre liste est vide"); } }
57
6 – Implémentation en Java Spécification du TAD Pilepackage pile;public interface Pile { //modificateursvoid empiler(Object element);Object depiler()
throws PileVideException;void effacer();//selecteursboolean estVide();Object sommet()
throws PileVideException;int longueur();boolean equals(Object o);
}
58
6 – Implémentation en Java Spécification du TAD Filepackage file;public interface File { // modificateurs void deposer(Object element); Object prelever()
throws FileVideException; void effacer();
// selecteursboolean fileVide();boolean equals (Object o);Object tete()
throws FileVideException;int longueur();
}
59
B – LES ARBRES Introduction
– Un arbre est une collection d’éléments organisés suivant une structure hiérarchique.
– Dans de nombreux problèmes, les données sont naturellement structurées de manière arborescente:• Arbre généalogique, organigrammes• Arbre syntaxique• Arbre de décision• Table des matières d’un livre
60
B – LES ARBRES Introduction
– Les structures d’arbres permettent d’implémenter efficacement des algorithmes d’insertion, de suppression, de recherche et de tri.
– Les arbres conviennent particulièrement bien comme structure de données pour implanter des dictionnaires informatiques.
– Les différents SGBD font appels à des arbres particuliers pour l’organisation physique des données et en particulier pour gérer les index.
61
B – LES ARBRES
Exemple :Représentation arborescente d’une table des matières
Livre
chapitre1 chapitre2 chapitre3
s11 s12 s21 s22 s23 s31 s32
s221 s222
62
B – LES ARBRES Définition1 d’un arbre
Un arbre est composé de deux ensembles N et A appelés respectivement l’ensemble des nœuds et l’ensemble de arcs et d’un noeud particulier appelé racine de l’arbre.Les éléments de A sont des paires (n1, n2) d’éléments de N.A doit être tel que chaque nœud, excepté la racine, a exactement un parent.
63
B – LES ARBRES
Définition2 d’un arbre (récursive)Un arbre est soit un ensemble vide, soit une paire A(r,S), r étant un nœud et S étant un ensemble d’arbres disjoints ne contenant pas r.
r
A1 A2 A3 S
A
64
B – LES ARBRES
Définitions usuelles– Un arbre vide est un arbre ne comportant
aucun nœud;– Une feuille est un nœud n’ayant aucun fils;– Un nœud interne est un nœud qui n’est pas
une feuille;– Un sous-arbre est un sous-ensemble des
nœuds d’un arbre ayant une structure d’arbre.
65
B – LES ARBRES
Définitions usuelles– La taille d’un arbre est égale au nombre de
nœuds qu’il contient.– L’étiquette d’un nœud est l’information
associée à celui-ci.– Le degré d’un nœud est égal au nombre de
ses fils;– Le degré d’un arbre est égal au maximum
des degrés de tous ses nœuds;
66
B – LES ARBRES
Plan d’étudeLes arbres seront traités dans un premier temps
comme des TAD.Les arbres binairesLes arbres binaires de recherche
On abordera ensuite leur utilisation comme structure de données très efficaces pour implanter plusieurs autres TAD tels que les dictionnaires
67
1 – LES ARBRES BINAIRES Généralités
– Définition 1 Un arbre binaire est un arbre de degré deux.Les fils sont appelés fils gauche et fils droit.
– Définition2 (récursive)Un arbre binaire est soit vide, soit constitué d’un nœud racine possédant un sous-arbre binaire gauche et un sous-arbre binaire droit.
68
1 – LES ARBRES BINAIRES
TAD Arbre binaire– Construteur
• Créer un arbre vide– Modificateurs
• Remplacer l’étiquette d’une racine• Accrocher un arbre comme sous-arbre gauche ou droit
d’un arbre• Décrocher le sous-arbre gauche ou droit d’un arbre• Effacer le contenu d’un arbre
69
1 – LES ARBRES BINAIRES
TAD Arbre binaire– Sélecteurs
• Vérifier si deux arbres sont égaux• Savoir si un arbre est vide• Déterminer l’étiquette de la racine• Obtenir le sous-arbre gauche d’un arbre• Obtenir le sous-arbre droit d’un arbre
70
1 – LES ARBRES BINAIRES
Parcours d’un arbre binaireIl y a plusieurs façon de visiter tous les nœuds d’un arbre pour les afficher ou leur appliquer un traitement.On va étudier les parcours les plus utilisés :• Parcours préordonné appelé aussi préfixé ou en
profondeur• Parcours symétrique• Parcours postordonné appelé aussi postfixé • Parcours en largeur
71
1 – LES ARBRES BINAIRES Le parcours préordonné
Algorithme :Si l’arbre n’est pas vide alors
traiter la racine de l’arbreeffectuer le parcours préordonné du sous-arbre gaucheeffectuer le parcours préordonné du sous-arbre droit
Fin si
72
1 – LES ARBRES BINAIRES
Le parcours préordonné
Application à l’arbre suivant:
Résultat : A B F G E I
A
B E
F G I
73
1 – LES ARBRES BINAIRES
Le parcours symétrique
Algorithme :Si l’arbre n’est pas vide alors
effectuer le parcours symétrique du sous-arbre gauchetraiter la racine de l’arbreeffectuer le parcours symétrique du sous-arbre droit
Fin si
Résultat : F B G A I E
74
1 – LES ARBRES BINAIRES
Le parcours postordonné
Algorithme :Si l’arbre n’est pas vide alors
effectuer le parcours postordonné du sous-arbre gauche
effectuer le parcours postordonné du sous-arbre droit traiter la racine de l’arbreFin si
Résultat : F G B I E A
75
1 – LES ARBRES BINAIRES Le parcours en largeur
Algorithme :Créer une file videSi l’arbre n’est pas vide alors
déposer la racine de l’arbre dans la filetant que la file n’est pas vide boucler prélever un nœud dans la file traiter ce nœud pour chaque fils de ce nœud, pris de gauche à droite,boucler
déposer ce nœud dans la file fin boucler
fin bouclerFin siRésultat : A B E F G I
76
1 – LES ARBRES BINAIRES
Application des parcours: les arbres d’expression
Définition d’une expression arithmétique : Combinaison d’opérateurs arithmétiques ( +, -, *, /), d’opérandes et de parenthèses exprimant les priorités des opérations.Chaque expression arithmétique peut être représentée par un arbre binaire appelé arbre d’expression :(a * (b – c)) *
a -
b c
77
1 – LES ARBRES BINAIRES Construction de l’arbre d’expression
associé à une expression arithmétique donnéeConstruction récursive à l’aide des règles suivantes:1. L’arbre d’expression d’un seul opérande est un
nœud racine unique le contenant.2. Si E1 et E2 sont des expressions représentées
par les arbres T1, T2 et si op est un opérateur, alors l’arbre d’expression E1 op E2 est composé d’un nœud racine contenant op et de deux sous-arbres T1 et T2.
78
1 – LES ARBRES BINAIRES
Conversion d’une expression arithmétique exprimée en notation infixée en notation postfixée:A partir de l’arbre d’expression associé à l’expression arithmétique, on peut exprimer l’expression arithmétique en notationpostfixée en utilisant un parcours postordonné.
79
1 – LES ARBRES BINAIRES Différentes représentations du TAD Arbre
Binaire 1. Représentation contiguë par un tableau de nœuds
Un nœud est caractérisé par une étiquette, un champ gauche et un champ droite de type entier.
Gauche et droite sont des indices permettant de retrouver les sous-arbres gauche et droit d’un nœud.On affectera à gauche (resp. droite) la valeur -1 quand le nœud n’a pas de sous-arbre gauche (resp. droit).
80
1 – LES ARBRES BINAIRES
Différentes représentations du TAD Arbre Binaire
Exemple :
1 3 5 -1 -1 7 -1 -1 -1A B E C D F I G H2 4 6 -1 -1 8 -1 -1 -1
A
B
C D
E
F I
G
gauche
étiquette
droite
H0 1 2 3 4 5 6 7 8
81
1 – LES ARBRES BINAIRES
Différentes représentations du TAD Arbre binaire2. Représentation chaînéeChaque nœud est caractérisé par• une étiquette• un pointeur vers le fils gauche• un pointeur vers le fils droit
82
1 – LES ARBRES BINAIRES
Différentes représentations du TAD Arbre binaire2. Représentation chaînée
racine A
B E
C D F I
G H
83
1 – LES ARBRES BINAIRES Spécification du TAD Arbre binaire en JAVApackage arbresBinaires;public interface ArbreBinaire { //modificateurs public void effacer(); public void modifierRacine(Object e) throws
ArbreBinaireVideException; public void accrocherGauche(ArbreBinaire a) throws
ArbreBinaireVideException; public void accrocherDroit(ArbreBinaire a) throws
ArbreBinaireVideException; public ArbreBinaire decrocherGauche() throws
ArbreBinaireVideException; public ArbreBinaire decrocherDroit() throws
ArbreBinaireVideException;
84
1 – LES ARBRES BINAIRES Spécification du TAD Arbre binaire en JAVA//selecteurspublic boolean estVide();public Object racine() throws
ArbreBinaireVideException;public ArbreBinaire droit() throws ArbreBinaireVideException;public ArbreBinaire gauche() throws ArbreBinaireVideException;
//parcours pour affichage public void parcoursSymetrique(); public void parcoursPreOrdonne() ; public void parcoursPostOrdonne() ; public void parcoursLargeur() ;}
85
1 – LES ARBRES BINAIRES Implantation du TAD Arbre binaire en JAVA
en utilisant une structure de données chainée.package arbresBinaires;public class Noeud { protected Object etiquette; protected Noeud ng; protected Noeud nd; public Noeud(Object o) { etiquette=o; ng =null; nd =null; }}
86
1 – LES ARBRES BINAIRES Implantation du TAD Arbre binaire en JAVApackage arbresBinaires;public class ArbreBinaireVideException extends RuntimeException{
public ArbreBinaireVideException() {
super("Votre arbre est vide");}public ArbreBinaireVideException(String msg) {
super(msg);}
}
87
1 – LES ARBRES BINAIRES Implantation du TAD Arbre binaire en JAVApackage arbresBinaires;public class ABChaine implements ArbreBinaire{ protected Noeud racine;public ABChaine() {
racine = null; } public ABChaine(Noeud n) { racine = n; }
88
1 – LES ARBRES BINAIRES//modificateurs public void effacer(){ racine = null; } public void modifierRacine(Object e) throws ArbreBinaireVideException{
if (estVide()) throw new ArbreBinaireVideException();
racine.etiquette=e; }
89
1 – LES ARBRES BINAIRESpublic void accrocherDroit(ArbreBinaire a) throws ArbreBinaireVideException{
if (estVide()) throw new
ArbreBinaireVideException();ABChaine ad = (ABChaine)a;racine.nd = ad.racine;
90
1 – LES ARBRES BINAIRESpublic void accrocherGauche(ArbreBinaire a) throws ArbreBinaireVideException{if (estVide()) throw new ArbreBinaireVideException();
ABChaine ag = (ABChaine)a; racine.ng = ag.racine;
}
91
1 – LES ARBRES BINAIRESpublic ArbreBinaire decrocherDroit() throws
ArbreBinaireVideException{ if (estVide()) throw new
ArbreBinaireVideException(); ArbreBinaire a= new ABChaine(racine.nd);racine.nd= null;return a;}
public ArbreBinaire decrocherGauche() throws ArbreBinaireVideException{
if (estVide()) throw new ArbreBinaireVideException(); ArbreBinaire a= new ABChaine(racine.ng);racine.ng= null;return a;}
92
1 – LES ARBRES BINAIRES//sélecteurs public ArbreBinaire droit() throws ArbreBinaireVideException{
if (estVide()) throw new ArbreBinaireVideException();
return new ABChaine(racine.nd);} public ArbreBinaire gauche() throws ArbreBinaireVideException{
if (estVide()) throw new ArbreBinaireVideException();
return new ABChaine(racine.ng);}
93
1 – LES ARBRES BINAIRESpublic boolean estVide() { return (racine==null); }public Object racine() throws ArbreBinaireVideException{
if (estVide()) throw new
ArbreBinaireVideException(); return racine.etiquette;}
94
1 – LES ARBRES BINAIRES public void parcoursSymetrique(){cf td}
public void parcoursPreOrdonne(){ cf td}
public void parcoursPostOrdonne(){ cf td}
public void parcoursLargeur(){// todo in td
}}
95
2 - Arbres binaires de recherche
DéfinitionUn arbre binaire de recherche est un arbre binaire satisfaisant aux propriétés suivantes:– L’étiquette de chaque nœud contient une valeur
particulière d’un type ordonné appelée clé;– Pour tout sous-arbre, la clé de la racine est
strictement supérieure à toutes les clés du sous-arbre gauche et strictement inférieure à toutes les clés du sous-arbre droit.
96
2 - Arbres binaires de recherche
Exemple
15
10
8
18
17 20
97
2 - Arbres binaires de recherche Le TAD arbre binaire de
recherche– Constructeur
• Créer un arbre vide– Modificateurs
• Effacer le contenu d’un arbre• Insérer un élément dans un arbre en
fonction de sa clé• Supprimer un élément dans un arbre
98
2 - Arbres binaires de recherche Le TAD arbre binaire de
recherche– Sélecteurs
• Les mêmes que pour le TAD arbre binaire
• Rechercher un élément dans un arbre
99
2 - Arbres binaires de recherche Algorithme de recherche d’un élément
si l’arbre est vide alorssignaler que l’élément est introuvable
sinon si (clé de l’élément < clé de la racine) alorsrechercher l’élément dans le sous-arbre
gauche sinon si (clé de l’élément > clé de la racine) alors
rechercher l’élément dans le sous-arbre droit
sinon retourner la racinefin si
fin sifin si
100
2 - Arbres binaires de rechercheAlgorithme d’insertion d’un élément si l’arbre est vide alors
créer une feuille contenant cet élément [=racine] sinon si (clé de l’élément < clé de la racine) alors
insérer l’élément dans le sous-arbre gauche sinon si (clé de l’élément > clé de la racine) alors
insérer l’élément dans le sous-arbre droitsinon erreur : élément existe déjà dans
l’arbrefin si
fin sifin si
101
2 - Arbres binaires de rechercheAlgorithme de suppression d’un élément
Localiser le nœud à supprimer par une recherche récursive.Une fois le nœud trouvé, il faut distinguer 3 cas:
1. Le nœud n’a pas de fils droit;2. Le nœud possède un fils droit mais pas de fils gauche;3. Le nœud possède deux fils. Cas 1 et 2, il suffit de court-circuiter le nœud à supprimer.Cas 3 :
Rechercher la clé maximale dans le sous arbre gauche du nœud à supprimer.Recopier cet élément dans le nœud à supprimer.Supprimer le nœud que l’on vient de recopier (cas 1).
102
2 - Arbres binaires de recherche
Algorithme de suppression d’un élémentsi l’arbre est vide alors
signaler une erreur (élément introuvable)sinon si l’arbre ne contient qu’un nœud dont la clé est
égale à la clé de l’élément alors retourner l’arbre vide sinon si (clé de l’élément < clé de la racine)
alorssupprimer l’élément dans le sous-
arbre gauche sinon si (clé de l’élément > clé de la racine) alors
supprimer l’élément dans le sous-arbre droit
sinon //la racine contient l’élément à supprimer et n’est pas une feuille
fin si fin sifin si
fin si
103
2 - Arbres binaires de recherche– Algorithme de suppression d’un élément suite
sinon //la racine contient l’élément à supprimer et n’est pas une feuille
si le sous-arbre droit est vide //cas1 alorsremplacer l’arbre par son sous-
arbre gauchesinon si le sous-arbre gauche est vide
//cas2 alors remplacer l’arbre par son sous-arbre droit
sinon //cas3rechercher le plus grand élément
du sous arbre gaucheremplacer l’étiquette de la racine
par celle de ce plus grand élément et supprimer l’élément
fin sifin si
fin si fin si
fin si
104
2 - Arbres binaires de recherche Parcours d’un arbre binaire de
rechercheLa propriété 2) des arbres binaires de
recherche permetd’afficher toutes les clés de l’arbre dans
l’ordre croissantà l’aide d’un parcours symétrique.
105
2 - Arbres binaires de recherche Application : On peut donc trier des
éléments en utilisant un arbre de recherche : • Insertion des éléments dans l’arbre de recherche• Parcours symétrique de l’arbre obtenu.L’intérêt réside dans l’efficacité de ce tri.Complexité : O(nlog(n)).Il faut cependant faire l’hypothèse que l’arbre n’estpas trop déséquilibré, i.e. pour chaque nœud, il y aapproximativement autant de nœud dans le sousarbre gauche que dans le sous-arbre droit.
106
2 - Arbres binaires de recherche
Il y a deux approches pour s’assurer qu’un arbre de recherche soit équilibré:
– L’équilibrer de temps en temps– Imposer l’équilibrage comme
contrainte supplémentaire pour l’arbre de recherche. On obtient alors un arbre AVL.
107
C – LES ENSEMBLES Définition
Un ensemble est une collection d’éléments uniques.Notation : S = {a, b, c}Les opérations principales sur les
ensembles :–Union– Intersection–Complément relatif ou différence
108
C – LES ENSEMBLES Le TAD ensemble
//constructeurs– Construire un ensemble vide– Construire un ensemble par union de deux
autres ensembles– Construire un ensemble par intersection de
deux autres ensembles– Construire un ensemble par différence de
deux autres ensembles//modificateurs– Insérer un élément dans un ensemble– Supprimer un élément d’un ensemble– Effacer tous les éléments d’un ensemble
109
C – LES ENSEMBLES Le TAD ensemble
//sélecteurs–Vérifier qu’un élément fait partie d’un
ensemble–Vérifier que deux ensembles sont égaux–Savoir si un ensemble est vide
110
C – LES ENSEMBLES Les implantations du TAD ensemble
– Cas où les ensembles sont des sous-ensembles d’un ensemble universel constitué des entiers 1, …, N pour un N donné:L’implémentation la plus simple et efficaceconsiste à utiliser un tableau de booléens T tel que T[i]= 1 si i appartient à l’ensemble
T[i] = 0 sinon.
111
C – LES ENSEMBLES Les implantations du TAD ensemble
– Les opérations d’insertion, de suppression et de recherche d’un élément sont réalisées en temps constant (O(1)).
– La réunion, l’intersection et la différence dans un temps proportionnel à la taille de l’ensemble universel.
112
C – LES ENSEMBLES Les implantations du TAD ensemble
–Cas général : on peut aussi utiliser une liste chaînée. Pas de limitation à des sous-ensembles d’un ensemble universel d’entiers.
113
C – LES ENSEMBLES Les dictionnaires
– Pas toujours besoin des opérations telles quel’union et l’intersection.
– On a souvent besoin de manipuler un ensemble d’objets avec seulement des insertions, des suppressions et d’effectuer des recherches.
– Le TAD ensemble avec uniquement ces trois opérations est appelé un dictionnaire.
114
C – LES ENSEMBLES Spécification du TAD dictionnairepackage dictionnaire;public interface Dictionnaire {
//modificateurs public void effacer(); public void inserer(Object x); public void supprimer(Object x)
throws DicoVideException;
//selecteurs public boolean estVide(); public boolean rechercher(Object x) ;}
115
C – LES ENSEMBLES Les implantations du TAD dictionnaire
1. par des structures de données simples :tableau, listes chaînées
2. par tables de hachage3. par arbres binaires de recherche
116
C – LES ENSEMBLES
1- Utilisation des structures de données simples: – Tableau avec un pointeur sur le dernier élément
Envisageable si on sait que la taille des ensembles ne dépassera jamais la taille du tableau.
Avantage : simplicitéInconvénients : suppression plus lente, l’espace n’est pasutilisé de manière efficace quand les ensembles sont de
taillevariable.
– Liste chaînée
117
C – LES ENSEMBLES Complexité des algorithmes
– L’implantation par tableau ou par liste chaînée du dictionnaire demande, en moyenne, n opérations pour exécuter une insertion, une suppression ou une recherche. Complexité : O(n).
– On va étudier une technique très utilisée pour implanter des dictionnaires : le hachage.Cette technique demande, en moyenne, un temps constant pour les trois opérations.Complexité : O(1).
118
C – LES ENSEMBLES2- Les tables de hachage
– La structure de données table de hachage est idéalement un tableau de taille N fixée contenant les éléments de l’ensemble.
– La répartition des éléments de l’ensemble dans le tableau se fait en utilisant une fonction appelée fonction de hachage.
119
C – LES ENSEMBLES2- Les tables de hachage
– Une fonction de hachage est une fonction h qui, pour chaque élément x de l’ensemble, calcule une valeur h(x) comprise entre 0 et N-1 correspondant à un indice du tableau.
2]1..0[:
xNEnsembleh
x
Table de hachage
0
1
2
N-1
120
C – LES ENSEMBLES2- Les tables de hachage
–En utilisant la même fonction de hachage pour l’insertion et la recherche, l’exécution de ces opérations demande se fait en temps constant.
–En pratique, ce cas idéal n’existe pas du fait de collisions.
121
C – LES ENSEMBLES2- Les tables de hachage
– Collision : pour deux éléments différents de l’ensemble, la fonction de hachage produit la même valeur.
– Exemple
x , y
yxetyhxh 2)()(
0
1
2
N-1
122
C – LES ENSEMBLES
2- Les tables de hachage– Une bonne fonction de hachage doit
calculer rapidement une valeur mais aussi diminuer le nombre de collisions.
– Exemple de fonction de hachage pour un ensemble dont les éléments sont des chaînes de caractères :
)mod)(()( Ncaractèresdecodeschaîneh
taille du tableau
123
C – LES ENSEMBLES
2- Les tables de hachage– Application à l’ensemble { Jean, Jacques, Vincent,
Lucien, Pierre}et une table de taille 10.
Jean 7Jacques 5Vincent 6Lucien 9Pierre 6
JacquesVincent, PierreJean
Lucien
chaîne h(chaîne)
0
1
2
3
4
5
6
7
8
9
124
C – LES ENSEMBLES2- Les tables de hachage
–En cas de collision, deux approches sont utilisées:• Gestion par hachage ouvert• Gestion par hachage fermé
125
2- Les tables de hachage– Gestion par hachage ouvert
En cas de collision, le tableau est «ouvert» vers la droite.
5
6
7
8
9
Jacques
Vincent Pierre
Lucien
Jean
Inconvénient : Plus il y a de collisions
->Plus les listes sont longues
->Moins la recherche est efficace
C – LES ENSEMBLES
126
C – LES ENSEMBLES2- Les tables de hachage
–Gestion par hachage ferméOn cherche à replacer l’élément en collision ailleurs dans le tableau en appliquant une fonction de rehachage qui calcule un nouvel indice et ceci jusqu’à ce que la nouvelle entrée soit libre.
127
C – LES ENSEMBLES2- Les tables de hachage
–Gestion par hachage fermé• Exemple de fonction de rehachage :
Fonction qui incrémente de 1 l’indiceobtenu.
• Ce choix conduit à une dégradation des performances dès que le taux de remplissage de la table dépasse 90%.
128
C – LES ENSEMBLES2- Implantation du TAD dictionnaire
par table de hachage, gestion par hachage ouvert
package dictionnaire;import listes.*;public class DicoHachageOuvert implements Dictionnaire{
private int taille; private static final int MASK = 0x7FFFFFFF;//forme hexadecimale
//MASK = 2147483647 private ListeChainee[] tableau; //tableau de listes
129
C – LES ENSEMBLES public DicoHachageOuvert(int dimension) { taille = dimension; //initialiser le tableau tableau = new ListeChainee[taille]; for (int i=0; i<taille; i++){ tableau[i] = new ListeChainee(); } }private int hachage(Object c){ return (c.hashCode()&MASK)%taille; //somme //modulo taille
//n&MASK permet de supprimer le signe de //l'entier n
}
130
C – LES ENSEMBLESpublic void effacer() { for (int i=0; i<taille; i++){ tableau[i].effacer(); } } public boolean estVide() { for (int i=0; i<taille; i++){ if (!tableau[i].estVide()) return false; } return true;}
131
C – LES ENSEMBLES public void inserer(Object x) { if(!rechercher(x)) tableau[hachage(x)].insererAuDebut(x)
}public void supprimer(Object x) throws DicoVideException {
if (estVide()) throw new DicoVideException();
Liste courant=null; courant=tableau[hachage(x)]; boolean b = courant.effacerElement(x);
}
132
C – LES ENSEMBLES public boolean rechercher(Object x) { int i =hachage(x);
return tableau[i].rechercher(x); }}//fin de la classe DicoHachageOuvert
133
C – LES ENSEMBLES3- Les arbres binaires de recherche
– Cette structure de données permet d’implanter les ensembles dont les éléments sont ordonnés.
– Moins efficace que les tables de hachage pour les insertions, les suppressions et les recherches.
– Plus efficace pour trier les données : parcours symétrique de la structure à condition que l’arbre soit équilibré.
134
D – LES TABLES Définitions
– Une table est un conteneur qui permet un accès direct par type d’index.
– Un table est une séquence de lignes constituées de paires (clé, valeur):• la clé sert d’index dans la table.• la valeur du composant clé. Elle contient les
informations recherchées.– Exemple : le dictionnaire
• La clé est le mot consulté• La valeur est la définition du mot
135
D – LES TABLES Exemple de table
Paires (prénom, âge) où on suppose que le prénom peut être pris comme clé (toutes les personnes enregistrées ont des prénoms différents)
Jean 18Jacques 21Vincent 10Lucien 10Pierre 14
Prénom âge
136
D – LES TABLES Le TAD Table//constructeurs
– Construire une table vide//modificateurs
– Insérer une ligne dans la table– Remplacer une ligne dans la table– Extraire une ligne dans la table– Effacer toutes les ligne de la table
//sélecteurs– Rechercher une valeur dans la table en fonction de la clé– Savoir si une table est vide
137
D – LES TABLES
Les implantations du TAD Table1. Par un tableau ou une liste2. Par un arbre de recherche3. Par une table de hachage
138
D – LES TABLES Implantation du TAD Table par un
tableau ou une listeDeux types de recherche peuvent être
envisagés– Recherche séquentielle si la position des
paires à l’intérieur de la structure estquelconque. Complexité : O(n).
– Recherche par dichotomie qui nécessite une table triée et une implantation par tableau pour avoir un accès direct aux paires. Complexité : O(log(n))
139
D – LES TABLES Implantation du TAD Table par
un arbre de recherche
Lucien10
Jean
Jacques
18
21 14Pierre
Vincent10
140
D – LES TABLES
Implantation du TAD Table par un arbre de recherche
La recherche est plus performante que la recherche par dichotomie car même complexité O(log(n)) mais le tri est réalisé implicitement à l’insertion des paires.
141
D – LES TABLES Implantation du TAD Table par table
de hachageOn applique une fonction de hachage qui détermine l’indice du tableau à partir de la valeur de la clé.
Complexité insertion et recherche :O(1) (en théorie)
142
D – LES TABLES Implantation du TAD Table
par table de hachage
Jean 7Jacques 5Vincent 6Lucien 9Pierre 6
Jacques 21Vincent 10Pierre 14Jean 18
Lucien 10
clé h(clé)
0
1
2
3
4
5
6
7
89
143
D – LES TABLES Réalisation du TAD Table
– Spécification de la ligne de la table• Les opérations sur une table nécessitent de
pouvoir comparer les lignes entre elles en fonction de leur clé.
• Chaque ligne doit – fournir sa clé– pouvoir être comparée à une autre ligne – être traitée (affichée par exemple).
144
D – LES TABLES Réalisation du TAD Table
– Solution : Une ligne est spécifiée par l’interface TypeComparable:
public interface TypeComparable{//calculer la clé de la lignepublic Comparable cle();
//établir un ordre entre les lignespublic int compare(Object o);//Appliquer un traitement à la lignepublic void traiter();}
145
D – LES TABLES
Réalisation du TAD Table– Application à une ligne (prénom, âge):class PairePrenomAge implements
TypeComparable{ String prenom;
int age;
public PairePrenomAge(String prenom, int age){
this.prenom = prenom;this.age = age;
}
146
D – LES TABLESpublic int compare(Object o){ PairePrenomAge pa = (PairePrenomAge)o; return ((this.cle().compareTo(pa.cle()));}public Comparable cle(){
return prenom;}public void traiter(){
System.out.print(«Prenom:» + prenom);System.out.println(«Age:» + age);
}}
147
D – LES TABLES Réalisation du TAD Tablepublic interface Table {//modificateurs public void effacer (); public void inserer ( TypeComparable ligne)
throws TablePleineException, LigneEnDoubleException;
public void remplacer ( TypeComparable ligne) throws LigneIntrouvableException;
public TypeComparable extraire( TypeComparable ligne) throws LigneIntrouvableException;
//sélecteurspublic boolean rechercher ( TypeComparable
ligne);public boolean estVide();
}