#include <stdio.h>
#include <stdlib.h>
#include "AVL.h"


int abs(int n)
{
    if (n<0) return -n;
    return n;
}

int max(int n, int m)
{
    if (n>m) return n;
    return m;
}

int getHauteur(AVL* a)
{
    if (a==NULL) return -1;
    return a->hauteur;
}

int ecart(AVL* a)
{
    if (a==NULL) return 0;
    return getHauteur(a->filsG) - getHauteur(a->filsD);
}

AVL* rotationGauche(AVL* a)
{
     AVL* b = a->filsD;
     if (b==NULL) return a;
     AVL* c = b->filsG;
     b->filsG = a;
     a->filsD = c;
     a->hauteur = 1 + max(getHauteur(a->filsG), getHauteur(a->filsD));
     b->hauteur = 1 + max(getHauteur(b->filsG), getHauteur(b->filsD));
     return b;
}

AVL* rotationDroite(AVL* a)
{
     AVL* b = a->filsG;
     if (b==NULL) return a;
     AVL* c = b->filsD;
     b->filsD = a;
     a->filsG = c;
     a->hauteur = 1 + max(getHauteur(a->filsG), getHauteur(a->filsD));
     b->hauteur = 1 + max(getHauteur(b->filsG), getHauteur(b->filsD));
     return b;
}     

AVL* rotationGaucheDroite(AVL* a)
{
     if (a->filsG==NULL) return a;
     a->filsG = rotationGauche(a->filsG);
     return rotationDroite(a);
}
     
AVL* rotationDroiteGauche(AVL* a)
{
     if (a->filsD==NULL) return a;
     a->filsD = rotationDroite(a->filsD);
     return rotationGauche(a);
}

AVL* equilibrer(AVL* a)
{
     int e = ecart(a);
     if (e==2)
     {
              if (ecart(a->filsG) == 1)
                 a = rotationDroite(a);
              else
                 a = rotationGaucheDroite(a);
     }
     else if (e==-2)
     {
              if (ecart(a->filsD) == -1)
                 a = rotationGauche(a);
              else
                 a = rotationDroiteGauche(a);
     }
     else // juste recalculer la hauteur
          a->hauteur = 1 + max(getHauteur(a->filsG), getHauteur(a->filsD));
     return a;
}
                         

void afficher_(AVL* a, int h)
{
     int n;
     if (a == NULL)
     {
        for (n=0; n<h; n++) printf("   ");
        printf("VIDE\n");
     }
     else
     {
        afficher_ (a->filsD, h+1);
        for (n=0; n<h; n++) printf("   ");
        printf("%d\n",a->racine);
        afficher_ (a->filsG, h+1);
     }
        
}

void afficher(AVL* a)
{
     afficher_(a, 0);
}

AVL* inserer (int n, AVL* a) {
       if (a == NULL)
       {
               a = (AVL*)malloc(sizeof(AVL));
               a->racine = n;
               a->filsG = NULL;
               a->filsD = NULL;
               a->hauteur = 0;
               return a;
       }
       else if (a->racine<n) a->filsD = inserer(n, a->filsD);
       else if (a->racine>n) a->filsG = inserer(n, a->filsG);
       return equilibrer(a);
}

int maxValue(AVL* a) {
    if (a == NULL) return 0;
    if (a->filsD == NULL) return a->racine;
    return maxValue(a->filsD);
}

AVL* supprMax(AVL* a) {
    if (a == NULL) return a;
    else if (a->filsD == NULL)
    {
           AVL* fG = a->filsG;
           free(a);
           return fG;
    }
    else
    {
           a->filsD = supprMax(a->filsD);
           return equilibrer(a);
    }
}

AVL* supprimer(int n, AVL* a)
{
     if (a==NULL) return a;
     else if (n > a->racine) 
     {
          a->filsD = supprimer(n,a->filsD);
          return equilibrer(a);
     }
     else if (n < a->racine)
     {
          a->filsG = supprimer(n,a->filsG);
          return equilibrer(a);
     }
     else if (a->filsG==NULL) 
     {
          AVL* fD = a->filsD;
          free(a);
          return fD;
     }
     else if (a->filsD==NULL)
     {
          AVL* fG = a->filsG;
          free(a);
          return fG;
     }
     else { // les deux fils existent:
          a->racine = maxValue(a->filsG);
          a->filsG = supprMax(a->filsG);
          return equilibrer(a);
     }
}