Login :  Mot de passe :

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

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 :

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

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

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 :

1.5 Programmez static Arbre ajouter(Arbre arbre, String element).

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

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.

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

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.

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

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.