INF 421 - TD 7
Arbre de Recherche

T. Clausen


 Login :  Mot de passe :

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

  • Une feuille est un arbre de hauteur 1.
  • L'arbre vide a la hauteur 0.
  • L'arbre vide et l'arbre réduit à une feuille sont des arbres AVL.
  • 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 :

  • rappeller le mécanisme d'interfaces de Java;
  • rappeller les arbres binaires et leur parcours comme nous l'avons vu au TD06;
  • implanter et manipuler les arbres équilibrés.
  • 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 :

  • nommer les classes, variables et méthodes EXACTEMENT comme demandé dans l'énoncé
  • écrire chaque classe java dans un fichier à part qui porte le nom de la classe (suivi de .java).
  • coder de manière claire et organisée de sorte que votre code soit aisément lisible par un tiers. Des commentaires pertinents seront appréciés.
  • 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:

  • public String label() - retourne un texte représentant l'étiquette du noeud - dans ce TD, c'est un entier.
  • public TreeElem getLeft() - retourne une référence au sous-arbre gauche
  • public TreeElem getRight() - retourne une référence au sous-arbre droit

    1.2 Premier pas : Arbre binaire

    Le premier pas vers un arbre binaire de recherche, est, bien sur, un arbre binaire. Donc, nous allons écrire une classe AVL, qui doit implémenter l'interface TreeElem (et, donc, les méthodes de cette interface), et avoir:

  • un attribut valeur de type int;
  • deux références respectivement à un sous-arbre gauche (left) et à un sous-arbre droit (right) qui sont tous les deux de type AVL;
  • 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:

  • les étiquettes ne sont pas distinctes;
  • 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

  • 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.
  • Un feuille est un arbre de hauteur 1.
  • L'arbre vide a la hauteur 0.
  • L'arbre vide et l'arbre réduit à une feuille sont des arbres AVL.
  • 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):

  • static AVL rotationG(AVL a) qui applique une rotation vers la gauche à l'arbre a
  • static AVL rotationD(AVL a) qui applique une rotation vers la droite à l'arbre a
  • 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:

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

    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:

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

    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 .
    ', si vous avez fait exactement comme demandé depuis TD1). Si vous n'avez pas une version de SymbolReader qui marche téléchargez SymbolReader.java ici.

    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:

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

    ( 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 :

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

    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
    
    et
       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 :

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