Série 7 – Ensembles par arbres de recherche

Le but de cette série, la troisième du mini-projet collections, est de terminer la classe TreeSet qui met en œuvre un ensemble au moyen d'un arbre binaire de recherche.

Pour démarrer, nous vous fournissons une archive Zip contenant la totalité du code donné dans le cours, sous une forme légèrement améliorée.

Avant de commencer à compléter la classe TreeSet, il convient de créer une classe de test pour elle.

Cela devrait se faire facilement puisque la classe abstraite SetTest, fournie et déjà utilisée la semaine dernière, contient des méthodes de test pour n'importe quelle classe implémentant l'interface Set. Seule une de ses méthodes est abstraite, newSet, son but étant de créer une instance de la classe d'ensemble à tester.

Normalement, il suffirait donc de définir une nouvelle sous-classe de SetTest, nommée TreeSetTest, et d'écrire le code (trivial) de la méthode newSet pour obtenir une classe de test pour TreeSet. Malheureusement, en essayant de faire cela, vous rencontrerez un problème nécessitant une légère adaptation de la classe SetTest et de ses sous-classes.

Faites cette adaptation et exécutez ensuite votre classe TreeSetTest comme test JUnit. Seuls trois tests sur 13 devraient s'exécuter correctement.

Ecrivez le code de la méthode d'ajout, add, en vous basant sur la description donnée dans le cours et en vous aidant de la méthode auxiliaire nodeOrParentFor. Utilisez de plus à bon escient les différents constructeurs de la classe Node qui vous permettent de simplifier votre code.

Comme toujours, relancez les tests après avoir écrit votre méthode afin de vérifier que ceux qui la concernent passent désormais.

Ecrivez le code de la méthode de suppression, remove, en vous basant sur la description donnée dans le cours. Aidez-vous cette fois des méthodes nodeFor et successor. Notez que la méthode successor fournie est plus générale — donc son code plus complexe — que celle donnée dans le cours, puisqu'elle fonctionne également dans le cas où le nœud qu'on lui passe n'a pas de fils droit. Cela n'est pas nécessaire pour la méthode remove, mais très utile pour mettre en œuvre l'itération.

Ecrivez le code de la méthode d'itération, iterator.

L'itérateur retourné par cette méthode n'est pas aussi difficile à écrire qu'il n'y paraît. En effet, la méthode successor mentionnée ci-dessus retourne le successeur de n'importe quel nœud. C'est-à-dire que, étant donné un nœud, elle retourne le nœud contenant le plus petit élément plus grand que celui du nœud en question, ou null si ce nœud contient le plus grand élément de l'ensemble.

Ainsi, l'itérateur peut conserver une référence vers le prochain nœud à retourner lors de l'itération. Initialement, elle désigne le nœud contenant le plus petit élément de l'ensemble, c-à-d celui situé « en bas à gauche » de l'arbre. Ensuite, à chaque appel à next, un simple appel à successor permet de mettre à jour cette référence.

Notez au demeurant que, comme cela a été dit au cours, cet itérateur produit les éléments de l'ensemble dans l'ordre.

Pour mettre en œuvre la méthode remove de l'itérateur, il faut conserver une référence vers le dernier nœud visité par next. Sa suppression se fait facilement si on prend soin d'extraire la plus grosse partie de la méthode remove de la classe TreeSet dans une méthode auxiliaire nommée p.ex. removeNode et supprimant un nœud donné. Une fois cela fait, la méthode remove de l'itérateur peut simplement appeler removeNode sur le dernier nœud visité par next.