Un arbre n-aire est un arbre dans lequel chaque noeud a un nombre quelconque de fils. On peut utiliser un arbre n-aire pour représenter un dictionnaire et ainsi accélérer la recherche. La racine a autant de fils que de premières lettres possibles, puis chacun de ces fils autant de fils que de seconde lettre possible, etc. Pour représenter un tel arbre, une solution consiste à attacher à chaque noeud deux liens : un lien vers son premier fils et un lien vers son frère.
- Assurez-vous que vous disposez de la ressource arbre. Au besoin, consultez la page Ressources.
- La classe Dictionnaire propose un constructeur sans paramètre. Combien de champs sont nécessaires à la représentation d’une instance de cette classe ?
- La fonction void ajouter(String) permet d’ajouter un mot dans le dictionnaire. Ajoutez le mot BU dans le dictionnaire et fixez votre attention sur l’évolution du schéma mémoire. Que s’est-il passé ?
- Que se passe-t-il si on ajoute un nouveau mot commençant par une autre lettre, comme par exemple AIR ?
- Que se passe-t-il si on ajoute à nouveau un mot existant, comme BU ou AIR ?
- Pour être sûr d’avoir bien compris ce qui se passe, ajoutez un troisième mot commençant encore par une autre lettre. Choisissez un mot court pour éviter d’encombrer le schéma. Que se passe-t-il ?
- La fonction boolean contient(String mot) permet de vérifier l’appartenance d’un mot au dictionnaire. Combien d’instances de Node vont être explorées lors de la recherche du mot AIR ?
- Que se passe-t-il maintenant si on ajoute un mot qui commence par une lettre déjà enregistrée, BOL par exemple ?
- Suivez attentivement ce qui se passe si on ajoute un nouveau mot comme BON.
- Après ces différentes adjonctions, le test d’appartenance du mot AIR nécessite-t-il plus ou autant d’exploration de noeuds ?