Arbres binaires de recherche équilibrés

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;

1. void update_height(node *t) met à jour la hauteur du noeud t. La fonction n'utilise que les hauteurs stockées dans les fils gauche et droit de t (s'ils sont non-NULL). La fonction ne parcourt pas l'arbre entier.
2. 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.
3. 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.
4. 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.
5. 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.

1. É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).
2. É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.
3. 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.

• 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.

• 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.

#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");