:: Enseignements :: ESIPE :: E3INFO :: 2018-2019 :: Algorithmique ::

Arbres binaires de recherche équilibrés

Le but de ce TP est d'implémenter les opérations d'un arbre binaire de recherche équilibré (AVL).

Récupérer l'archive Base.zip et extraire les fichiers dans votre répertoire de travail. La structure de données d'un noeud et d'un arbre se trouve dans le fichier avl.h. Cette structure intègre le champs height qui signifie la hauteur du sous-arbre enraciné dans ce noeud :

typedef struct _node {
    int data;                  /* donnee stockee : un entier  */
    int height;                /* la hauteur de ce sous-arbre */
    struct _node *left;        /* pointeur sur le fils gauche */
    struct _node *right;       /* pointeur sur le fils droit  */
} node;

La fonction write_tree a été mise à jour pour visualiser également le champs height de chaque noeud.

Exercice 1 - Rotation

Pour réaliser des rotations dans un arbre AVL, vous implémentez les fonctions suivantes (vues entièrement ou partiellement au cours). Vous utilisez la fonction de visualisation pour vérifier le comportement de vos fonctions. Vous pouvez également réutiliser le menu et les fonctions du tp précédent.

void update_height(node *t) met à jour la hauteur de l'arbre t. La fonction n'utilise que les hauteurs stockées dans les sous-arbres gauche et droit de t (s'ils sont non-NULL). La fonction ne parcourt pas l'arbre entier.
node *rotate_right(node *t) effectue une rotation à droite et met à jour les hauteurs des noeuds concernés. La fonction renvoie un pointeur sur la racine de l'arbre après la rotation.
node *rotate_left(node *t) effectue une rotation à gauche et met à jour les hauteurs des noeuds concernés. La fonction renvoie un pointeur sur la racine de l'arbre après la rotation.
node *rotate_left_right(node *t) effectue une rotation à gauche du sous-arbre gauche de t et ensuite une rotation à droite sur la racine de t. La fonction renvoie un pointeur sur la racine de l'arbre après les rotations.
node *rotate_right_left(node *t) effectue une rotation à droite du sous-arbre droit de t et ensuite une rotation à gauche sur la racine de t. La fonction renvoie un pointeur sur la racine de l'arbre après les rotations.

Exercice 2 - Insertion

Écrire une fonction int compute_balance(node *t) qui calcule et renvoie le facteur d'équilibrage de l'arbre t. La fonction n'utilise que les hauteurs stockées dans les sous-arbres gauche et droit de t (s'ils sont non-NULL).
Écrire une fonction node *rebalance(node *t) qui teste si le noeud t est déséquilibré et dans le cas échéant effectue les rotations nécessaires pour le rééquilibrer. La fonction renvoie un pointeur sur la racine de l'arbre après le rééquilibrage.
Modifier la fonction node *insert_bst(node *t, int elt) du tp précédent pour obtenir une fonction node *insert_avl(node *t, int elt) qui insère l'élément elt dans l'arbre binaire de recherche t et effectue ensuite les mises à jour et les rotations nécessaires pour l'équilibrer. La fonction renvoie un pointeur sur la racine de l'arbre après l'insertion.

Exercice 3 - Vérification

Écrire une fonction int is_avl(node *t) qui prend en argument un arbre binaire. La fonction renvoie 1 si

les hauteurs des champs height sont correctes et
l'arbre satisfait la propriété d'un arbre équlibré : hauteur(sous-arbre gauche)-hauteur(sous-arbre droit) = -1, 0 ou 1.

Sinon, la fonction renvoie 0.

Attention : Cette fonction ne vérifie pas si l'arbre est un arbre binaire de recherche.

Indice : Pour chaque noeud d'un parcours en profondeur, la fonction

récupère les hauteurs des deux fils (s'ils existent) et
- calcule la hateur du noeud lui-même et vérifie qu'elle équivaut à la valeur du champs height
- calcule le facteur d'équilibrage du noeud et vérifie qu'elle est -1, 0 ou 1
vérifie que les deux appels récursifs renvoient 1.

Tester les fonctions avec le code suivant :

#include <stdlib.h>
...
node *t = NULL;
int i;
for (i = 0; i < 100; i++) {
   t = insert_avl(t, i);
   if (!is_avl(t)) {
      printf("The tree is not balanced\n");
      exit(-1);
   }
}
printf("Ok!\n");

Exercice 4 - Chronométrage

Refaire l'exercice 4 - Chronométrage - du tp 9 en utilsant un arbre AVL.

Exercice 5 - Suppression [FACULTATIF]

Implémenter l'opération de suppression dans un arbre binaire de recherche équilibré.

Attention ! Il est conseillé d'utiliser une version récursive de la fonction extract_min pour faciliter la mise à jour des hauteurs et le rééquilibrage des noeuds en remontant l'arbre.