Tris : tas et arbres binaires équilibrés
Sujet proposé par David Monniaux.
Nous expérimenterons deux méthodes pour trier les lignes d'un fichier à l'aide d'algorithmes en n log n. Pour comparer deux chaînes a et b on regardera le signe de a.compareTo(b), qui est <0, =0, >0 si, respectivement, a est plus petite que b, égale ou plus grande.
Un corrigé est disponible : Arbre.java et Tas.java.
1. Arbre binaire équilibré
Nous nous proposons dans cette section d'utiliser des arbres binaires de recherche (comme la dernière fois), mais équilibrés, c'est-à-dire que pour chaque nœud, les sous-branches gauche et droite ont pratiquement la même hauteur (plus précisément, nous admettrons des différences de hauteur inférieures ou égales à 2). Nous stockerons sa hauteur dans chaque nœud, laquelle devra toujours être égale au maximum des hauteurs de son sous-arbre de gauche et de son sous-arbre de droite, plus un. Un arbre sera ainsi représenté :
- Soit par la valeur
null, pour l'arbre vide.
- Soit par un objet de type
Arbre, comprenant deux champs gauche et droite de type Arbre, un champ hauteur de type entier, un champ valeur de type String.
Ainsi, on aura donc la déclaration :
class Arbre {
Arbre gauche, droite;
String valeur;
int hauteur;
}
Nous vous rappelons sous forme condensée les contraintes que tout arbre bien formé doit vérifier :
hauteur(arbre)=max(hauteur(arbre.gauche),hauteur(arbre.droite))+1- |
hauteur(arbre.gauche)-hauteur(arbre.droite)| ≤ 2.
Vous écrirez toutes vos fonctions dans la classe Arbre dans le fichier Arbre.java.
1.1 Programmez une fonction static int hauteur(Arbre a) qui retourne la hauteur de l'arbre (un arbre vide a une hauteur nulle, sinon prendre la hauteur dans le nœud).
1.2 Programmez une fonction static int max(int a, int b) qui retourne le maximum de deux entiers.
1.3 Programmez un constructeur Arbre(Arbre gauche, String valeur, Arbre droite) qui construit un nœud avec un champ hauteur correct (vous utiliserez les fonctions précédemment écrites).
1.4 Programmez une fonction static Arbre balancer(Arbre gauche, String valeur, Arbre droite). Vous supposerez que |hauteur(gauche)-hauteur(droite)| ≤ 3 et que gauche et droite sont bien équilibrés.
Voici l'analyse que cette fonction doit faire :
- Premier cas,
hauteur(arbre.gauche)>hauteur(arbre.droite)+2. On distinguera alors :
- Sous-cas où
hauteur(gauche.gauche)≥hauteur(gauche.droite).On doit alors retourner un nouvel arbre selon la rotation :
Remarquez qu'alors forcément hauteur(gauche.gauche)=hauteur(droite)+2 et que hauteur(droite)≤hauteur(gauche.droite)≤hauteur(droite)+2 et que le nouvel arbre est forcément équilibré.
- Sous-cas où
hauteur(gauche.gauche)<hauteur(gauche.droite).
Remarquez qu'alors forcément hauteur(gauche.droite)=hauteur(droite)+2 et que hauteur(droite)≤hauteur(gauche.gauche)≤hauteur(droite)+2 et que l'arbre produit est donc forcément équilibré.
- Second cas,
hauteur(arbre.gauche)<hauteur(arbre.droite)-2, qui est symétrique du précédent.
- Sinon, |
hauteur(arbre.gauche)-hauteur(arbre.droite)| ≤ 2, et il suffit d'appeler le constructeur pour former un arbre bien équilibré.
1.5 Programmez static Arbre ajouter(Arbre arbre, String element).
1.6 Programmez une fonction static void imprimer(Writer writer, Arbre arbre) throws IOException qui parcourt l'arbre de gauche à droite en imprimant les nœuds à l'aide de writer.write(arbre.valeur + "\n");.
1.7 Programmez une fonction static boolean estBienBalance(Arbre arbre) qui vérifie si l'arbre est bien équilibré.
1.8 Téléchargez Trier.java. Mettez en commentaire la partie concernant les tas, compilez, et exécutez (java Trier fichier1 fichier2 fichier3 triera fichier1 par tas (sortie dans fichier2 et par arbre (sortie dans fichier3). Vous pourrez par exemple comparer la sortie de votre programme à celle de la commande sort. Vous pourrez par exemple utiliser le fichier les_miserables.txt comme exemple de gros fichier à trier.
2. Tas
On se propose également de trier, mais à l'aide de tas binaire stockés dans des tableaux. Vous écrirez toutes vos fonctions dans une classe Tas dans un fichier Tas.java, avec les déclarations suivantes :
class Tas {
String[] elements; // contenu du tas
int rempli; // nombre d'éléments dedans
int filsGauche(int pere) {
return 2*pere+1;
}
int filsDroit(int pere) {
return 2*pere+2;
}
int pere(int fils) {
return (fils-1)/2;
}
Tas(int n) {
elements = new String[n];
rempli = 0;
}
}
2.1 Programmez la fonction void ajouter(String element) qui rajoute l'élément au tas, l'ordre étant choisi de façon à ce que la plus petite chaîne soit la racine du tas. Vous pourrez par exemple vous aider d'une fonction auxiliaire int comparer(int i, int j) comparant les éléments d'indices i et j et d'une fonction void echanger(int i, int j) les échangeant.
2.2 Programmez la fonction String oter() qui retourne la plus petite chaîne du tas et la supprime du tas en maintenant la structure de tas.
2.3 Programmez la fonction boolean disponible() qui retourne true si et seulement si le tas est non vide.
2.4 Dans la classe Trier, décommentez les lignes concernant les tas et testez votre code.
3. Comparaisons
En prenant par exemple des extraits de ocaml-source.txt, comparez la vitesse des deux algorithmes. Le programme affiche les temps en millisecondes.
