Lab6 : Les Arbres AVL

Objectifs

• Implémenter et appliquer une classe générique ArbreAVL.
• Se préparer au TP2.

Lecture préalable

• Sections 8.8 à 8.9 des notes de cours.

Présentation du code de l'insertion

• Le code de l'insertion dans un arbre binaire de recherche (non équilibré) a été présenté en classe dans les diapos #19 à 23 de arbres-binrech.pdf.
• Le code de l'insertion dans un arbre AVL est partiellement fourni et sera expliqué au début du lab par les démonstrateurs.

template <class T>
bool ArbreAVL<T>::inserer(Noeud*& noeud, const T& element)
{
    if(noeud==NULL)
    {
        noeud = new Noeud(element);
        return true;
    }
    if(element < noeud->contenu){
        if(inserer(noeud->gauche, element))
        {
            noeud->equilibre++;
            if(noeud->equilibre == 0) return false;
            if(noeud->equilibre == 1) return true;
            assert(noeud->equilibre==2);
            if(noeud->gauche->equilibre == -1)
                    rotationDroiteGauche(noeud->gauche);
                rotationGaucheDroite(noeud);
        }
        return false;
    }
    else if(noeud->contenu < element){
        // À compléter.
        return false;
    }

    // element == noeud->contenu
    noeud->contenu = element;  // Mise à jour
    return false;
}

• La fonction inserer ci-haut retourne true si et seulement si le sous-arbre a crû en hauteur.
• La fonction rotationGaucheDroite reconnecte des pointeurs pour rebalancer l'arbre.

template <class T>
void ArbreAVL<T>::rotationGaucheDroite(Noeud*& racinesousarbre)
{
    Noeud *temp = racinesousarbre->gauche;
    int  ea = temp->equilibre;
    int  eb = racinesousarbre->equilibre;
    int  neb = -(ea>0 ? ea : 0) - 1 + eb;
    int  nea = ea + (neb < 0 ? neb : 0) - 1;

    temp->equilibre = nea;
    racinesousarbre->equilibre = neb;
    racinesousarbre->gauche = temp->droite;
    temp->droite = racinesousarbre;
    racinesousarbre = temp;
}

---

Tâches

Téléchargement des fichiers du Lab6

wget http://ericbeaudry.ca/INF3105/lab6/lab6.zip
unzip lab6.zip

Implémentation dans arbreavl.h

Pour tester :

g++ test_arbreavl.cpp
./a.out

Cette tâche devrait vous occuper pour une bonne partie du Lab6.

Notez que la solution finale de arbreavl.h ne sera pas fournie, car sa complétion est l'un des objectifs du TP2. Une bonne partie du code de arbreavl.h est fournie dans les notes de cours. De plus, les démonstrateurs peuvent vous aider si vous êtes bloqués.

Application pour la prévention de fraudes (suite Lab5)

• Utilisez votre ArbreAVL pour optimiser l'application du Lab5.
• Vous aurez besoin d'implémenter l'enlèvement.

Question d'examen antérieur

Cette tâche est basée sur la question 3 de l'examen préparatoire de mi-session de la session 2012H.

Vous devez écrire un programme qui reçoit en entrée des lectures de température. Chaque ligne comporte une date exprimée en heure et une température en Celsius séparées d’un espace blanc. Tous les nombres sont des nombres réels (double). Les données sont dans l’ordre chronologique. Voici un exemple d’entrée.

0.00 9.7
1.00 10.1
2.00 10.2
3.00 10.5
4.00 10.3
5.00 10.7
6.01 11.7
7.00 12.4
8.01 14.7

Partie A

Écrivez un programme lab6.cpp qui permet :

1. d’estimer la température à une date donnée
2. et de calculer la température moyenne entre deux dates.

On suppose que la température varie de façon linéaire entres deux dates pour lesquelles la température est connue. Par exemple, la température au temps 0.5 est de 9.9. Votre solution doit être construite autour d’une classe Historique qui permet de garder l’historique des températures en mémoire. Vous devez choisir une représentation de la classe Historique et coder les fonctions estimeTemperature(...) et calculeMoyenne(...). Si ces fonctions appellent d’autres fonctions, vous devez les donner. Vous n’avez pas à fournir le code pour lire les données. Vous devez vous soucier des qualités usuelles d’un logiciel, soit l’efficacité (mémoire et temps), la lisibilité du code, etc.

class Historique{
   private:
     // Représentation
   public:
     Historique();
     ~Historique();
     void ajouter(double date, double temperature);
     double estimeTemperature(double date) const;
     double calculeMoyenne(double datedebut, double datefin) const;
};

Partie B

Donnez les modifications requises (si nécessaire) pour traiter des cas où les données n’arriveraient pas de façon chronologique. Écrivez lab6.cpp implémentant cette solution.

Si vous jugez qu’aucune modification n’est requise, expliquez pourquoi la solution en A est «parfaite». Si vous jugez que des modification sont requises, expliquez pourquoi la solution en A demeure pertinente dans le cas où les données sont dans l’ordre chronologique.