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>
avecK
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