#include<stdio.h>
#include<stdlib.h>
typedef struct noeud *avl;
struct noeud{int cle,eq; avl fg,fd;};
int hauteur(avl a) {return a? hauteur(a->fd)+1-(a->eq>>1) : 0;}
void aff(avl a) {for(;a;a=a->fd) aff(a->fg), printf("%d ",a->cle);}
void affln(avl a) {printf("( "),aff(a),printf(")\n");}

void aff2(avl a,avl r) // dessine le sous-arbre a de l'arbre r
{ for(;a;a=a->fd)
  { avl p=a->fd;     int g, gg=2;    //On coupe
    a->fd=0, aff2(a->fg,r), a->fd=p; //la branche droite pendant la descente à gauche.
    for(p=r;p!=a;p=g ? p->fg : p->fd)//On va de r à a, en allant de préférence à droite
    g=!p->fd, printf(gg==g ? "|  " : "   "), gg=!g; // On écrit | à chaque virage. 
    printf("%c--+ (%d) %d\n", "/\\-"[gg], a->eq, a->cle);
  }
}
void affarbre(avl a) {putchar('\n'),aff2(a,a);}
inline int maxi(int a,int b){return a<b?b:a;}
void affv(avl a)
{ int t[30],l,p,j;
  void tiret(int i){while(j<i) putchar('-'),++j;}
  void aff(avl a,int n)
  { if(!a) return;
    aff(a->fg,++n);
    t[n]=6+maxi(t[n-1],maxi(t[n],t[n+1]));
    if(n!=l) ; else
    if(p) printf("%*d",t[n]-j,a->cle), j=t[n]; else
    { if(a->fg) printf("%*s/" ,t[n+1]-j-1,""          ),j=t[n+1],tiret(t[n]-1);
                printf("%*s%c",t[n  ]-j-1,"",'='+a->eq),j=t[n  ];
    }
    aff(a->fd,n);
    if(n==l && !p && a->fd) tiret(t[n+1]-1),putchar('\\'),++j;
  }
  putchar('\n');
  for(l=1;l<29;++l) for(p=2;p--;)
  { for(j=30;j--;) t[j]=0;
    j=0, aff(a,0), putchar('\n');
    if(!j) return;
  }
}
void erreur(char *m){printf("\nerreur %s\n",m);exit(1);}

int verifavl2(avl a,avl *xx)
{ int hg,hd;
  if(!a) return 0;
  hg=verifavl2(a->fg,xx);
  if(*xx && (*xx)->cle>=a->cle) erreur("clefs non croissantes");
  *xx=a;
  hd=verifavl2(a->fd,xx);
  if(hd-hg!=a->eq || a->eq<-1 || a->eq>1)
  printf("\nhg=%d hd=%d eq=%d",hg,hd,a->eq),erreur("champs eq incompatibles");
  return 1+maxi(hg,hd);
}
void verifavl(avl a) {avl x=0; verifavl2(a,&x);}
void totale(avl a) {affln(a), affarbre(a), verifavl(a), affv(a);}

avl cree(int x)
{ avl a=malloc(sizeof(*a));
  return a->cle=x, a->eq=0, a->fg=a->fd=0, a;
}
void tourne(avl *aa)                          /*  *aa=a          *aa=b    */
{ avl a=*aa, b;                               /*    / 1 \           / \   */
  if(a->eq>0) b=a->fd, a->fd=b->fg, b->fg=a;  /*   x     b  -->    a   z  */
  else        b=a->fg, a->fg=b->fd, b->fd=a;  /*        / \       / \     */
  *aa=b;                                      /*       y   z     x   y    */
}
void reequilibre(avl *aa)
{ avl a=*aa, *bb=a->eq>0?&a->fd:&a->fg, b=*bb;
  if(b->eq+a->eq)  tourne(aa), b->eq=-(a->eq-=b->eq); // rotation simple
  else tourne(bb), tourne(aa), a=*aa,                 // rotation double
  a->fg->eq=-(a->eq>0),
  a->fd->eq=  a->eq<0 , a->eq=0;
}
int ajoute(avl *aa,int x)  /* =1 ssi la hauteur augmente */
{ avl a=*aa;
  if(!a) return *aa=cree(x), 1;    // L'arbre est vide. On crée un nouveau noeud.
  if(x==a->cle) return 0;          // x est déjà dans l'arbre. On ne fait rien.
  { int d=x>a->cle, deq=d+d-1;     // x va à droite (d=1=deq) ou à gauche (d=0 deq=-1)
    if(!ajoute(d ? &a->fd : &a->fg,x)) return 0; // Le fils garde sa hauteur.
    if(a->eq!=deq) a->eq+=deq;     // On change eq puisqu'un des fils est plus haut.
    else           reequilibre(aa);// Si eq devient 1+1=2 ou -1-1=-2 on arrange l'arbre
    return (*aa)->eq!=0;           // La hauteur a augmenté ssi eq est non nul.
  }
}
int retire(avl *aa,int x)  /* =1 ssi la hauteur diminue */
{ avl a=*aa, b;
  if(!a) return 0;                 // L'arbre est vide. On ne fait rien.
  { int g=x<a->cle, deq=g+g-1;     // x est à gauche (g=1=deq) ou à droite (g=0 deq=-1)
    if(x!=a->cle) ; else           // Si x est la racine de l'arbre, il y a 2 cas :
    if(!a->fd) return *aa=a->fg,free(a),1; else//1) Sans fils droit on garde le gauche 
    { for(b=a->fd;b->fg;b=b->fg);  //  2) sinon la plus petite clé du sous-arbre droit
      a->cle=x=b->cle;             //     est copiée à la place de x (dans a) et
    }                              //     enlevée du fils droit (g=0 et x=b->cle).
    if(!retire(g ? &a->fg : &a->fd,x)) return 0; // Le fils garde sa hauteur.
    if(a->eq!=deq) a->eq+=deq;     // On change eq puisqu'un des fils est plus bas.
    else           reequilibre(aa);// Si eq devient 1+1=2 ou -1-1=-2 on arrange l'arbre
    return !(*aa)->eq;             // La hauteur a diminué ssi eq est nul.
  }
}
int main()
{ int i,n=10;  avl a=0;
  for(i=0;i<n;++i) ajoute(&a,i*3%n),totale(a);
  totale(a);
  for(i=0;i<n;++i) retire(&a,i*3%n),totale(a);
  i=getchar();
  return 0;
}