:: Enseignements :: ESIPE :: E3INFO :: 2015-2016 :: Algorithmique ::

Arbres binaires de recherche équilibrés

Le but de ce TP est d'implémenter l'opération d'insertion 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 balance qui signifie la différence entre la hauteur du sous-arbre droit et celle du sous-arbre gauche :

typedef struct _node {
    int value;                 /* donnee stockee : un entier  */
    int balance;               /* la balance 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 balance de chaque noeud.

Exercice 1 - Insertion

Pour réaliser l'insertion 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.

void rotate_left(tree *t) effectue une rotation à gauche.
void rotate_right(tree *t) effectue une rotation à droite.
void rotate_right_left(tree *t) effectue une rotation à droite du sous-arbre droit de t et ensuite une rotation à gauche sur la racine de t.
void rotate_left_right(tree *t) effectue une rotation à gauche du sous-arbre gauche de t et ensuite une rotation à droite sur la racine de t.
int insertion_avl(tree *t, int val) insère l'élément val dans l'arbre binaire de recherche t et effectue ensuite les mises à jour et les rotations nécessaires pour l'équilibrer. La valeur de retour signifie le changement en hauteur résultant : 0 si l'arbre a la même hauteur qu'avant l'insertion et 1 si la hauteur de l'arbre a augmentée.