Diaporama n°21

Tableaux associatifs

ou

"Dictionnaires"

Problématique

Associer des "clés" à des "valeurs"

A chaque clé, on associe une valeur

On veut pouvoir accéder/modifier/supprimer à partir des clés

NB : asymétrie : la clé permet d'accéder à la valeur (et pas le contraire)

Exemple : contacts téléphoniques

• clé : numéro de téléphone
• valeur : fiche du contact (nom, prénom, ...)

Type de donnée abstrait DICTIONNAIRE et opérations

• Type paramétrique Dict<K,V> avec K type des clés, V type des valeurs

• est_present(Dict,K) -> bool

• ajouter(Dict,K,V) -> void

• acceder(Dict,K) -> V

• modifier(Dict,K,V) -> void

• supprimer(Dict,K) -> void

NB

On peut voir un tableau "classique" est un dictionnaire particulier :

• les clés sont les indices, les valeurs sont les éléments du tableau

... mais les clés sont rarement des indices entre $0$ et $N-1$ ...

Implémentation d'un dictionnaire

Implémentation par "table de hachage"

(cf plus tard) : astucieux et très efficace

NB : les dictionnaires en Python sont des tables de hachage

implémentation avec une liste chaînée de couples ?

[(clé1, valeur1); (clé2, valeur2); (clé3, valeur3); ...]

Complexité des opérations ?

• ajouter : en $\mathcal{O}(1)$

• accéder, modifier, supprimer : en $\mathcal{O}(n)$ dans le pire des cas

Et si les clés sont ordonnées ?

on aimerait profiter de l'efficacité de la recherche par dichotomie.

Recherche par dichotomie dans une liste chaînée ??

Impossible !

Il faudrait pouvoir accèder au maillon du milieu de la chaîne

et comparer pour chercher dans le début de la chaîne ou dans la fin de la chaîne

C'est un arbre !

Implémentation avec un arbre binaire de recherche

cf cours

NB : les valeurs n'ont pas vraiment d'importance, elles ne font qu'accompagner les clés

NB : les Arbres Binaires de Recherche ne représenteront que l'ensemble des clés