#include<stdio.h>
#include<stdlib.h>
int maxi(int a,int b) { return a>b?a:b; }

typedef struct noeud noeud, *arbin;  // noeud = struct noeud    arbin = noeud*
struct noeud {int val;  arbin fg,fd; int taille;} vide[1]={{0,vide,vide,1}};
enum {sans,  // pas d'équilibrage
      oncle, // un oncle ne doit pas être plus petit que son neveu
      avl    // un oncle ne doit pas être plus bas que son neveu
     } eq=sans;

arbin nn(arbin fg,int val,arbin fd)   // rend l'adresse d'un nouveau noeud  
{ arbin a=malloc(sizeof(*a));         // situé dans une zone mémoire allouée par malloc
  *a=(noeud){val,fg,fd};              // et rempli avec les 3 valeurs passées en arguments
  return a;
}
void aff(arbin a) { for(;a!=vide;a=a->fd) aff(a->fg), printf("%d ",a->val); }
int somme(arbin a) { return a==vide?0:somme(a->fg)+a->val+somme(a->fd); }
arbin copie(arbin a) { return a==vide?a:nn(copie(a->fg),a->val,copie(a->fd)); } // ne copie pas les tailles
arbin recherche(arbin a,int x)
{ while(a!=vide && a->val!=x) a=x<a->val?a->fg:a->fd;
  return a;
}

void affarbinmarge(arbin a,int marge)    // affiche a sous forme d'arbre avec une marge à gauche de largeur MARGE.
{ if(a!=vide) affarbinmarge(a->fd,marge+3), printf("%*s%d\n",marge,"",a->val), affarbinmarge(a->fg,marge+3); }
void affarbre(arbin a) { printf("\n"), affarbinmarge(a,0); }

arbin equi(arbin);
arbin insere(arbin a,int x)    // b=insere(b,x) modifie l'arbre b en y ajoutant un noueud contenant la clé x
{ if(a==vide) a=nn(vide,x,vide);      else  //  un arbre vide est remplacé par un nouveau noeud sans fils contenant x
  if(x<a->val) a->fg=insere(a->fg,x); else  //  si x est grand, on l'insère dans le fils droit
  if(x>a->val) a->fd=insere(a->fd,x);       //  si x est petit, on l'insère dans le fils gauche
  return equi(a);                           //  met à jour la taille et rééquilibre éventuellement l'arbre
}
arbin insereit(arbin a,int x)   // version itérative mais sans équilibrage
{ arbin *b=&a;                  // on doit faire *b=insere(*b,x)
  while(*b!=vide && (*b)->val!=x) b= x<(*b)->val ? &(*b)->fg : &(*b)->fd ;
  if(*b==vide) *b=nn(vide,x,vide);
  return a;
}
arbin enleve(arbin a,int x)                    // a=enleve(a,x)  enlève x de l'arbre a
{ if(a==vide) ; else                           // Si a est vide il n'y a rien à faire.
  if(x<a->val) a->fg=enleve(a->fg,x); else     // Si x est petit, on l'enlève du fils droit.
  if(x>a->val) a->fd=enleve(a->fd,x); else     // Si x est grand, on l'enlève du fils gauche.
  if(a->fd==vide) { arbin b=a->fg; free(a); a=b; } else  // Si le noeud à enlever n'a qu'un fils
  if(a->fg==vide) { arbin b=a->fd; free(a); a=b; } else  // on le remplace par ce fils.
  { arbin b=a->fd;                             // Si a le noeud à enlever a deux fils
    while(b->fg!=vide) b=b->fg;                //  On cherche b le noeud le plus à gauche du fils droit de a.
    a->fd=enleve(a->fd,a->val=b->val);         //  On copie sa clé dans a puis on l'enlève du fils droit.
  }
  return equi(a);                              // On rééquilibre l'arbre a si nécessaire.
}
void libere(arbin a)                           // libère récursivement tous les noeuds d'un arbre.
{ if(a!=vide) libere(a->fg), libere(a->fd), free(a); }

arbin rotg(arbin a)    //      A     -->      B       arbre complet    :  A -> B 
{ arbin b=a->fd;       //    x   B          A   z     fils droit de A  :  B -> y
  a->fd=b->fg;         //       y z        x y        fils gauche de B :  y -> A
  b->fg=equi(a);       // le nouveau sous-arbre est rééquilibré si nécessaire
  return b;            // mais pas l'arbre complet, car cette rotation simple est
}                      // peut-être la première moitié d'une rotation double
arbin rotd(arbin a)
{ arbin b=a->fg;
  a->fg=b->fd;
  b->fd=equi(a);
  return b;
}
arbin equi(arbin a)
{ if(a==vide) return a;
  for(;eq;)                                                    // pas de rotation si eq==sans
  if(maxi(a->fd->fd->taille,a->fd->fg->taille)>a->fg->taille)  // si un petit fils dépasse le frère gauche de son père
  { if(a->fd->fg->taille>a->fd->fd->taille) a->fd=rotd(a->fd); //    (rotation double si petit fils interne)
    a=rotg(a);                                                 // on fait une rotation à gauche
  } else
  if(maxi(a->fg->fd->taille,a->fg->fg->taille)>a->fd->taille)  // si un petit fils dépasse le frère droit de son père
  { if(a->fg->fd->taille>a->fg->fg->taille) a->fg=rotg(a->fg); //    (rotation double si petit fils interne)
    a=rotd(a);                                                 // on fait une rotation à droite
  } else
  break;   // On arrête la boucle for quand on ne trouve plus de petit fils qui dépasse son oncle
  a->taille=eq==avl?1+maxi(a->fg->taille,a->fd->taille):a->fg->taille+a->fd->taille;  // hauteur ou taille
  return a;
}
arbin linearise(arbin a)
{ arbin *b=&a;                        // *b est l'arbre à linéariser
  for(;*b!=vide;b=&(*b)->fd)          // si *b n'est pas vide on se débarasse de son fils gauche par la ligne suivante, puis on linéarise le fils droit.
  for(;(*b)->fg!=vide;) *b=rotd(*b);  //    tant que *b a un fils gauche on lui applique une rotation à droite
  return a;
}
arbin egalise(arbin a)
{ noeud f={0,a,vide}, **b;
  for(a=linearise(&f);a!=&f;)
  for(b=&a;(*b)->fd!=vide;b=&(*b)->fd) *b=rotg(*b);
  return f.fg;
}

int main()
{ int i;
  arbin a=nn(nn(vide,6,nn(vide,8,vide)),7,nn(vide,10,vide)), b=copie(a);
  aff(a), printf("\n");
  aff(b), printf("\n");
  printf("somme=%d\n",somme(a));
  libere(b), a=b=vide;
  for(eq=0;eq<3;eq++)
  { for(i=0;i<10;i++) a=insere(a,i*3%10), affarbre(a);
    if(eq==sans) a=egalise(a),            affarbre(a);
    for(i=0;i<10;i++) a=enleve(a,i*3%10), affarbre(a);
  }
  return 0;
}