0. Introduction

On a vu au TD6 que les arbres binaires permettent de représenter de manière simple et efficace des expressions arithmétiques telles que (2+3)-5. Mais les arbres et en particulier les arbres binaires peuvent être utilisés pour beaucoup d'autres applications. Ce TD aborde une application fondamentale pour l'informatique : l'arbre de recherche.

On dit qu'un arbre dit de recherche est défini comme un arbre binaire tel que l'étiquette d'un noeud est comprise entre les étiquettes de son fils gauche et celles de son fils droit. Une définition plus formelle est la suivante :

Un arbre binaire a est un arbre binaire de recherche si, pour tout noeud s de a, les contenus des noeuds du sous-arbre binaire gauche de s sont strictement inférieurs au contenu de s, et que les contenus des noeuds du sous-arbre droit de s sont strictement supérieurs au contenu de s. Voici un exemple d'arbre de recherche :

Un arbre de recherche encode un ensemble d'entiers, si toutes ses étiquettes sont distinctes. On se place désormais dans ce cas qui revient à considérer des comparaisons strictes dans la définition des arbres de recherche. Par exemple, l'arbre suivant n'encode pas un ensemble car il contient deux fois l'entier 3.

L'intérêt des arbres (par rapport aux listes) est que la recherche d'un élément ou son ajout prend un temps proportionnel à la hauteur de l'arbre (pour les listes c'est le cardinal de l'ensemble). Or, cette hauteur a de bonnes chances d'être de l'ordre de log(N) où N est le cardinal de l'ensemble encodé. En fait, nous désirons fortement que la hauteur de l'arbre de recherche soit log(N) et c'est ce souhait qui nous amène au concept traité dans ce TD, les arbres équilibrés.

Nous allons considérer une famille particulière d'arbres équilibrés : les arbres AVL. Dans ce TD nous allons travailler avec ce type d'arbre parce que leur programmation peut être menée jusqu'au bout, et parce que les principes utilisés dans leur gestion se retrouvent dans d'autres familles plus complexes.

Nous définissons un arbre AVL de la fac§on suivante :

Un arbre binaire est un arbre AVL si, pour tout noeud de l'arbre, les hauteurs des sous-arbres gauche et droit diffèrent d'au plus 1.

Curiosité : la famille des arbres AVL est nommée ainsi d'après leurs inventeurs Adel'son-Velskii et Landis, qui les ont présentés en 1962.

0.1 Au cours de ce TD, nous allons :

0.2 Pré-requis et indices pour la résolution des exercices de ce TD

Il est important que vous respectiez les règles suivantes :

1. Echauffement : les arbres binaires et les interfaces

Au cours de ce TD, nous allons construire des arbres de recherche. Nous utilisons le mécanisme d'interfaces de Java, qui a été discuté en amphithéâtre et au TD6, pour les visualiser en utilisant le meme outil que au TD6. Téléchargez donc le fichier TreeDraw.java, contenant une petite classe Java servant à afficher graphiquement une représentation de tout arbre binaire - donc les arbres binaires du TD6 et les arbres AVL de ce TD.

1.1 Interface TreeElem

On se rappele que pour que TreeDraw puisse afficher un arbre binaire, l'arbre doit implémenter l'interface TreeElem. Donc, comme en TD6, nous allons créer un ficher TreeElem.java avec le contenu suivant:

	interface TreeElem{
	
	   public String label();
	   public TreeElem getLeft();
	   public TreeElem getRight();   
	}

Comme en TD6, les méthodes dans l'interface TreeElem répondent à la spécification suivante:

un constructeur AVL(int valeur, AVL left, AVL right).

Le code suivant permet de tester le constructeur et l'affichage:

   public static void main(String[] args){
      AVL l = new AVL(3, new AVL(3, null, null), new AVL(12, new AVL(8, null, null), new AVL(13,null,null)));
      AVL r = new AVL(25, new AVL(21, null, null), new AVL(28, null,l));
      AVL a = new AVL(20, l, r);
      TreeDraw.drawTree(a);		
   }

Vous devriez obtenir le résultat suivant :

Cet arbre, est-il un arbre binaire de recherche ou pas?

Déposez votre implémentation de AVL.java ici:

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

1.3 Hauteur d'un Arbre

Ajouter à la classe AVL la fonction statique suivante : static int hauteur(AVL a) qui retourne la hauteur d'un arbre, tout en respectant qu'un arbre vide a la hauteur 0, et une feuille est un arbre de hauteur 1.

Vous pouvez tester votre implémentation en ajoutant à la fin de public static void main(String[] args) la ligne suivante :

   System.out.println("Tree height: "+ AVL.hauteur(a));

Vous devriez obtenir le résultat suivant :

   Tree height: 6

Déposez votre implémentation de AVL.java ici:

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

1.4 Copier des arbres

Ajouter une fonction récursive static AVL copier (AVL a) à la classe AVL qui retournera une copie de l'arbre (c'est-à-dire une copie de tous les noeuds de l'arbre).

Vous pouvez tester votre implémentation en ajoutant a la fin de public static void main(String[] args) les lignes suivante :

   AVL b = AVL.copier(a);
   b.left=null;
   TreeDraw.drawTree(a);
   TreeDraw.drawTree(b);

Vous devriez obtenir le résultat suivant (deux fenêtres):

Déposez votre implémentation de AVL.java ici:

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2. Arbre Binaire de Recherche

L'arbre obtenu dans l'exercice précèdent n'est pas un arbre binaire de recherche pour les raisons suivantes:

la condition que pour tout noeud s de a, les contenus des noeuds du sous-arbre binaire gauche de s soient strictement inférieurs au contenu de s, et que les contenus des noeuds du sous-arbre droit de s soient strictement supérieurs au contenu de s n'est pas remplie.

2.1 Ajouter un Elément dans un Arbre Binaire de Recherche

Dans cet exercice, nous allons ajouter à notre classe AVL une fonction statique static AVL ajouter(AVL a, int i) qui ajoute l'entier i à la bonne place dans l'arbre a et qui nous retourne l'arbre résultant - qui doit être un arbre binaire de recherche. L'opération ajouter dans un arbre binaire de recherche a aussi été presenté en amphi

Le code suivant permet de tester votre implementation :

   public static void main(String[] args){
      AVL a = AVL.ajouter(null,1);
      a = AVL.ajouter(a, 2);
      a = AVL.ajouter(a, 3);
      a = AVL.ajouter(a, 6);
      a = AVL.ajouter(a, 4);
      a = AVL.ajouter(a, 5);
      TreeDraw.drawTree(a);
   }

Vous devriez obtenir le résultat suivant :

Cet arbre est-il un arbre binaire de recherche ou pas?

Déposez votre implémentation de AVL.java ici:

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3. Arbres AVL

L'arbre obtenu dans l'exercice précèdent est bien un arbre binaire de recherche, mais n'est pas du toute équilibré et, donc, pas un arbre AVL non plus. En fait, l'arbre obtenu a dégénéré en liste triée. Ce fait a comme conséquence que, par exemple, le test dâ'appartenance dâ'un élement est (au pire) linéaire du nombre des élements.

Dans cet exercice, on va équilibrer les arbres pour qu'au lieu de l'arbre obtenu en haut, on obtient pour le même ensemble dâ'entiers un arbre comme suit :

Rappel : Définition d'arbre AVL et les transparents d'amphi

3.1 Rotations

Comme vu en cours, les rotations sont des éléments clés pour créer et maintenir des arbres AVL. Construire ainsi deux fonctions (qui seront toutes deux non-destructrices):

Ajouter à la fin du public static void main(String[] args) les lignes suivante :

	  a = AVL.ajouter(a,0);
      TreeDraw.drawTree(a);
      TreeDraw.drawTree(AVL.rotationD(AVL.copy(a)));
      TreeDraw.drawTree(AVL.rotationG(AVL.copy(a)));

Vous devriez obtenir le résultat suivant (3 fenetres):

Déposez votre implémentation de AVL.java ici:

3.2 Insertion Equilibre

Dans la classe AVL écrivez une méthode static AVL ajouterAVL (AVL a, int val) qui ajoute un élément dans un arbre AVL. La fonction doit renvoyer un arbre équilibré, tel que les hauteurs des sous-arbres left et right diffèrent d' un au plus. La fonction doit utiliser les fonctions AVL.rotationD(...) et AVL.rotationG(...).

Pour vous en tirer, nous vous conseillons de regarder les dessins de rotations dâ'arbres AVL dans le poly, ou les transparents.

Ajouter à la fin du public static void main(String[] args) les lignes suivante :

      AVL b = AVL.ajouterAVL(null,1);
      b = AVL.ajouterAVL(b, 2);
      b = AVL.ajouterAVL(b, 3);
      b = AVL.ajouterAVL(b, 6);
      b = AVL.ajouterAVL(b, 4);
      b = AVL.ajouterAVL(b, 5);
      b = AVL.ajouterAVL(b, 0);
      TreeDraw.drawTree(b);
   }

Vous devriez obtenir le résultat suivant :

Déposez votre implémentation de AVL.java ici:

4. Ensembles

Nous allons manipuler des ensembles de nombres entiers. Un ensemble est par exemple B = {1, 8, 9, 20}. Au niveau informatique un ensemble peut être représenté de façon efficace par un arbre binaire de recherche ou un arbre AVL. Nous allons implémenter cette stratégie dans cette partie du TD.

4.1 Création facile d'un ensemble d'entiers

En TD6, vous avez implémenté une classe SymbolReader qui permet dâ'extraire facilement les symboles de la ligne des commandes. Nous allons réutiliser cette classe pour facilement construire un ensemble à partir de la ligne des commandes comme suit :

   java Ensemble 10 7 14 5 9 12 21

Récupérez le ficher SymbolReader.java dans votre répertoire TD6 (la commande est ‘

cp ../TD6/SymbolReader.java .

Ecrire la classe Ensemble, qui pour lâ'instant contient seulement une fonction public static void main(String[] args) dans laquelle vous allez utiliser SymbolReader pour lire la ligne de commande, Integer.parseInt(...) pour convertir les Strings vers des entiers et AVL.ajouterAvl(...) pour ajouter les entiers à lâ'arbre AVL :

   class Ensemble{
      public static void main(String[] args){
         AVL myAvl = null;
          
         // ...a completer...

         TreeDraw.drawTree(myAvl);	
      }
   } 

Testez la fonctionnement de votre code avec :

   java Ensemble 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Vous devriez obtenir le résultat suivant :

Déposez votre implémentation de Ensemble.java ici:

( Vous pouvez essayer de remplacer AVL.ajouterAVL(...) par AVL.ajouter (...) pour mieux voir les avantages d'un arbre AVL sur un simple arbre binaire de recherche. N'oubliez pas néanmoins de remettre AVL.ajouterAVL(). )

4.2 Test d'appartenance

Ajouter à la classe Ensemble la méthode static boolean mem(int x, ArbreAVL a), qui va vous permettre de tester si un entier appartient à un suite de nombres entiers.

Vous pouvez tester votre implémentation en ajoutant à la fin de public static void main(String[] args) la ligne suivante :

   System.out.println ("L'ensemble contient l'element 9? " + Ensemble.mem(9,myAvl));

Testez avec les commandes:

   java Ensemble 10 7 14 5 9 12 21

et

   java Ensemble 1 6 8 4

Vous devriez obtenir le résultat suivant :

   L'ensemble contient l'element 9? true

et

   L'ensemble contient l'element 9? false

Déposez votre implantation de Ensemble.java ici :

4.3 Test d'inclusion d'ensembles

Ajouter à la classe Ensemble la méthode static boolean subEnsemble (AVL a, AVL b) qui vous dit si un ensemble dâ'entiers, a, est inclus dans un autre ensemble dâ'entiers, b.

Vous pouvez tester votre implémentation en ajoutant à la fin de public static void main(String[] args) la ligne suivante :

   AVL myAvl2 = AVL.ajouterAVL(null, 5);
   myAvl2 = AVL.ajouterAVL(null, 7);
   myAvl2 = AVL.ajouterAVL(null, 12);

   System.out.println ("L'ensemble {5,7,12} est bien inclus dans l'ensemble extrait de la ligne de commande? " 
                       + Ensemble.subEnsemble(myAvl2,myAvl));

Tester avec les commandes:

   java Ensemble 10 7 14 5 9 12 21

   java Ensemble 1 6 8 4

Vous devriez obtenir le résultat suivant :

   L'ensemble {5,7,12} est bien inclus dans l'ensemble extrait de la ligne de commande ? true

et

   L'ensemble {5,7,12} est bien inclus dans l'ensemble extrait de la ligne de commande ? false

Déposez votre implantation de Ensemble.java ici :