:: Enseignements :: ESIPE :: E3INFO :: 2016-2017 :: Algorithmique ::

Arbres binaires de recherche équilibrés

Le but de ce TP est d'implémenter les opérations d'insertion et de suppression dans un arbre 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 elt;                   /* 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 la 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 la balance 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 - 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 extract_min pour faciliter la mise à jour des hauteurs et le rééquilibrage des noeuds en remontant l'arbre.