emacs& depuis un des PCs des autres
salles : slogin machine, où machine est un
des noms suivants : femur phalange radius rotule tibia axis
tarse perone cubitus metacarp acromion sacrum cote ain allier ardennes
carmor charente cher creuse dordogne doubs essonne finistere gironde
indre jura landes loire manche marne mayenne morbihan moselle saone
somme vendee vosges).
Le but du TP est de construire un dictionnaire grâce à un
arbre de recherche. On va définir une classe Dico
permettant de stocker un ensemble de mots et de tester si
un mot donné est dans cet ensemble.
Dans un arbre de recherche, les éléments sont stockés dans les noeuds d'un arbre binaire vérifiant toujours la propriété suivante :
e, tous les
noeuds du sous-arbre gauche ont des éléments inférieurs à
e et tous les noeuds du sous-arbre droit ont des
éléments supérieurs à e.
String sont supposés totalement ordonnés.
compareTo
de la classe String ainsi : quand s
et t sont des String,
if (s.compareTo (t) < 0) ... // s < t dans l'ordre alphabétique
if (s.compareTo (t) == 0) ... // s = t
if (s.compareTo (t) > 0) ... // s > t dans l'ordre alphabétique
Noeud, maillon de base pour
construire les arbres décrits ci-dessus.
Dico qui contient un arbre
binaire de recherche pour stocker des mots. L'arbre est originellement
vide.
Ajouter les méthodes suivantes dans la classe Dico :
Dico () qui renvoie un dictionnaire vide.
public static void inserer (Dico d, String m)
qui permet d'insérer un mot dans le dictionnaire ; on pourra
utiliser une méthode
static Noeud insererArbre (Noeud n, String m).
public static boolean existe (Dico d, String m)
qui permet de tester si un mot est dans le dictionnaire.
O(h)
où h est la hauteur de l'arbre. Idéalement,
h=log2n où n est le nombre de
mots dans l'arbre.
On veut analyser la hauteur des arbres obtenus sur un jeu de dictionnaires tests.
static int hauteur (Dico d)
permettant de calculer la hauteur de l'arbre d'un dictionnaire.
Ajouter une méthode static int taille (Dico d)
permettant de calculer le nombre de mots d'un dictionnaire.
h
en fonction de log2n obtenue pour les fichiers suivants :
~viennot/dicos/francais.3court (30 mots) ~viennot/dicos/francais.3 (347 mots) ~viennot/dicos/francais.4 (979 mots) ~viennot/dicos/francais.5 (2181 mots) ~viennot/dicos/francais.6 (4017 mots) ... et ~viennot/dicos/francais.tout (47509 mots)On pourra se servir du programme LireDicos.java en exécutant
java LireDicos ~viennot/dicos/francais.[1-9]*
et java LireDicos ~viennot/dicos/francais.tout. Dessiner ensuite
à la main la courbe obtenue.
Noeud et Dico
pour que l'arbre du dictionnaire soit toujours équilibré selon le
fonctionnement des arbres AVL. Comparer les hauteurs d'arbre
obtenues sur les fichiers tests de 2.2.
Question subsidiaire : écrire une méthode pour supprimer un mot du dictionnaire.