Afficher dans l'ordre — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 9)

Afficher dans l'ordre

Arbres binaires de recherche de coût minimum · niveau 1 (application)

Énoncé

Écrire void ac(AB a) qui affiche les valeurs de l'abr $a$ dans l'ordre croissant, et justifier le programme par des commentaires (base, hérédité).
Écrire void ad(AB a) qui les affiche dans l'ordre décroissant.
En déduire un algorithme de tri d'un tableau de valeurs distinctes. Quelle est sa complexité dans le pire cas ?

Corrigé

Parcours gauche, racine, droite :


static void ac(AB a) {
    if (vide(a)) return;           // a vide : ses valeurs sont affichées
    ac(sag(a));                    // (1) les valeurs de sag(a) affichées croissantes
    System.out.print(vr(a) + " "); // (2) la racine, plus grande que toutes celles de sag(a)
    ac(sad(a));                    // (3) les valeurs de sad(a), plus grandes que la racine
}                                  // (1)(2)(3) : les valeurs de a affichées croissantes

Il suffit d'échanger les deux appels récursifs :


static void ad(AB a) {
    if (vide(a)) return;
    ad(sad(a)); System.out.print(vr(a) + " "); ad(sag(a));
}


ac : 1 2 3 4 5 6 7 8 9 | ad : 9 8 7 6 5 4 3 2 1


valeurs : 1 2 3 4 5 6 7 8 9
indices : non
colorier : 4
zone : 0..3 sag(5)
zone : 5..8 sad(5)
legende : ac sur l'abr des insertions 5, 3, 8, 1, 4, 7, 9, 2, 6

On insère les $n$ valeurs dans un abr vide, puis on le parcourt par ac : c'est un tri. Le parcours est en $Θ (n)$ , mais les insertions coûtent $Θ (n^{2})$ dans le pire cas (tableau déjà trié, exercice 9.3) : le tri est en $Θ (n^{2})$ dans le pire cas.