Lab6 : Les Arbres AVL - Partie A

Objectifs

• Implémenter les fonctions de base d'une classe générique ArbreAVL.
• Appliquer une arbre binaire de recherche à un problème simple.
• Se préparer au TP3.

Lecture préalable

• Sections 8.8 et 8.9 des notes de cours.

Tâches

Fichiers du Lab6

wget http://cria2.uqam.ca/INF3105/lab6/lab6.zip
unzip lab6.zip
         

Fonctions de base

Complétez les fonctions de base de la classe ArbreAVL dans arbreavl.h:

1. vide
2. contient
3. inserer
4. vider

L'objectif est de réussir les tests #1 à 6 dans testavl.cpp. Pour tester :

g++ -o testavl testavl.cpp
./testavl
         

Notez que la solution finale de arbreavl.h ne sera pas fournie. Une bonne partie du code de arbreavl.h est fournie dans les notes de cours. La partie la plus difficile est la rotation droite-gauche.

L'Enlèvement simplifié

Le code de l'enlèvement n'a pas été fourni et est laissé en exercice. Tel qu'annoncé, l'enlèvement est plus difficile que l'insertion, car il y a plus de cas à gérer. Toutefois, il est possible d'implémenter un enlèvement simplifié.

L'enlèvement simplifié consiste à marquer les éléments enlevés, plutôt que de les enlever complètement de l'arbre, puis de les ignorer. L'avantage de cette méthode est sa simplicité. En effet, elle évite d'avoir à reconnecter des pointeurs, d'effectuer les rotations requises pour rééquilibrer l'arbre, etc. Le principal inconvénient est que l'arbre peut accumuler des éléments inutilisés. Ainsi, la hauteur de l'arbre peut être plus grande que nécessaire. Il y a aussi un gaspillage temporaire de mémoire pour garder ces éléments jusqu'au vidage de l'arbre.

Étapes pour implémenter l'enlèvement simplifié :

1. Ajouter un attribut bool enlevé dans la structure Noeud.
2. Initialiser cet attribut à false (ex: dans le constructeur).
3. Réviser la fonction contient : si l'élément recherché est trouvé dans l'arbre, il faut retourner faux si le noeud a été marqué enlevé=true.
4. Réviser la fonction compter : il ne faut pas compter les noeuds marqués par enlevé=true.
5. Réviser la fonction inserer : si l'élément est déjà dans l'arbre, il faut réinitialiser enlevé=false.

L'objectif est de passer le test #7.

Application : Détection de fraudes (revisitée)

Ici, il s'agit du même problème qu'au Lab5 / Tâche 3. L'objectif est d'utiliser un arbre binaire de recherche pour améliorer l'efficacité du programme. En effet, plutôt que de parcourir une liste chaînée en temps O(n), on peut vérifier le numéro de la carte en temps O(log n).

Algorithme proposé

1. Créer une File<PassageCarte> (ou liste) vide L.
2. Créer un ArbreAVL<int> vide A.
3. Tant que la lecture de l'entrée standard (std::cin) n'est pas terminée :
4. |  Lire un passage p. //Un passage est une paire d'entiers (temps, numéro_de_carte).
5. |  Tant que L n'est pas vide ET L.premier().temps + 600 ≤ p.temps.
6. |  |  A.enlever(L.premier().numéro)
7. |  |  L.défiler (ou enlever début)
8. |  Si A.contient(p.numéro) :
9. |  |  Afficher "Passage invalide !" // on pourrait améliorer pour afficher le temps dans A
10.|  Sinon :
11.|  |  A.inserer(p.numéro)
12.|  |  L.enfiler(p)
            

Des fichiers de test sont dans les fichiers de départ du Lab5 : lab5.zip.

Exercices complémentaires

Copie d'un arbre : opérateur = et constructeur par copie

Il s'agit essentiellement de coder la fonction copier utilisée par le constructeur par copie et l'opérateur d'affectation =. Si vous avez implémenté l'enlèvement simplifié, vous aurez une décision à prendre, soit comment traiter les éléments marqués enlevés (enlevé=true). Vaut-il mieux recopier l'arbre dans sa structure entière, ce qui inclut les éléments enlevés ? Ou, vaut-il mieux insérer les éléments non enlevés, un à un, dans le nouvel arbre ?

L'Enlèvement complet

Ébauche de l'enlèvement :

template <class T>
void ArbreAVL<T>::enlever(const T& element)
{
    enlever(racine, element);
}

template <class T>
bool ArbreAVL<T>::enlever(Noeud*& noeud, const T& element)
{
    if(element < noeud->contenu)
    {
        if(enlever(noeud->gauche, element))
        {
            // ...
        }
    }
    else if(element > noeud->contenu)
    {
        if(enlever(noeud->droite, element))
        {
            // ...
        }
    }
    else // if(element == noeud->contenu)
    {
        if (noeud->gauche==nullptr && noeud->droite==nullptr)
        {
            delete noeud;
            noeud = nullptr;
            return true;
        }
        else
        {
            // ...
            return true;
        }
    }

}