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

image.png

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