Travail pratique #3 — Arbres AVL

Objectifs

• Pratiquer l'encapsulation et concevoir des types abstraits de données.
• Implémenter une structure de données ArbreAVL en C++.
• Implémenter des algorithmes de manipulation d'un ArbreAVL.
• Gérer la mémoire.
• Se préoccuper de l'efficacité.

Tâches

Le TP3 consiste à :

1. terminer l'implémentation de la classe générique ArbreAVL (fichier arbreavl.h) amorcée aux Lab6 et Lab7;
2. implémenter des fonctions de la classe ArbreAVL spécifiques au TP3.

Vous pouvez utilisez les tests fournis au Lab7 pour valider le fonctionnement des fonctions de base de votre classe ArbreAVL. À noter que ces tests ne sont pas exhaustifs. Il est donc fortement recommandé de créer vos propres tests pour vous assurer du bon fonctionnement de votre classe.

Des tests supplémentaires sont fournis dans tp3.zip. Bien qu'un fichier source arbreavl.h soit fourni, il est plutôt conseillé d'utiliser votre solution arbreavl aux labs 6 et 7, et d'y ajouter les fonctionnalités spécifiques au TP3. Le fichier pile.h fourni est le même qu'au Lab7. Aucune modification n'est permise, seul arbreavl.h est à remettre.

Interface publique

Votre implémentation finale doit offrir l'interface publique suivante. Autrement dit, tous les constructeurs, fonctions et opérateurs suivants doivent être implémentés.

template <class T>
class ArbreAVL{
  public:
    ArbreAVL();
    ArbreAVL(const ArbreAVL&);
    ArbreAVL& operator=(const ArbreAVL&);

    bool vide() const;
    bool contient(const T&) const;
    void inserer(const T&);
    void enlever(const T&); // version efficace ou simplifiée
    void vider();

    class Iterateur {
        Iterateur(const ArbreAVL& a);
        Iterateur(const Iterateur& a);
        Iterateur(const ArbreAVL& a, Noeud* c);

        operator bool() const;
        bool operator!() const;
        bool operator==(const Iterateur&) const;
        bool operator!=(const Iterateur&) const;

        const T& operator*() const;

        Iterateur& operator++();
        Iterateur operator++(int);
        Iterateur& operator=(const Iterateur&);
    };

    Iterateur debut() const;
    Iterateur fin() const;
    Iterateur rechercher(const T&) const;
    Iterateur rechercherEgalOuSuivant(const T&) const;
    Iterateur rechercherEgalOuPrecedent(const T&) const;

    // Nouvelles fonctions du TP3:

    // Retourne le i ième élément du parcours inordre de l'arbre.
    const T& operator[](int i) const;

    // Retourne un nouvel arbre AVL contenant les éléments inverses de l'arbre.
    // Ex.: si l'arbre contient 1, -2 et 3, le nouvel arbre doit contenir -1, 2 et -3.
    // On suppose que l'opérateur - est défini pour le type T.
    ArbreAVL<T> arbreInverse() const;

    // Retourne un nouvel arbre AVL représentant la différence symétrique
    // entre l'arbre courant et l'arbre passé en paramètre.
    // La différence symétrique est l'ensemble des éléments qui sont
    // dans un des deux arbres, mais pas dans les deux.
    ArbreAVL<T> differenceSymetrique(const ArbreAVL<T>&) const;

  private:
    ...
};

Vous pouvez ajouter d'autres fonctionnalités que celles listées ci-haut. Cependant, toutes les fonctionnalités listées ci-haut doivent être présentes, sinon les tests automatiques échoueront.

Vous pouvez modifier la représentation autant que vous le souhaitez. L'important est de respecter l'interface publique spécifiée ci-haut.

Perfection

Votre implémentation ArbreAVL doit viser la perfection. Lorsque vous avez différents choix possibles, au niveau de la représentation ou des algorithmes, vous devez prendre les meilleurs choix possibles. Si des compromis sont requis, vous devez prioriser, dans l'ordre, les qualités suivantes: (1) le fonctionnement correct, (2) l'efficacité temporelle, (3) l'efficacité spatiale (mémoire), et (4) la simplicité du code.

Contraintes

Bibliothèques permises

L'objectif du TP3 est d'implémenter votre propre classe générique ArbreAVL. Ainsi, il n'est pas permis d'utiliser les conteneurs de la bibliothèque standard de C++ (ex.: std::set ou std::map).

Environnement de développement

Relisez les Politiques et les directives sur les outils informatiques dans le cours INF3105. Votre TP3 doit pouvoir être compilé avec g++ version 11 ou 13 (versions installées sur le serveur java.labunix.uqam.ca).

Remise

Tous les membres de l'équipe doivent remettre le fichier arbreavl.h via le formulaire de remise du TP3 au plus tard le mardi 02 juillet 2024 à 23h59m59s.

Vous pouvez soumettre votre TP autant de fois que vous voulez. Seule la dernière soumission sera considérée.

Évaluation

Ce travail pratique est noté sur 100 et vaut 10% de la note finale.

Grille de correction

Critère	Description	Points
A	Respect des directives pour la remise Seul le fichier arbreavl.h doit être remis. Remise par le formulaire Web. Pas de remise par courriel. Compilable avec make sans modification. Exécutable sans modification.	10
B	Fonctionnement correct des fonctions de base du Lab6 et Lab7 La correction utilisera les tests du Lab6 et Lab7, et ajoutera des tests supplémentaires.	30
C	Fonctionnement correct des fonctions spécifiques au TP3: operator[](int), arbreInverse(), et differenceSymetrique(const ArbreAVL<T>&). La correction utilisera les tests dans tp3_operator.cpp et tp3_inverse.cpp et ajoutera des tests supplémentaires.	20
D.	Efficacité des fonctions spécifiques au TP3 Tests basés sur le nombre d'opérations (ex.: comparaisons et copies d'objets) et/ou temps CPU (mesuré avec la commande time). Pour obtenir des points d'efficacité pour une des fonctions spécifiques au TP3, il faut que la fonction réussise les tests de fonctionnement du critère C. Un programme incorrect mais efficace est généralement inutile ! Principes: L'équipe obtenant le plus petit temps d'exécution aura tous les points. L'équipe obtenant le temps médian aura au moins la moitié des points.	30
E.	Gestion de la mémoire correcte La mémoire est libérée correctement (avec delete). Utilisation raisonnable de la mémoire (pas de gaspillage déraisonnable).	10
	Total	100