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

Exercice 1 : obligatoire (facile, ∼45mn)
Exercice 2 : obligatoire (difficile, ∼1h45)
Exercice 3 : entraînement (facile, ∼10mn)
Exercice 4 : entraînement (difficile)

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 :

Un tableau extensible est inadéquat, car une banque possède un grand nombre (non borné) de clients. Comme vu en CI3, si on utilisait un tableau extensible pour stocker nos clients, on prendrait alors le risque de devoir étendre (et donc copier) un immense tableau lors de l'ajout d'un nouveau client, ce qui grèverait les performances.
Une liste chaînée est inadéquate, car cette structure est particulièrement inefficace pour effectuer une recherche. En effet, avec une liste chaînée, le seul moyen d'atteindre le n^ième élément de la liste est de traverser exhaustivement les n-1 nœuds précédents. Si la liste chaînée possède N nœuds et si les recherches sont équitablement réparties sur l'ensemble des clients, il faudrait donc, en moyenne, parcourir N/2 nœuds avant de trouver un client. Si N est très grand, cette complexité ruine les performances.

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 rouges-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.

Les comptes (∼45mn – facile – obligatoire)

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 IronBank appartenant au package tsp.bank. Ajoutez une méthode de classe main à la classe IronBank 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èque 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 qu'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.

Cette question a pour but de convertir la méthode display en méthode d'instance. Pour cela, il faut commencer par supprimer le mot clé static et par supprimer le paramètre de façon à utiliser le paramètre implicite this. La déclaration de la méthode display doit donc être la suivante

void display() { ... }

Une fois la déclaration de la méthode display modifiée, corriger les erreurs introduites par cette modification dans le reste du programme.

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).

Account.java

Félicitations, vous venez de créer votre premier objet dans le sens de la programmation orientée objet !

La banque (∼1h45 – difficile – obligatoire)

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œuds 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 vides ou non vides. 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 IronBank.

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 renvoyer le résultat de l'appel à lookupOrCreate sur la racine de la banque.

Enfin, dans la méthode IronBank.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 s'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.

Quelle est la complexité de lookupOrCreate dans le pire des cas en fonction du nombre de nœuds dans l'arbre ? À quoi correspond ce pire des cas ?

La complexité est linéaire dans le pire des cas. Il correspond au cas où l'arbre forme une simple liste chaînée, c'est-à-dire que l'on a toujours inséré des éléments plus petits ou plus grands que les précédents. Dans ce cas, soit le fils gauche est toujours vide, soit le fils droit est toujours vide.
Cependant, en moyenne, la fonction a une complexité en

\mathcal{O}(log(n))

, ce qui explique l'attrait pour cette structure.

bonus

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 !

Discussion (∼10mn en hors présentiel – moyen – entraînement)

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.

Pour aller plus loin (entraînement)

Écrivez une fonction pour dire si le nœud actuel est une feuille ou non.

Écrivez une fonction qui compte le nombre de nœuds dans l'arbre. On ne compte pas les feuilles.

Une notion commune pour les arbres s'appelle la hauteur. Il s'agit de la distance maximale entre le nœud racine et une feuille. Par exemple, l'arbre donné en exemple plus haut a une hauteur de 5 (n'oubliez pas les feuilles qui sont des nœuds vides et que nous n'affichons pas). Écrivez une fonction donnant la hauteur d'un arbre.
La hauteur d'un arbre peut-être calculée de manière récursive.

Le arbre binaire de recherche est le plus efficace lorsque sa hauteur est minimale. Quelle est la hauteur minimale d'un arbre de recherche binaire contenant n nœuds ?

La hauteur optimale est fonction du logarithme:

\lfloor log_2(n) \rfloor

. En effet, le nombre de nœuds que l'on peut stocker à une profondeur p donnée est :

2^{p}

Et donc on a un total de nœuds maximum à la profondeur p ou moins de :

2^{p + 1} - 1

Si on a :

2^{k} \leq n + 1 < 2^{k + 1}

Il faudra bien une hauteur de :

k = l o g (n)

Cela explique pourquoi, avec un bon arbre, les opérations comme l'addition, la recherche et la suppression se font en temps logarithmique.

Un arbre est dit équilibré lorsque sa hauteur est minimale, i.e., pour chaque nœud, la hauteur du fils de droite et de gauche ne diffère au plus d'un. Écrivez une fonction pour vérifier que l'arbre est équilibré.

Sachant qu'un arbre est équilibré, quelle est la complexité de lookupOrCreate ?

Dans ce cas, la complexité est en

\mathcal{O}(log(n))

car la hauteur d'un arbre équilibré est logarithmique.

Écrivez une fonction pour obtenir la valeur maximale et minimale d'un arbre. On fera attention aux nœuds feuilles qui ne doivent pas être considérés. Dans l'exemple plus haut, le minimum est Alton et le maximum est Willem.

Écrivez une fonction delete qui supprime une personne de la banque. Attention, le résultat doit rester un arbre binaire de recherche. Pour cela, il va vous falloir considérer plusieurs cas de figure. Un dessin peut vous aider.

Les cas à considérer sont les suivants:

Les deux fils du nœud à supprimer sont des feuilles. Alors, il faut remplacer le nœud à supprimer par une feuille.
Un seul fils du nœud à supprimer est une feuille. On fait alors remontrer le fils non-feuille d'un niveau.
Les deux fils ne sont pas des feuilles. On remplace alors le nœud à supprimer par le minimum du fils de gauche (ou le maximum du fils de droite) et on supprime ce nouveau nœud du fils.

Quelle est la complexité de la fonction delete en fonction du nombre de nœuds dans l'arbre dans le pire des cas ?

Comme pour l'ajout, la complexité est linéaire dans le cas où l'arbre forme une ligne droite et où il faut supprimer un nœud tout en bas.

Quand on passe sur tous les nœuds d'un arbre, on dit qu'on parcourt l'arbre. À la suite de ce parcours, on obtient une liste d'éléments dont l'ordre dépend de l'ordre dans lequel on insère la représentation du nœud actuel, du fils de gauche, et du fils de droite. Cela définit trois types de parcours:

Préfixe : on insère, dans l'ordre, le nœud actuel, la représentation du fils de gauche et la représentation du fils de droite.
Infixe : on insère, dans l'ordre, la représentation du fils de gauche, le nœud actuel et la représentation du fils de droite.
Postfixe : on insère, dans l'ordre, la représentation du fils de gauche, la représentation du fils de droite et le nœud actuel.

Par exemple, pour l'exemple plus haut, nous avons les parcours suivants:

Préfixe : Tyrion -> Jaime -> Cersei -> Alton -> Kevan -> Lancel -> Martyn -> Tywin -> Willem
Infixe : Alton -> Cersei -> Jaime -> Kevan -> Lancel -> Martyn -> Tyrion -> Tywin -> Willem
Postfixe : Alton -> Cersei -> Martyn -> Lancel -> Kevan -> Jaime -> Willem -> Tywin -> Tyrion

Nous allons réutiliser les listes chaînées introduites au dernier TP pour représenter les parcours. Pour commencer, récupérez le code implémenté au dernier CI. Il va falloir renommer le Node car il entre en conflit avec nos arbres. Appelez-le LinkedList et modifiez le code pour renommer tous les types. Ensuite, transformez les méthodes de classe en méthodes d'instance (sauf les méthodes servant à créer les listes). Faites en sorte que le type de la liste soit Account. Il vous faudra supprimer des méthodes qui ne peuvent plus fonctionner.

Implémentez les trois types de parcours. Ils doivent retourner une liste chaînée des Accounts.

Quelle propriété intéressante remarquez-vous pour le parcours infixe ?

On obtient les éléments triés !

Étant donnée une liste chaînée triée, ajoutez à la classe LinkedList une fonction pour créer un arbre binaire de recherche équilibré. Quelle est la complexité de cet algorithme ?
On pourra utiliser une fonction auxiliary récursive.

Notre fonction auxiliaire cherche le milieu (opération linéaire) et appelle deux fois la fonction auxiliaire sur des sous-listes deux fois plus petites. On a donc l'équation de récurrence:

C(n) = 2 * C(\frac{n}{2}) + n

Cela nous donne une complexité finale en

\mathcal{O}(n*log(n))

Écrivez une fonction qui équilibre un arbre binaire de recherche.

Node.java

IronBank.java

LinkedList.java