TP — Séance 4 — Arbres et tas

Écrire, tester et mesurer un ABR, un AVL et un tas binaire en Java

TP de la séance 4 de Structures de données et algorithmes avancés : chercher en O(log n) et toujours extraire le minimum.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Écrire les trois structures du cours, SimpleBST (arbre binaire de recherche), AVLTree (arbre AVL) et BinaryMinHeap (tas binaire), les faire passer par les tests JUnit fournis, puis mesurer leur coût : hauteur et comparaisons selon l’ordre d’insertion, comparées à la formule \(2(1+1/n)H_n-3\) et à la borne \(1{,}44\log_2(n+2)\) des AVL, échanges des percolations comparés à \(\log_2 n\). Durée : une séance de TP.

À rendre. Le dépôt Git du projet (les trois classes complétées, les tests au vert) et un compte rendu d’une à deux pages qui répond aux questions marquées Observer, Expliquer et Modifier, en recopiant les sorties obtenues.

Préparation

Le TP se fait dans l’environnement Docker du cours (Java 17, Gradle 8, JUnit 5). Sur la machine, décompresser le code de départ, TP_S04_code_depart.zip, dans ~/dsa : le dossier TP_S04_code_depart/ apparaît. Le conteneur se lance depuis ce dossier :

cd ~/dsa
docker run -it --rm -v "$(pwd):/workspace" elbachirtoure/dsa-java:v2.0

Sous Windows (Git Bash), la commande docker run est précédée de MSYS_NO_PATHCONV=1. Dans le conteneur :

cd /workspace
new-project tp-s04
cd tp-s04
cp -r ../TP_S04_code_depart/. .
rm src/test/java/MainTest.java

Le code de départ contient six fichiers, cinq dans src/main/java/ et ArbresTasTest.java dans src/test/java/ : la copie les range dans le projet, en remplaçant le Main.java créé par new-project, et rm supprime le MainTest.java créé par new-project. Le dépôt Git du projet se crée dans tp-s04 : git init -b main et l’identité locale, comme à l’étape 7 du TP-1.

Fichier Rôle
BinarySearchTree.java l’interface du type abstrait (put, get, contains, size, hauteur), fournie
SimpleBST.java l’ABR non équilibré : méthodes à écrire aux étapes 1 et 2
AVLTree.java l’arbre AVL : méthodes à écrire à l’étape 4
BinaryMinHeap.java le tas binaire min : méthodes à écrire à l’étape 5
Main.java programmes d’observation et de mesure, fournis
ArbresTasTest.java quinze tests JUnit, fournis

Les méthodes à écrire contiennent une consigne en commentaire et lèvent UnsupportedOperationException ; tout le reste est fourni. Sur un arbre dégénéré de plusieurs milliers de nœuds, les méthodes récursives empilent autant d’appels que l’arbre a de niveaux, ce qui peut dépasser la pile par défaut de la machine virtuelle ; ajouter donc à la fin de build.gradle les lignes suivantes, qui l’agrandissent pour run et pour test :

application {
    applicationDefaultJvmArgs = ['-Xss16m']
}
test {
    jvmArgs '-Xss16m'
}

Les deux commandes du TP sont gradle --no-daemon test et gradle --no-daemon run --args="mode", où mode vaut suppression, hauteurs, equilibre, avl, tas ou tri.

Observer. Lancer les tests avant d’écrire la moindre ligne : combien échouent, et avec quelle exception ?

Étape 1 : recherche et insertion dans l’ABR

SimpleBST range ses paires dans des nœuds à deux liens, gauche et droite ; le champ racine vaut null pour un arbre vide, et le compteur public comparaisons compte les appels à compareTo de get et de put. Écrire, dans l’ordre, la méthode privée récursive put, puis get (itérative), contains et la méthode privée hauteur, en suivant les consignes en commentaire.

  1. Observer. Les cinq tests dont le nom commence par abr et qui ne portent pas sur la suppression (abrPutGet, abrRemplacement, abrContainsValeurNulle, abrHauteurEtComparaisons, abrDegenere) doivent passer. Dessiner l’arbre du test abrHauteurEtComparaisons et retrouver par le calcul les valeurs 10 et 3 attendues pour comparaisons.
  2. Expliquer. Le test abrDegenere attend 66 comparaisons pour 12 insertions croissantes : retrouver ce nombre, puis donner la formule pour \(n\) clés croissantes.
  3. Modifier. Ajouter provisoirement n++ dans la branche qui remplace la valeur d’une clé présente. Quel test échoue, avec quel message ? Revenir au code correct.
  4. Expliquer. Pourquoi contains n’est-elle pas écrite return get(cle) != null; ? Citer le test qui l’établit.

Étape 2 : suppression et parcours infixe

Écrire la méthode privée remove, qui traite les trois cas du cours (feuille, un enfant, deux enfants, ce dernier par le successeur infixe, minimum du sous-arbre droit, calculé par la méthode fournie min), puis la méthode privée infixe.

  1. Observer. Les tests abrSuppressionTroisCas, abrSuppressionAbsente et abrInfixeTrie doivent passer. Lancer gradle --no-daemon run --args="suppression" et recopier les six lignes écrites.
  2. Expliquer. Pour chacune des quatre suppressions, nommer le cas et dire quel nœud prend la place de la clé supprimée.
  3. Modifier. Remplacer provisoirement, dans le cas à deux enfants, le successeur par le prédécesseur infixe (maximum du sous-arbre gauche). Quel test échoue ? Comparer l’arbre écrit par le mode suppression à celui de la question (a) : les parcours infixes diffèrent-ils ? Revenir au successeur.

Étape 3 : la hauteur mesurée

Le mode hauteurs construit, pour \(n\) de 500 à \(8\,000\), un ABR par insertions croissantes, puis 20 ABR par insertions dans un ordre aléatoire (graine 2026) ; il donne leurs hauteurs et le coût moyen mesuré d’une recherche réussie, à côté de la formule \(C_n=2(1+1/n)H_n-3\). Le mode equilibre insère les mêmes clés dans l’ordre des médianes : la médiane d’abord, puis la médiane de chaque moitié, et ainsi de suite.

  1. Observer. Lancer les deux modes et recopier les deux tableaux.
  2. Expliquer. Comparer, pour \(n=8\,000\), la hauteur des arbres aléatoires à \(\lfloor\log_2 n\rfloor\) et le coût mesuré à \(C_n\). Pourquoi la hauteur varie-t-elle d’un arbre à l’autre, alors que le coût moyen suit la formule de près ?
  3. Expliquer. Dans le mode equilibre, pourquoi la hauteur vaut-elle exactement \(\lfloor\log_2 n\rfloor\) et le coût moyen environ \(\log_2 n-1\) ?

Étape 4 : l’arbre AVL

AVLTree mémorise dans chaque nœud la hauteur de son sous-arbre ; h, equilibre et majHauteur sont fournies, ainsi que get, contains, etat et estAVL, qui vérifie l’invariant et les hauteurs mémorisées. Écrire rotationDroite, rotationGauche, reequilibrer et la méthode privée put, qui compte les rotations dans le champ rotations (une double rotation compte pour 2).

  1. Observer. Les tests avlQuatreCas, avlCroissant et avlAleatoire doivent passer. Pour chacun des quatre ordres du test avlQuatreCas, dessiner l’arbre avant rééquilibrage et nommer le cas.
  2. Observer. Lancer gradle --no-daemon run --args="avl", qui construit des AVL de \(2\,000\), \(20\,000\) et \(200\,000\) clés, croissantes puis mélangées, et recopier le tableau. Comparer chaque hauteur à la borne et à \(\lfloor\log_2 n\rfloor\).
  3. Expliquer. Pourquoi les insertions croissantes demandent-elles presque une rotation par clé, plus que les insertions aléatoires ?
  4. Modifier. Supprimer provisoirement, dans reequilibrer, la première rotation des cas LR et RL. Quels tests échouent ? Que devient la colonne AVL ? du mode avl, et pourquoi les insertions croissantes ne sont-elles pas touchées ? Revenir au code correct.

Étape 5 : le tas binaire et le tri par tas

BinaryMinHeap range le tas dans le tableau data ; plusPetit(i, j) (qui compte les comparaisons), swap(i, j) (qui compte les échanges), resize, peekMin, toString et estTas sont fournies. Écrire insert, percolateUp, extractMin et percolateDown.

  1. Observer. Les quatre tests dont le nom commence par tas doivent passer, et les quinze tests au total. Dessiner le tas du test tasPercolationVersLeBas avant et après l’extraction.
  2. Observer. Lancer les modes tas et tri et recopier leurs sorties.
  3. Expliquer. Pourquoi une insertion de clé aléatoire coûte-t-elle environ 1,3 échange quelle que soit la taille, alors qu’une insertion de clés décroissantes coûte environ \(\log_2 n-2\) échanges ? Pourquoi extractMin reste-t-elle proche de \(\log_2 n\) ?
  4. Modifier. Dans percolateDown, descendre provisoirement toujours vers l’enfant gauche, sans comparer les deux enfants. Quels tests échouent ? Expliquer sur le tas de tasPercolationVersLeBas. Revenir au code correct.
  5. Expliquer. À partir de la sortie du mode tri, calculer le nombre de comparaisons par clé, puis le rapporter à \(\log_2 n\) : de quelles opérations vient l’essentiel de ce coût ?

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet