39
Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: [email protected]

Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: [email protected][email protected]

Embed Size (px)

Citation preview

Page 1: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Structures de données avancées : Introduction

Pr ZEGOUR DJAMEL EDDINEEcole Supérieure d’Informatique (ESI)

zegour.esi.dz email: [email protected]

Page 2: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Structure de données

Structures de données : concept vital en Informatique

Pour un problème donné, quelle structures de données choisir pour l’implémentation de sa solution ?

Les arbres de recherche binaires équilibrés en RAM

Distribuées(RP*, LH*, TH*)

Les structures de fichiers

Unidimensionnelles (B-arbres, LH, TH,)

Multidimensionnelles (MB-arbres, MLH, MTH)

Dynamique (AVL, RB, AA)

Statique(DSW)

Structures de données spécifiques: Quadtree, Octree : ImagerieR-tree : données spatiales

Page 3: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Arbre de recherche binaire

Les arbres

Arbres AVL Arbres RBArm avec degré < 5Arm équilibrés : Arbres 2-3 et 2-4

Arbre m-aire

Arbre binaire

Arbre de rech

erche m

-aire

Page 4: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

AVL

B Arbres Arbres 2-3 Arbres 2-4

Arbres AA

Arbres Red-Black

Arbr

es é

quili

brés

en

RAM

1962

1972

1993

2008LLRB

1978

BB : B-arbres Binaires

SBB : B-arbres Binaires Symétriques

Arbres équilibrés en RAM

Page 5: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Local ou

distribué

Structures de fichiers : Classification

- Organisation directe( hash-code) - Organisation d'arbre ( tables

d'index hiérarchisées )

Simple attribut,

plusieurs attributs

Statique ou

dynamique

Préservation de

l'ordre ou pas

Page 6: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Hachage

B Arbres

LH TH

TH*

LH*

HI

HI*

MTH MLH MBT

Uni-dim

Distribuées

Multi-dim

1955

1973

1980 1981

1983

2002

1993

1985

RP* 1996

Stru

ctur

es d

e fic

hier

s

Structures de fichiers

Page 7: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

O-notation

Complexité des algorithmes

Mesure des algorithmes

Stratégies: files d’attente - piles

Expressions : itérative -récursive

Méthodologie : ascendante - descendante

Types abstraits et Implémentation

Généralités

Page 8: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Pré-requis : Structures de données en RAM

Page 9: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Tableaux, listes

Graphes

Arbre de recherche m-aire d’ordre 3 et 4

Arbre de recherche binaire

Hachage

Structures de données en RAM

Page 10: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

n

T2T1

Arbres binaires : types de parcours

Préordre : n T1 T2

Inordre : T1 n T2

Postordre : T1 T2 n

Préordre inverse : n T2 T1

Inordre inverse : T2 n T1

Postordre inverse : T2 T1 n

Parcours en largeur Gauche Droite

Parcours en largeur Droite Gauche

Etc.

Page 11: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Opérations:Recherche dichotomiqueL'élément inséré est toujours une feuilleSuppression : plus délicate.

Arbres de recherche binaire

Structure d'un nœud :

(s1, k, s2)

K: donnée et S1, S2 les fils

(Éléments dans s1 ) < k(Éléments dans s2) > k

L'inordre donne la liste ordonnée de tous les éléments.

Page 12: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

nfg fd Action

a) Nil Nil Remplacer n par Nilb) Nil #Nil Remplacer n par Fd(n)c) #Nil Nil Remplacer n par Fg(n)d) #Nil #Nil 1. Rechercher le plus petit descendant

du sous-arbre droit, soit p.2. Remplacer Info(n) par Info(p)3. Remplacer p par Fd(p)

Arbres de recherche binaire : Suppression

Page 13: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Généralisation de l'AB

Structure d'un nœud :

(k1, s1, s2 .......,sn)

• Pas de relation d’ordre

• Peut se transformer en un arbre binaire

Arbres m-aire

Page 14: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

a b cd

e f gh i

j k

r

n

T2T1 Tp…Préordre : n T1 T2 .. . Tp

( r a b e f j k g c d h i )

Inordre : T1 n T2 .…Tp( a r e b j f k g c h d i )

Postordre : T1 T2 ... Tp n( a e j k f g b c h i d r )

Arbres m-aire: Parcours

Page 15: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Généralisation de l'ARB

Structure d'un nœud : (s1, k1, s2, .......kn-1,sn)

k1 < k2 ....< kn-1

(Éléments dans s1 ) <= k1

(Éléments dans sj) > kj-1 et ≤ kj

(j=2,3, ...n-1)(Éléments dans sn) > kn-1.

Arbre de recherche m-aire TOP-DOWN : Tout nœud non rempli doit être une feuille. ( C’ est le plus utilisé )

Arbres de recherche m-aire

Arbre de recherche m-aire équilibré : B-arbre

Page 16: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Arbres de recherche m-aire

. 23 . 45 . 68. 80.

. 12 .

. 23 . 45 . 68. 80.

45, 68, 80, 25

12

50, 54

. 12 .

. 23 . 45 . 68. 80.

. 50 . 54 .

•Arbre de recherche TOP-DOWN

Page 17: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Arbres de recherche m-aire

. 12 .

. 23 . 45 . 68. 80.

. 50 . 54 .

20, 92, 48, 63, 60, 100

. 12 . 20 .

. 23 . 45 . 68. 80.

. 48. . 50 . 54 .63 . . 92 . 100 .

. 60.

Page 18: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Arbres de recherche m-aire

. 23 . 45 . 68. 80.

. 12 . 23 .

. 45 .

45, 68, 80, 25

12

50, 54

. 68 . 80 .

. 12 . 23 .

. 45 .

. 50. 54 . 68 . 80 .

•B-arbre (ordre=5)•Min=2 données; Max=4 données

Page 19: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Arbres de recherche m-aire

. 12 . 23 .

. 45 .

. 50. 54 . 68 . 80 .

20, 92

. 12 . 20 . 23 .

. 45 . 68 .

. 50. 54 . . 80. 92 .

48, 63, 60

. 12 . 20 . 23 .

. 45 . 54 . 68 .

. 60. 63 . . 80. 92 .. 48 . 50 .

Page 20: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Rangement des données dans un tableau

Rangement séquentiel( O(n) )Rangement ordonné ( O(Log(n) )Rangement aléatoire ou Hachage (Comme une 3ième possibilité avec

O(1)Technique : Transformer la donnée K par une fonction f. f(K) est alors l'emplacement où sera rangée la donnée K.

Le problème : Impossible de trouver une fonction bijective (paradoxe de l'anniversaire)

Existence de techniques de résolution des collisions.

Hachage

Page 21: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Double hachage (D) : - généralisation de l’essai linéaire- pas calculé par une autre

fonction de hachage)

Hachage : Techniques de résolution des collisions

Essai linéaire (L)En cas de collision sur la

case k, utilisation de la séquence cyclique K-1, ......, 0, M-1, M-2, ......K+1

Chainage séparé (S) : chaîner les synonymes à l’ extérieur de la table

Chainage interne (I) : chaîner les groupes de synonymes à l’intérieur de la table

Page 22: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Hachage : Synthèse

Données statiques

S > C > D > L

Pas d’ordre

Insertions contrôlées

Page 23: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Pré-requis : Structures de fichiers

Page 24: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Structure d’un disque

Page 25: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Secteur

Secteur : unité de transfert RAM Disque

Secteur

Secteur

Secteur

Secteur

Secteur

Secteur

Secteur

Secteur

Cluster (lecture sans bouger la tête de Lect/Ecrit)

Etendue = clusters contigus

Fichier = plusieurs étendus dispersés

Organisation d’un fichier sur le disque

Page 26: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Fragmentation interne : Présence de "trous" dans les blocs

Fichier = ensemble de blocs

Bloc = n secteurs ( un cluster de préférence)

Fragmentation externe : Présence de blocs entièrement vides

Organisation d’un fichier sur le disque

Page 27: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Bloc = n articles

Article = Ensemble de champs formant une même entité

Format des articles :fixe ou variable

Chevauchement éventuel des articles sur les blocs

Si format variable :-Indicateur de longueur ( nombre d'octets )

Organisation interne d’un fichier

Page 28: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Tableaux, listes

Indexes simples

B-arbres

Arbre de recherche m-aire

Hachage

Méthode d’accès

Page 29: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Structure du fichier

Méthode d'accès du fichier :

Approche utilisée pour localiser un article dans le fichier.

Organisation du fichier :

Comment distinguer un article d'un autre

Structure d’un fichier

Page 30: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Réaction de la méthode aux pannes systèmes

Nombre d'accès disque :

viser un accès

Taux d'occupation:70 % : un bon

compromis

Encombrement et complexité des algorithmes

Mesure d’une structure de fichier

Page 31: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Structure simples de fichiers

T L

O O

F V F V F V F V

Tableau Ordonné, format fixe des articles

Liste non ordonné, format variable des articles, chevauchement non permis

Etc.

Page 32: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

• 2 fichiers sont utilisés : fichier d'index et fichier de données.

• En règle générale, le fichier de données n'est pas trié.

• Fichier de données = Structure simple de fichier non ordonné (tableau ou une liste linéaire chainée).

• Fichier d'index = Tableau ordonné (selon les clés) en mémoire. (recherche dichotomique en mémoire).

Indexes simples

Page 33: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

• Fichier de données non ordonné.

• Fichier d'index ordonné chargé en mémoire dans un tableau (contient toutes les clés)

43 15 18 32 65 12 22 55 58 35 72 78 99 19 93

43

15

18

32

Fichier d’index

Fichier de données

Indexes simples : variante 1

Page 34: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Fichier de données non ordonné.Fichier d’index ordonné maintenu sur le disque (contient toutes les clés)

[ Dense index ]

Fichier d’index

Fichier de données

43 15 18 32 65 12 22 55 58 35 72 78 99 19 93

(12, .) (15,.) (18,.) (19,.) (22, .) (32,.) (35,.) …..

Indexes simples : variante 2

Page 35: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Fichier de données ordonné.Fichier d’index ordonné maintenu sur le disque (ne contient pas toutes les

clés) [ Sparse index ]

13 15 18 32 35 38 53 55 58 68 72 78 93 96 99

(13,.) (32,.) (53,.) (68,.) (93,.)

Fichier d’index

Fichier de données

Indexes simples : variante 3

Page 36: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Méthode d'accès = ARM avec Ordre > 100.

Un nœud = un bloc sur le disque.

Bloc= cluster (unité d’entrée/sortie)

Arbre de recherche m-aire

Avantages:Pas de problème de tailleFichier ordonné

Inconvénients:- Destinés pour les fichiers statiques- Déséquilibre de l’ ARM (Pas de solution Réorganisation périodique

Page 37: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Implémentation des ARM : 2 façons de ranger les articles :

Arbre de recherche m-aire

Si le fichier est grand : utilisation de (ii)

(ii) séparément. Pointeur additionnel vers l'information. (fichier = index vers un fichier de données )

(S1, (Clé1, Article1), S2, ....... , (Clén-1, Articlen-1),Sn)

(i) dans les nœuds avec les clés, (fichier de données = ARM)

(S1, (Clé1, Adresse1), S2, ....... , (Clén-1, Adressen-1),Sn)

Bloc=4KClé= 4 octetsAdresse= 4 octetsSi=4 octetsArticle=200 octets(i) Ordre=20(ii) Ordre= 341

Page 38: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

But : Accélérer l’accès à l’information

Hachage

Une collision apparaît quand plus de b articles ont la même adresse de bloc.

Nécessite une phase d’initialisation de tous les blocs

Méthodes intéressantes sur le disque :- Essai linéaire (Contiguïté physique des blocs)- Chainage séparé (Débordements dans un même cylindre(ou cylindres

voisins)

Avantages - Pas de mémoire pour l'index. - Facilitent les opérations. - Temps d'accès < inférieur à 2. - Efficaces pour les fichiers statiques.

Le fichier = tableau de M blocs // Bloc= b articles.

Inconvénients :Ne répondent pas aux fichiers dynamiquesFichiers désordonnés.

Page 39: Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure d’Informatique (ESI) zegour.esi.dz email: d_zegour@esi.dzd_zegour@esi.dz

Hachage

Chainage séparé

M-1

012

Zone de débordement(même cylindre)

…..

Zone primaire: M blocs

M-1

012

…..

Blocs

Zone primaire et de débordementEssai linéaire