/* Si on veut que l'utilisation des arbres binaires de recherche
soit efficace, il faut qu'il n'y ait pas de branche trop grande.
On peut y arriver en utilisant les AVL, qui sont des arbres binaires
de recherche dans lesquels, pour chaque sommet, la différence entre
la hauteur du fils droit et celle du fils gauche vaut -1, 0 ou 1.
On garde cette différence rangée dans le champ EQ de chaque noeud.
On insère chaque élément grace à une procédure récursive comme pour
les arbres binaires de recherche, mais elle rend comme résultat
un booléen qui indique si la hauteur de l'arbre a augmenté (de 1).
Le facteur d'équilibrage est mis à jour, et s'il atteint 2 ou -2
on rééquilibre l'arbre.
La procédure de rééquilibrage suppose que le l'arbre qu'on lui passe est
un AVL correct, sauf au niveau de la racine dont le facteur d'équilibrage
vaut ±2 (mais EQ vaut ±1). Elle réarrange l'arbre en faisant une rotation
simple ou double. On sait que la hauteur de l'arbre a diminué (de 1),
quand le facteur d'équilibrage de la racine vaut 0.
booleen fonction ajoute(var avl a; entier x)
   si a=NULL alors
      a=nouveau_noeud(fg:=NULL, fd:=NULL, cle:=x, eq:=0)
      ajoute:=vrai
   sinon si x=a.cle alors
      ajoute:=faux
   sinon si x>a.cle alors
      si ajoute(a.fd,x) alors
         ++a.eq
         si a.eq=2 reequilibre(a)
         ajoute:= a.eq!=0
      sinon
         ajoute:=faux
      finsi
   sinon
     // on ajoute à gauche
   finsi
fin fonction ajoute
La procédure reequilibre traite les cinq cas suivants, et leur miroirs :
       h                          h-1
       A                           B
    /  2  \                     /  0  \
  h-3      h-1     ----->     h-2      h-2
   x        B                  A        z
          / 1 \              / 0 \
        h-3   h-2          h-3   h-3
         y     z            x     y

       h                           h
       A                           B
    /  2  \                     / -1  \
  h-3      h-1     ----->     h-1      h-2
   x        B                  A        z
          / 0 \              / 1 \
        h-2   h-2          h-3   h-2
         y     z            x     y

      h+3                                      h+2
       A                                        C
    /  2  \                                  /  0  \
   h       h+2                             /         \
   x        B      ----->                /             \
          /-1 \                     h+1                   h+1
        h+1    h                     A                     B
         C     t                 / 0,0,-1\             / 1,0,0 \
     /-1,0,1 \                  h       h,h,h-1   h-1,h,h       h
 h,h,h-1   h-1,h,h              x         y           z         t
   y           z                                                     */
#include<stdio.h>
#include<stdlib.h>
typedef struct noeud noeud, *AVL;
struct noeud{AVL fg,fd; int clef,eq;};
void aff(AVL a){ for(;a;a=a->fd) aff(a->fg), printf("%d ",a->clef); }

int somclef(AVL a)
{ return a ? a->clef+somclef(a->fg)+somclef(a->fd) : 0; }

int present1(int x, AVL a)
{ if(a) if(x==a->clef) return 1; else
        if(x< a->clef) return present1(x,a->fg);
        else           return present1(x,a->fd);
  else                 return 0;
}
int present2(int x, AVL a)
{ return a ? x==a->clef ? 1
                        : present2(x, x<a->clef ? a->fg : a->fd)
           : 0;
}
AVL present3(int x, AVL a)
{ while(a && x!=a->clef) a=x<a->clef ? a->fg : a->fd;
  return a;
}
void tourne(AVL *aa)
{ AVL a=*aa, b;
  if(a->eq>0) *aa=b=a->fd, a->fd=b->fg, b->fg=a;
  else        *aa=b=a->fg, a->fg=b->fd, b->fd=a;
}
void reequilibre(AVL *aa)
{ AVL a=*aa, *bb=a->eq>0 ? &a->fd : &a->fg, b=*bb, c;
  if(a->eq+b->eq) tourne(aa), a->eq=-(b->eq-=a->eq);
  else tourne(bb),tourne(aa), c=*aa,
       c->fd->eq=  c->eq<0,
       c->fg->eq=-(c->eq>0),
       c->eq=0;
}
int ajoute(int x,AVL *aa)
{ AVL a=*aa;
  if(!a)
  { *aa=a=malloc(sizeof(*a));
    a->clef=x;
    a->fg=a->fd=0;
    a->eq=0;
    return 1;
  }
  if(x==a->clef) return 0;
  { int deq=x<a->clef ? -ajoute(x,&a->fg) : ajoute(x,&a->fd);
    if(!deq) return 0;             /* la hauteur du fils n'a pas changé */
    if(a->eq==deq) reequilibre(aa);/* 1+1=2 ou -1+-1=-2  */
    else           a->eq+=deq;
    return !!(*aa)->eq;
  }
}
int ajoute2(int x,AVL *aa)
{ AVL a, *bb=aa, b, c;
  for(;a=*aa,a;aa=x<a->clef ? &a->fg : &a->fd)
   if(x==a->clef) return 0; else  /* x est déjà dans l'arbre */
   if(a->eq) bb=aa;               /* La hauteur de *aa ne changera pas */
  *aa=a=malloc(sizeof(*a));
  a->clef=x;
  a->fg=a->fd=0;
  a->eq=0;
  { int beq=(b=*bb)->eq;
    for(c=b;c!=a;) if(x<c->clef) c->eq=-1, c=c->fg;
                   else          c->eq= 1, c=c->fd;
    if(!beq) return 1;
    if(b->eq==beq) reequilibre(bb);
    else           b->eq=0;
    return 0;
  }
}
void affarb1(int marge,AVL a)
{ if(a)
   affarb1(marge+2,a->fd),
   printf("%*s%d\n",marge,"",a->clef),
   affarb1(marge+2,a->fg);
}
void affAVL1(AVL a){affarb1(0,a);}
void affarb2(int marge,char slash,AVL a)
{ if(a)
   affarb2(marge+2,'/',a->fd),
   printf("%*c-%d\n",marge+1,slash,a->clef),
   affarb2(marge+2,'\\',a->fg);
}
void affAVL2(AVL a){printf("\n"), affarb2(0,'-',a);}
void affarb3(AVL r,AVL a)
{ for(;a;a=a->fg)
  { int d, dd=2;
    AVL x=a->fg;
    a->fg=0, affarb3(r,a->fd), a->fg=x;
    for(x=r;x!=a;x=d ? x->fd : x->fg)
     d=!x->fg, printf(d==dd ? "|  " : "   "), dd=!d;
    printf(" %c-+(%2d)%d\n","/\\-"[dd],a->eq,a->clef);
  }
}
void affAVL3(AVL a){printf("\n"), affarb3(a,a);}

int verif(AVL a,AVL *xx)
{ if(a)
  { int hg=verif(a->fg,xx), hd;
    if(*xx && (*xx)->clef>=a->clef)
     printf("\n%d>=%d\n",(*xx)->clef,a->clef), exit(1);
    *xx=a;
    hd=verif(a->fd,xx);
    if(a->eq<-1 || a->eq>1 || a->eq!=hd-hg)
     printf("\nh(fg)=%d h(fd)=%d eq=%d\n",hg,hd,a->eq), exit(1);
    return 1+(hg<hd ? hd : hg);
  } else return 0;
}
void verifAVL(AVL a) {AVL x=0; verif(a,&x);}

AVL exclu;
int detache(int x,AVL *aa)
{ AVL a=exclu=*aa,b;
  int deq;
  if(!a) return 0;  /* x n'est pas dans l'arbre */
  if(x!=a->clef) deq=x<a->clef ? detache(x,&a->fg)
                               :-detache(x,&a->fd); else
  if(!a->fg) return *aa=a->fd, 1; else
  if(!a->fd) return *aa=a->fg, 1; else
  { for(b=a->fd;b->fg;b=b->fg);        /* b est le noeud suivant a */
    deq=-detache(b->clef,&a->fd);      /* On le détache            */
    exclu=a;
    b->fg=a->fg;      /* b vole les fils de a             */
    b->fd=a->fd;
    b->eq=a->eq;      /*        son facteur d'équilibrage */
    *aa=a=b;          /*     et son père                  */
  }
  if(!deq) return 0;  /* La hauteur du fils n'a pas changé */
  if(a->eq==deq) reequilibre(aa);
  else           a->eq+=deq;
  return !(*aa)->eq;
}
void affverif(AVL a)
{   aff(a), printf("%10d",somclef(a));
    affAVL1(a), affAVL2(a), affAVL3(a), verifAVL(a);
}
int main()
{ int i;
  AVL a=0;
  for(i=10;i--;) ajoute2(i*i%23,&a), affverif(a);
  for(i=10;i--;) detache(i*i%23,&a), affverif(a), free(exclu);
  return 0;
}