Remarque préliminaire

1. votre code compile sans warning ;
2. dans votre code, quand vous libérez une zone mémoire, vous mettez le pointeur sur cette zone mémoire à NULL.

Préparation

Question 1 : Amélioration des tests unitaires

1. La compilation génère le warning "arbreAVL_usernameUnix.c:57:21: warning: ‘newNode’ defined but not used [-Wunused-function] static struct Node* newNode(const char *key)". Vu que vous n'avez pas encore commencé à coder arbreAVL_usernameUnix.c, ce warning est acceptable. Les warnings de compilation ne seront plus acceptés à partir de la question suivante.
2. Si la commande make run affiche le message "./testsUnitaires: error while loading shared libraries: libcmocka.so.0: cannot open shared object file: No such file or directory", dans votre terminal, tapez la commande :
   export   LD_LIBRARY_PATH=$LD_LIBRARY_PATH:cmocka/install/lib

Question 2 : Codage des fonctions update_height(), nbNodes(), newNode(), insert() et release()

• Si node vaut NULL, insert renvoie newNode(key)
• Si key est plus petit que node->key, insert insère key dans une feuille la plus basse possible du sous-arbre de gauche de node.
  Pour ce faire, nous vous recommandons d'appeler récursivement insert. NB : la fonction insert() renvoie un struct node *. Aussi, n'oubliez pas de stocker le noeud renvoyé par insert() dans votre structure de données (ne vous contentez pas d'appeler insert() sans tenir compte de sa valeur de retour, dit autrement comme si c'était une procédure ; vous auriez alors probablement des bugs à cette question ou aux questions suivantes).
  
• Si key est plus grand que node->key, insert insère key dans une feuille la plus basse possible du sous-arbre de droite de node.
  Pour ce faire, nous vous recommandons d'appeler récursivement insert. Même NB qu'au point précédent.
  
• Si key est égal à node->key, insert renvoie simplement node sans rien faire d'autre (ainsi, il n'y jamais deux valeurs identiques dans l'arbre).
• Puis, insert met à jour le champ height de node.

Question 3 : Codage des fonctions getKeyHeight() et getKeyRank()

Question 4 : Mise à jour du code pour équilibrer l'arbre au moment de sa construction

• z est le nœud le plus profond au niveau duquel la balance est strictement inférieure à -1 ou strictement supérieure à +1 ;
  
• x est le nœud petit-enfant de z, dont l'arbre contient la clé qui vient d'être insérée ;
  
• y est le nœud enfant de z, qui est parent de x.
  

Figure 3 : Traitement du cas Gauche-Gauche (figure provenant d'ici)

Figure 4 : Traitement du cas Droite-Droite (figure provenant d'ici)

Figure 5 : Traitement du cas Gauche-Droite (figure provenant d'ici)

Figure 6 : Traitement du cas Droite-Gauche (figure provenant d'ici)

1. codez la fonction static struct Node *rightRotate(struct Node *z) qui réalise le traitement présenté à la figure 3  et retourne la nouvelle racine du sous arbre (ici, y); par ailleurs, cette fonction modifie le champ height des nœuds y et z ;
   
2. codez la fonction static struct Node *leftRotate(struct Node *z) qui réalise le traitement présenté à la figure 4  et retourne la nouvelle racine du sous-arbre (ici y); par ailleurs, cette fonction modifie le champ height des nœuds y et z ;
3. ajoutez le calcul de la balance et le traitement des 4 cas à la fonction insert().
   

1. les tests test_equilibrageGaucheGauche, test_equilibrageDroiteDroite, test_equilibrageGaucheDroite et test_equilibrageDroiteGauche soient OK ;
2. valgrind ./testsUnitaires ne vous signale aucun problème d'accès mémoire ou de fuite mémoire.

Question 5 : Stockage de paires clé/valeur dans l'arbre AVL

1. ajoutez un champ char *value à la structure Node ;
2. ajoutez un paramètre char *value à la fonction newNode et recopiez le dans le champ value du nœud créé à l'aide de ce paramètre ;
3. ajoutez un paramètre char *value à la fonction insert et utilisez ce paramètre de manière adéquate dans cette fonction. En particulier, s'il existe déjà un nœud ayant pour clé key dans l'arbre, veillez à remplacer l'ancienne valeur du champ value de ce nœud à l'aide de ce paramètre ;
4. Complétez la fonction getValue()
   NB : il est probable que l'algorithme de recherche du nœud dans getValue()ressemble à s'y méprendre à l'algorithme de recherche du nœud dans getKeyHeight(). Pour éviter une duplication de code (jamais saine dans un projet), créez une fonction qui centralise ce code et qui est appelée par getValue()et getKeyHeight().
   

1. le test test_getValue soit OK ;
2. valgrind ./testsUnitaires ne vous signale aucun problème d'accès mémoire ou de fuite mémoire.

Livraison de votre travail sous Moodle

• Cas 1 : Cette commande affiche le message "===>  OK, fichier arbreAVL_usernameUnix.tgz genere : vous pouvez le remonter dans Moodle."
  La génération du fichier d'archive arbreAVL_usernameUnix.tgz s'est bien passée. Il ne vous reste plus qu'à remonter ce fichier dans Moodle.
• Cas 2 : cette commande affiche le message "make: ***  Aucune règle pour fabriquer la cible « arbreAVL_usernameUnix.c », nécessaire pour « gentgz ». Arrêt." (et/ou le même message concernant testsUnitaires_usernameUnix.c). Cela signifie que vous avez oublier de taper la commande cp  arbreAVL.c  arbreAVL_$USER.c (et/ou la commande cp concernant testsUnitaires.c) dans la phase préliminaire de cet exercice. Faites-le(s), puis tapez à nouveau make  gentgz
  

Page mise à jour le 22 mai 2017