TD-6, Les arbres équilibrés
|
Envoyez vos programmes à Luc.Maranget@inria.fr.
Les solutions sont ici.
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.
-
Plus facile : ne pas programmer la méthode remove.
- Plus rapide, programmer directement les arbres équilibrés
(exercice 2).
- Plus difficile, choisir les arbres rouge-noir pour la
programmation des arbres équilibrés.
- Plus sportif, modifier les arbres en place (il faudra alors
enlever le blindage des constructeurs).
| 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.
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 :
-
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.
- 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...
É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 :
-
Si a et b sont structurellement les mêmes,
subset a un coût de l'ordre du cardinal de cet ensemble.
- Pour programmer remove, utiliser une méthode auxiliaire
qui enlève le plus petit élément d'un ensemble (ou le plus grand).
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.
Récupérez la nouvelle classe ArbrePlus des arbres.
Cette nouvelle classe des arbres étend la précédente au sens suivant :
-
Le blindage du constructeur des noeuds est
plus épais, il refuse de créer un arbre qui ne sera pas équilibré.
- 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.