Portail informatique Année 2018 – 2019

CSC 3101 – Algorithmique et langage de programmation

L'objectif de cet exercice est de vous faire manipuler des méthodes d'instance et de vous présenter une nouvelle structure de données particulièrement efficace pour trier et rechercher des éléments : les arbres binaires de recherche.

Durée des exercices obligatoires : 2h10 en présentiel + 20mn en hors présentiel
Dans cet exercice, nous concevons une petite banque en nous focalisant sur le problème de la recherche rapide d'un client à partir de son nom. Ce problème de recherche rapide est assez général : n'importe quelle application Web comme Facebook doit retrouver un compte à partir d'un identifiant de connexion.

À haut niveau, le problème du stockage des clients d'une banque est assez similaire au problème du stockage des monstres dans une armée de monstres. Puisque le nombre de clients d'une banque est non connu et non borné, nous avons jusqu'à maintenant vu qu'on pouvait stocker les clients dans un tableau extensible ou dans une liste chaînée. Aucune de ces deux structures n'est adéquate :

Comme aucune des structures de données que nous avons étudiées jusqu'à maintenant n'est adéquate, nous vous présentons les arbres binaires de recherche dans ce TP. Cette structure de données a l'avantage de pouvoir gérer un nombre non borné d'éléments tout en étant efficace lors de l'ajout ou de la recherche d'éléments. L'algorithme que nous allons étudier dans ce TP est (relativement) simple à mettre en œuvre, mais peut poser des problèmes d'inefficacité que nous vous présentons en fin d'exercice. Pour palier ces problèmes d'inefficacité, il existe les arbres rouge-noirs ou les arbres 2-3-4, et nous invitons les étudiants curieux et amateurs de jolis algorithmes à aller les étudier.

Pour les étudiants qui savent déjà programmer en objet, vous remarquerez que nous n'utilisons pas de constructeurs puisque nous n'avons pas encore étudié cette notion. La façon de créer un objet pourra donc vous paraître étonnante et contre-intuitive. Si vous connaissez déjà les constructeurs, n'hésitez pas à adapter l'énoncé de façon à les utiliser à la place des méthodes statiques nommées create. Dans un premier temps, nous nous focalisons sur la conception des comptes des clients de la banque. Cet exercice a pour but de vous faire manipuler des méthodes d'instances dans un cadre conceptuel simple. Pour cela, nous commençons par utiliser des méthodes de classe, puis nous modifions le code de façon à les remplacer par des méthodes d'instance. Commencez par créer un projet nommé bank contenant une classe nommée Main appartenant au package tsp.bank. Ajoutez une méthode de classe main à la classe Main et vérifiez que vous êtes capable d'exécuter votre programme. Dans le package tsp.bank, créez une classe Account possédant les champs suivants :
  • name : cette chaîne de caractères indique le nom du propriétaire du compte en banque,
  • balance : ce nombre de type double indique le solde du compte.
Ajoutez une méthode de classe (mot clé static) nommée create à la classe Account. Cette méthode doit prendre en paramètre une chaîne de caractères indiquant le nom d'un compte. Elle doit renvoyer un compte associé à ce nom et, comme votre banque est bien sympathique, le solde du compte doit être initialisé avec un montant aléatoire compris entre 0 et 100 euros arrondi à l'entier précédent. Pour cela, vous pouvez utiliser les méthodes de classe :
  • Math.random() qui renvoie un nombre flottant (double) compris entre 0 et 1,
  • Math.floor(double d) qui renvoie la partie entière du nombre flottant d.

Vous pouvez trouver l'ensemble des méthodes de la bibliothèques Java ici. Pour vous promener dans cette documentation, vous avez la liste des packages en haut à gauche, la liste des classes d'un package en bas à gauche et une description exhaustive de la classe à droite. À part au cours des deux dernières séances, vous ne devriez que avoir besoin que de vous promener dans le package java.lang (la classe Math se trouve dans ce package).

Cette documentation, appelée la javadoc, est particulièrement commode et son existence est l'une des raisons qui explique le succès de Java. Nous vous conseillons d'enregistrer l'adresse de cette documentation dans un favori. Pour la retrouver, vous pouvez aussi chercher javadoc 8 dans un moteur de recherche.
En vous inspirant de ce que vous avez fait au CI3, ajoutez une méthode de classe (mot clé static) nommée display à la classe Account. Cette méthode doit afficher "nom: € solde", où nom est le nom du propriétaire du compte et solde son solde.

Utilisez bien une méthode de classe ici, le but étant de vous montrer dans la question suivante comment on peut la convertir en méthode d'instance.

Dans la méthode main, utilisez create pour créer le compte en banque associé au client nommé Tyrion, puis display pour afficher les richesses durement acquises par ce client.
Convertissez maintenant la méthode display en méthode d'instance. Pour cela, commencez par supprimer le mot clé static et corrigez ensuite les erreurs introduites par cette modification.

Bien qu'apparemment simple, cette question est absolument essentielle dans ce cours ! Vous devez prendre le temps de comprendre ce que vous faîtes car vous êtes en train de passer de la programmation impérative à la programmation orientée objet. Si vous ratez cette marche, le reste du module risque de vous sembler bien difficile...

À partir de cette question et jusqu'à la fin du module, nous vous demandons de ne plus jamais utiliser de méthodes de classe sauf dans deux cas particuliers :
  • pour la méthode main qui permet de démarrer votre application,
  • pour les méthodes create qui permettent d'allouer et d'initialiser des objets (vous verrez au cours suivant une façon plus élégante d'initialiser un objet).
Pour rechercher les comptes, nous allons les trier. Le tri que nous utilisons est lexicographique sur le nom du propriétaire du compte. Nous vous demandons donc d'ajouter une méthode d'instance int compareTo(String name) à la classe Account qui renvoie :
  • un nombre positif si le propriétaire du compte est plus grand que name (en suivant l'ordre lexicographique),
  • 0 si le propriétaire est égal à name,
  • un nombre négatif sinon.

Pour vous aider, il s'avère que les chaînes de caractères sont des objets en Java, et que la classe String fournit une méthode d'instance int compareTo(String name) renvoyant le résultat de la comparaison lexicographique entre this et name (voir la documentation de java.lang.String).

Vérifier que votre code est correct en comparant, dans la méthode main, le compte de Tyrion avec les chaînes de caractères "Daenerys" (résultat positif), "Tyrion" (résultat égal à zéro) et "Ygrid" (résultat négatif).
Félicitations, vous venez de créer votre premier objet dans le sens de la programmation orientée objet !
Maintenant que vous avez conçu les comptes, vous pouvez construire une banque pour stocker les comptes.

Pour cela, nous vous proposons d'utiliser un arbre binaire de recherche. De façon générale, un arbre binaire est constitué de nœuds et chaque nœud possède deux fils : un fils gauche et un fils droit.

Pour un arbre binaire de recherche, chaque nœud est étiqueté par une valeur définie sur un ensemble totalement ordonné. Dans notre cas, il s'agit d'un compte en banque, et l'ordre utilisé est l'ordre lexicographique sur les noms des propriétaires des comptes. Le principe d'un arbre binaire de recherche est que les étiquettes se trouvant sous le fils gauche (inclus) d'un nœud soient toutes plus petites que l'étiquette du nœud, et que celle se trouvant sous le fils droit (inclus) soient toutes plus grandes.

La figure ci-dessous illustre le principe. Si on prend, par exemple, le nœud étiqueté par le compte de Jaime, on peut constater que les nœuds se trouvant à gauche sont plus petits et que ceux se trouvant à droite sont plus grands.

[Tyrion] / \ [Jaime] [Tywin] / \ \ [Cersei] [Kevan] [Willem] / \ [Alton] [Lancel] \ [Martyn]

De façon à simplifier le code, nous considérons aussi des nœud dits vides qui ne sont pas représentés sur la figure. Un nœud vide est un nœud dont l'étiquette est la référence null. Par opposition, nous considérons qu'un nœud est non vide si son étiquette est différente de la référence null.

Dans notre mise en œuvre, un nœud non vide possède toujours deux fils, ces derniers pouvant être vide ou non vide. Si le fils est un nœud vide, c'est que ce fils n'existe pas et que nous sommes en bas de l'arbre. Par exemple, dans l'exemple ci-dessus, le nœud non vide étiqueté avec le compte de Cersei possède deux fils : celui de gauche est un nœud non vide et celui de droite est un nœud vide non représenté dans la figure. Commencez par supprimer tout le code se trouvant à l'intérieur de la méthode main de la classe Main. Dans le package tsp.bank, définissez une classe nommée Node déclarant trois champs : une étiquette (du type Account), un fils gauche (du type Node) et un fils droit (du type Node). Ajoutez à cette classe une méthode de classe nommée create. Cette méthode sans paramètre doit renvoyer un nouveau nœud vide, c'est-à-dire un nœud ayant une étiquette égale à null et ayant deux fils égaux à null. Dans le package tsp.bank, définissez une classe nommée Bank déclarant un unique champ nommé root de type Node. Ce champ représente la racine de l'arbre binaire de recherche. Ajoutez à cette classe une méthode de classe nommée create. Cette méthode sans paramètre doit renvoyer une nouvelle banque, c'est-à-dire une banque dont la racine est un nouveau nœud vide (un nœud ayant une étiquette égale à null). Ajoutez à la classe Node une méthode d'instance nommée lookupOrCreate prenant un nom (une chaîne de caractères) en paramètre et renvoyant un compte (Account). À terme, cette méthode va renvoyer le compte associé au nom et, si ce compte n'existe pas, le créer, l'enregistrer dans la banque et le renvoyer. À cette question, avant de se lancer dans cette mise en œuvre complexe, la méthode lookupOrCreate doit simplement afficher le nom passé en paramètre et renvoyer la référence null.

Après avoir écrit cette version simplifiée de Node.lookupOrCreate, ajoutez à la classe Bank une méthode d'instance nommée lookupOrCreate prenant un nom en paramètre. Cette méthode doit appeler lookupOrCreate sur la racine de la banque.

Enfin, dans la méthode Main.main, vérifiez que l'enchaînement de vos méthodes est correct en :
  • créant une nouvelle banque,
  • appelant lookupOrCreate avec comme paramètre la chaîne de caractères "Tyrion".
Le code est maintenant suffisamment avancé pour que vous puissiez ajouter des comptes à votre arbre binaire de recherche. Complétez le code de Node.lookupOrCreate de façon à (i) renvoyer le compte si il existe en parcourant l'arbre ou (ii) ajouter le compte à la banque avant de le renvoyer, en vous assurant que votre arbre est toujours un arbre binaire de recherche, c'est-à-dire que les nœuds de gauche d'un nœud sont toujours plus petits et que ceux de droite sont toujours plus grands.

Cette question est relativement complexe et il est donc normal que vous y passiez un peu de temps. N'oubliez pas que les feuilles de l'arbre sont représentées par des nœuds vide, c'est-à-dire des nœuds ayant une étiquette égale à null.

Nous vous conseillons de mettre en œuvre votre algorithme de façon récursive, en commençant par vous focaliser sur le problème de la recherche. Si à la fin d'une recherche, vous n'avez pas trouvé le compte, il suffit de l'ajouter comme enfant du nœud vide sur lequel votre recherche termine puisque, si le nœud existait, il se trouverait à cet endroit là. En détail, vous devez traiter plusieurs cas.
  • Si l'étiquette du compte du nœud courant (this) est non vide, vous avez trois choix :
    • Si l'étiquette du compte est strictement plus petite que le nom passé en paramètre, c'est que le compte - s'il existe - se trouve à droite. Vous devez donc renvoyer le résultat de l'appel à lookupOrCreate sur le nœud droite.
    • Si l'étiquette du compte est strictement plus grande, c'est que le compte - s'il existe - se trouve à gauche,
    • Sinon, c'est que l'étiquette du compte est égale au nom passé en paramètre. Vous avez donc trouvé le compte associé au nom passé en paramètre et il suffit de renvoyer l'étiquette (le compte) référencé par le nœud courant.
  • Sinon, c'est que vous êtes arrivé en bas de l'arbre sans avoir trouvé le compte associé au paramètre. Vous devez donc transformer le nœud courant qui est vide en un nœud non vide associé à un nouveau compte, lui même associé au nom passé en paramètre. Techniquement, vous devez :
    • allouer un nouveau nœud vide et l'associer au champ gauche du nœud courant,
    • allouer un nouveau nœud vide et l'associer au champ droite du nœud courant,
    • créer un compte associé au nom passé en paramètre, l'associer au champ étiquette du nœud courant et enfin renvoyer ce nouveau compte.
Afin de vérifier que votre code est correct, utilisez lookupOrCreate pour ajouter des comptes associés aux utilisateurs suivants : "Tyrion", "Jaime", "Cersei", "Tywin", "Kevan", "Lancel", "Alton", "Martyn", "Willem".

Ajoutez ensuite des méthodes display aux classes Bank et Node, et parcourez l'arbre binaire de recherche de façon à afficher les comptes dans l'ordre lexicographique.
Modifier votre programme de façon à ce qu'un compte soit décalé d'autant d'espace que sa profondeur dans l'arbre. Si votre programme est correct, vous devriez obtenir l'affichage suivant (aux soldes près) : Alton: € 54.0 Cersei: € 63.0 Jaime: € 15.0 Kevan: € 48.0 Lancel: € 70.0 Martyn: € 32.0 Tyrion: € 2.0 Tywin: € 75.0 Willem: € 6.0 Félicitations, vous venez de mettre en œuvre votre premier programme objet complexe !
Sur papier, dessinez l'arbre que vous obtiendriez si vous ajoutiez les comptes dans cet ordre : "Alton", "Cersei", "Jaime", "Kevan", "Lancel", "Martyn", "Tyrion", "Tywin", "Willem" (pour les courageux qui ont fait la question bonus de l'exercice précédent, vous pouvez directement visualiser votre arbre). Quelle est, dans ce cas précis, la complexité moyenne d'une recherche de compte en terme de nombre de nœuds traversés dans l'arbre ? Il faut savoir que les arbres rouge-noirs et les arbres 2-3-4 corrigent ce défaut et que ce sont ces arbres qui sont utilisés en pratique aujourd'hui. Alton: € 29.0 Cersei: € 5.0 Jaime: € 35.0 Kevan: € 6.0 Lancel: € 66.0 Martyn: € 69.0 Tyrion: € 68.0 Tywin: € 32.0 Willem: € 68.0

L'arbre est clairement non équilibré et la complexité moyenne est de N/2 comme pour les listes chaînées.