Structures de données avancées : Introduction Pr ZEGOUR DJAMEL EDDINE Ecole Supérieure...

Structures de données avancées : Introduction

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

zegour.esi.dz email: d_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

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

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

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

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

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

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

Tableaux, listes

Graphes

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

Arbre de recherche binaire

Hachage

Structures de données en RAM

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.

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.

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

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

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

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

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

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.

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

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 .

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

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

Hachage : Synthèse

Données statiques

S > C > D > L

Pas d’ordre

Insertions contrôlées

Pré-requis : Structures de fichiers

Structure d’un disque

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

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

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

Tableaux, listes

Indexes simples

B-arbres

Arbre de recherche m-aire

Hachage

Méthode d’accès

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

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

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.

• 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

• 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

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

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

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

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

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.

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