TD-6, Les arbres équilibrés




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-6/

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

Avertissement
Le fil du travail pratique vous prend par la main. Un premier exercice est l'implémentation des ensembles d'entiers par les arbres de recherche, on passe ensuite au second exercice qui est l'implémentation des mêmes ensembles par les arbres AVL. Le style de programmation proposé est différent des transparents et du cours : pas de modification en place.

On peut parfaitement adapter cet exercice à ses connaissances préalables où à ses goûts.
1 Encodage des ensembles d'entiers par les arbres
Les arbres (de recherche) sont abordés dans les dans la section 4.4 du poly.

1.1 Principe
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. Voici un exemple d'arbre de recherche.
         _________20______
       __3__           _25_
      3  __12__       21   28
       __8    13
       6
(Dans ce TD, pas de jolis dessins, mais des représentation des arbres en mode texte !)

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 ci-dessus n'encode pas un ensemble car il contient deux fois l'entier 3.

Dans le cas qui nous occupe donc, 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é. Pour cela, il faut un arbre équilibré et l'exercice raffiné y revient. Pour le moment ignorons ce détail en supposant par exemple que nos arbres sont naturellement équilibrés.

1.2 Des journées entières dans les arbres

Le source Arbre fourni contient la classe des arbres. Récupérez le, mais ne le lisez pas ! Pour vous cette classe est exactement équivalente à la définition sans surprise :
Usage didactique, ne pas copier, ne pas coller, ne pas compiler !!!

class Arbre {
  int val ; // étiquette
  Arbre left,right; // fils gauche et droit

  Arbre (int val) { // Constructeur des feuilles
    this.val = val ;
    this.left = this.right = null ;
  }

  Arbre (Arbre left, int val, Arbre right) {//Constructeur des noeuds internes
    this.val = val ;
    this.left = left ;
    this.right = right ;
  }
}
La vraie classe des arbres Arbre offre les fonctionnalités supplémentaires suivantes :
  1. Le constructeur des noeuds internes est blindé, il refuse de créer un noeud qui viole la contrainte (stricte) d'ordre des arbres de recherche.
  2. Il y a une méthode (non-statique) toString, de sorte que, si a est un arbre, alors l'appel System.out.print(a) affiche l'arbre sur la console.
Une fois compilé Arbre.java, vous pouvez tester ces fonctionnalités supplémentaires en donnant un arbre sous forme infixe sur la ligne de commande :
maranget@manche ~/TD/TD-10 > java Arbre [ [ 1 2 3 ] 4 [ 5 6 7 ] ]
    ___4____
  _2__    _6__
 1   3   5   7 
Ou encore :
maranget@manche ~/TD/TD-10 > java Arbre [ [ 1 2 3 ] 6 [ 5 6 7 ] ]
java.lang.Error: Valeurs mal fichues :
val : 6
gauche :
  _2__
 1   3 
et droite :
  _6__
 5   7 
La lecture des arbre sous forme infixe est un peu rustique...

1.3 À vous de jouer

Écrire une classe des ensembles Set qui possède les méthodes, cardinal, mem, add, remove et subset réalisant respectivement, le calcul du cardinal, le test d'appartenance, l'ajout d'un élément, le retrait d'un élément, et le test d'inclusion des ensembles représentés comme des arbres. Voici des signatures possibles pour ces méthodes :
  static int cardinal (Arbre a)
  static boolean mem (int x, Arbre a)
  static Arbre add (int x, Arbre a)
  static Arbre remove (int x, Arbre a)
  static boolean subset (Arbre a, Arbre b)
Il faut réaliser les opérations traditionnelles sur les ensembles, ainsi ajouter un élément à un esemble qui le contient déjà est parfaitement légal. Dans ce cas, la méthode add renvoie le même ensemble. Voici une contrainte et une indication : Votre classe Set possédera aussi une méthode main qui va permettre de tester ses méthodes. On obtiendra par exemple, en utilisant cette méthode main (qui ne teste pas remove) :
maranget@manche ~/TD/TD-10 > java Set 7 2 50 5 25
Voici votre ensemble :
  ___7____
 2_     __50 
   5   25 

Son cardinal est : 5.
Il est bien inclus dans lui même.
Il ne contient pas -1.
J'y ai ajouté 10 entiers pris au hasard :
      ___7_________________________
    _2_           _________________50 
  _1   5    _____25____
 0         12_       __34_
              22    30    37____
                              __47 
                             39 

Votre ensemble est bien inclus dans le mien.
Cette inclusion est stricte.
Solution

2 Une question d'équilibre
Les arbres équilibrés sont abordés à la section 4.5 du poly.

2.1 De l'importance d'être équilibré
Choisissons un ensemble bien particulier et donnons ses éléments dans l'ordre à la solution de l'exercice précédent :
maranget@manche ~/TD/TD-10 > java Set 1 2 3 4 5 6 7 8
Voici votre ensemble :
 1_
   2_
     3_
       4_
         5_
           6_
             7_
               8
L'arbre a dégénéré en liste triée. En particulier, le test d'appartenance est (au pire) linéaire en le cardinal des ensembles. On peut certainement faire mieux à la sixième séance.

Un arbre qui ressemble à un arbre est équilibré. Pour préciser cette idée, on peut par exemple, borner la différence des hauteurs des deux fils d'un noeud par une constante, encore par exemple 1. Et on obtient les arbres AVL. (Exercice un peu taupinal mais intéresssant, quel est, pour une hauteur h donnée, le nombre minimal de noeuds d'un arbre AVL ?)

Selon ce critère, l'arbre suivant n'est pas équilibré
      4___
         _6_
        5   8 
car le fils gauche de la racine est de hauteur zéro, tandis que son fils droit est de hauteur deux.

2.2 Programmation
Récupérez la nouvelle classe ArbrePlus des arbres.

Cette nouvelle classe des arbres étend la précédente au sens suivant :
  1. Le blindage du constructeur des noeuds est plus épais, il refuse de créer un arbre qui ne sera pas équilibré.
  2. On récupère la hauteur d'un arbre a par l'appel d'une nouvelle méthode (statique) ArbrePlus.hauteur(a).
Ensuite copier votre Set.java dans un nouveau fichier SetPlus.java et changez toutes les occurrences de ``Arbre'' en ``ArbrePlus'' (avec la fonction de remplacement d'emacs, Esc-x replace-string). Après compilation de ArbrePlus.java et SetPlus.java, vous pouvez constater que le blindage du constructeur est efficace :
maranget@manche ~/TD/TD-10 > java SetPlus 1 2 3 4 5 6 7 8
java.lang.Error: Arbre mal équilibré :
val : 1
gauche :
 arbre vide
et droite :
 2_
   3 
Vous ne pouvez donc plus appeler directement le constructeur des noeud sans précaution.

Voici deux indications : À la fin, on aura :
maranget@manche ~/TD/TD-10 > java SetPlus 1 2 3 4 5 6 7 8
Voici votre ensemble :
    ___4___
  _2_     _6_
 1   3   5   7_
               8 

Son cardinal est : 8.
Il est bien inclus dans lui même.
Il ne contient pas -1.
J'y ai ajouté 10 entiers pris au hasard :
      ___4_______
    _2_       ___8__________
  _1   3    _6_        _____49____
 0         5   7    __39_       __58_
                   33    47    56    59 

Votre ensemble est bien inclus dans le mien.
Cette inclusion est stricte.
Solution


Dernière modification : 2003-05-9

Ce document a été traduit de LATEX par HEVEA.