Enoncé 6 : Hachage interne - Arbres  Corrigé 6

Problème : Une version du chaînage séparé

Soit la table suivante construite par la technique du chaînage séparé :

h(e) = 0

h(a) = h(f) = h(g) = 1

h(b) = 2

h(c) = h(h) = h(i) = h(j) = i

h(d) = h(k) = M-1

- Définir la structure ci-dessus et dire comment l'initialiser.

- Ecrire le module de recherche R d'un élément donné dans une table ainsi organisée.

- Définir les paramètres nécessaires de R puis l'utiliser pour développer l'algorithme d'insertion I.

- De même, utiliser R pour écrire l'algorithme de suppression S.

- Quelles modifications apportées aux algorithmes R, I et S si on considère que la liste des débordements est maintenue ordonnée. On appellera les nouveaux algorithmes R', I' et S'.

Une autre méthode de résolution de collision consiste à garder les débordements dans un arbre de recherche binaire au lieu d'une liste linéaire chaînée.

- Ecrire le module de recherche R".

- Définir les paramètres nécessaires de R" puis l'utiliser pour développer l'algorithme d'insertion I".

- De même, utiliser R" pour écrire l'algorithme de suppression S".

- Donner une estimation du temps moyen de recherche d'une donnée en fonction du nombre de données insérées pour les algorithmes R, R' et R".