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

typedef struct noeud noeud, *arbin;
struct noeud {int val;  arbin fg,fd; int taille;} vide[1]={{0,vide,vide,1}};
enum {sans, oncle, avl} eq=sans;

void aff(arbin a) { for(;a!=vide;a=a->fd) aff(a->fg), printf("%d ",a->val); }
void affarbinmarge(arbin a,int 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)
{ if(a==vide) a=malloc(sizeof(*a)),a->fg=a->fd=vide,a->val=x;
  if(x<a->val) a->fg=insere(a->fg,x);
  if(x>a->val) a->fd=insere(a->fd,x);
  return equi(a);
}
arbin enleve(arbin a,int x)
{ if(a==vide) ; else
  if(x<a->val) a->fg=enleve(a->fg,x); else
  if(x>a->val) a->fd=enleve(a->fd,x); else
  if(a->fd==vide) { arbin b=a->fg; free(a); a=b; } else
  if(a->fg==vide) { arbin b=a->fd; free(a); a=b; } else
  { arbin b=a->fd;
    while(b->fg!=vide) b=b->fg;
    a->fd=enleve(a->fd,a->val=b->val);
  }
  return equi(a);
}
arbin rotg(arbin a) { arbin b=a->fd; a->fd=b->fg; b->fg=equi(a); return b; }
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;)
  if(maxi(a->fd->fd->taille,a->fd->fg->taille)>a->fg->taille)
  { if(a->fd->fg->taille>a->fd->fd->taille) a->fd=rotd(a->fd);
    a=rotg(a);
  } else
  if(maxi(a->fg->fd->taille,a->fg->fg->taille)>a->fd->taille)
  { if(a->fg->fd->taille>a->fg->fg->taille) a->fg=rotg(a->fg);
    a=rotd(a);
  } else
  break;
  a->taille=eq==avl?1+maxi(a->fg->taille,a->fd->taille):a->fg->taille+a->fd->taille;
  return a;
}
typedef struct chainon chainon, *liste;
struct chainon {int val; liste suite;};
liste cree(int val,liste suite)
{ liste a=malloc(sizeof(*a));
  a->val=val;
  a->suite=suite;
  return a;
}
void affl(liste a)
{ for(;a;a=a->suite) printf("%d ",a->val);
  printf("\n");
}
liste a=0,b=0,c=0;
void p0(liste d) {d=a; a=b; b=d;}
void p1(liste d) {d=a; a=c; c=d;}
void p2(liste d) {d=a; a=d->suite; d->suite=b; b=d;}
void p3(liste d) {d=a->suite; a->suite=b->suite, b->suite=d;}
void p4(liste a) {if(a && a->suite) a->val+=a->suite->val, p4(a->suite);}
void p5(liste a) {if(a && a->suite) a->suite->val+=a->val, p5(a->suite);}
void p6(liste a) {if(a && a->suite) p6(a->suite), a->suite->val+=a->val;}
void p7(liste a) {if(a && a->suite) p7(a->suite), a->val+=a->suite->val;}
void abc()
{ printf("\n");
  printf("a="); affl(a);
  printf("b="); affl(b);
  printf("c="); affl(c);
}
void (*p[])(liste)={p0,p1,p2,p3,p4,p5,p6,p7};
int main()
{ int t[8]= { 0 , 2 , 1 , 3 , 4 , 5 , 6 , 7 }, i;
  arbin d=vide;
  for(i=0;i<8;i++) printf("%3d",t[i]), a=cree(t[i],a), p1(a), p0(a), abc();
  for(i=0;i<8;i++) p[t[i]](i&1?a:b), printf("p%d",t[i]), abc();
  for(eq=0;eq<2;eq++)
  { for(i=0;i<11;i++)
    { d=insere(d,(i<8?t[i]:i)*4%11);
      if(eq || i==10)  aff(d), affarbre(d);
    }
    while(d!=vide) d=enleve(d,d->val), aff(d), affarbre(d);
  }
  return 0;
}