#include<stdio.h>
#include<stdlib.h>
/* Un arbre binaire est défini récursivement comme 
- ou bien une feuille, appelée aussi arbre vide,
- ou bien un noeud, appelé racine de l'arbre, qui contient une clé et
   deux (sous-)arbres, appelés fils droit et fils gauche.
Les noeuds d'un arbres sont les racines de ses sous-arbres.
En C en fait un arbre sera un pointeur sur un noeud, et l'arbre vide sera représenté
par une valeur spéciale de pointeur, comme le pointeur nul. */
typedef int elem;
typedef struct noeud noeud, *abr;
struct noeud { elem clef; abr fg,fd; };
/* La taille d'un arbre binaire est le nombre de ses feuilles.
C'est donc un de plus que le nombre de ses noeuds.
La taille est toujours un entier naturel strictement positif.
La taille d'un arbre représenté par un noeud est la somme des tailles de ses deux fils.
La hauteur d'un arbre binaire est la longueur de sa plus longue branche.
On peut calculer la taille et la hauteur avec les fonctions suivantes : */
int taille(abr a) { return a ? taille(a->fg)+taille(a->fd) : 1 ; }
int maxi(int a,int b) { return a>b?a:b;}
int hauteur(abr a) { return a ? 1+maxi(hauteur(a->fg),hauteur(a->fd)) : 0 ; }
/* Un arbre binaire est dit «de recherche» si la clé d'un noeud quelconque est toujours
strictement plus grande que toutes les clés de son sous-arbre gauche et strictement plus
petite que toutes les clés de son sous-arbre droit.
Autrement dit, les clés de l'arbre doivent être affichées dans l'ordre croissant par
la procédure récursive suivante : */
#define recursif 0
#if recursif
void aff(abr a) { if(a) aff(a->fg), printf(" %d",a->clef), aff(a->fd); }
/* Dans cette procédure, on peut remplacer le dernier appel récursif par une itération : */
#else
void aff(abr a) { for(;a;a=a->fd) aff(a->fg), printf(" %d",a->clef); }
#endif
void affln(abr a) {aff(a),printf("\n");}
/* recherche du noeud contenant une clé donnée */
#if recursif
abr recherche(abr a,elem x)
{ return !a         ? a :             // Si l'arbre est vide, on rend le pointeur nul.
         x==a->clef ? a :             // Si x est dans un noeud, on rend son adresse.
         x> a->clef ? recherche(a->fd,x) : // On cherche x à droite ou à gauche
                      recherche(a->fg,x) ; // selon qu'il est plus grand ou plus petit
}                                          // que la clé de la racine.
#else
abr recherche(abr a,elem x)
{ while(a && x!=a->clef) a=x>a->clef ? a->fd : a->fg;
  return a;
}
#endif

abr nn(abr fg,elem clef,abr fd) // nouveau noeud
{ abr a=malloc(sizeof(*a));     // a est l'adresse d'un nouveau noeud
  *a=(noeud){clef,fg,fd};       // dans lequel on range les 3 arguments de la fonction.
  return a;                     // On rend l'adresse de ce nouveau noeud.
}
abr n2(elem x) { return nn(0,x,0); }   // Nouvel arbre de taille 2
abr copie(abr a)                       // Crée un nouvel arbre de même forme, avec les mêmes clés 
{ return a ? nn(copie(a->fg),a->clef,copie(a->fd)) : a ; }
abr eipoc(abr a) // crée un arbre contenant des clés de signe opposé
{ return a ? nn(eipoc(a->fd),-a->clef,eipoc(a->fg)) : a ; }
void test(abr b,abr a)    // vérifie que b->clef < a->clef si b est non nul
{ if(b && b->clef>=a->clef) printf("raté %d<%d\n",b->clef,a->clef), exit(1); }
void verif(abr a)
{ abr b=0;          // dernier noeud visité.
  void ver(abr a)   // procédure récursive de parcours infixe de l'arbre.
  { for(;a;a=a->fd)
     test(a->fg,a), // Cette ligne arrête le programme quand par exemple a->fg->fg==a
     ver(a->fg),
     test(b,a), b=a;// On vérifie que les clés sont dans l'ordre croissant.
  }
  ver(a);           // Unique instruction de verif.
}
void affarbre(abr r)  // affichage sous forme d'arbre couché vers la gauche
{ void af(abr a)      // procédure récursive qui affiche le sous-arbre a de l'arbre r
  { for(;a;a=a->fg)
    { int dd,d=2;
      abr p=a->fg;
      a->fg=0, af(a->fd), a->fg=p;  // pendant l'appel récursif à droite, on ôte le fils gauche
      for(p=r;p!=a;p=d?p->fd:p->fg) dd=d,d=!p->fg,printf(dd-!d?"   ":"|  ");
      printf("%c--+  %d\n","\\/-"[d],a->clef);
    }
  }
  af(r);              // unique instruction de affarbre
}
void Aff   (abr a) { affln(a), affarbre(a), verif(a); }
void libere(abr a) { if(a) libere(a->fg), libere(a->fd), free(a); }
abr  rotg  (abr a) { abr b=a->fd; a->fd=b->fg, b->fg=a; return b; }
abr  rotd  (abr a) { abr b=a->fg; a->fg=b->fd, b->fd=a; return b; }
#if recursif
abr linearise(abr a)    // rend un arbre linéaire, c'est-à-dire, avec une seule branche
{ if(!a) return a;      // Si l'arbre est vide, il n'y a rien à faire.
  while(a->fd) a=rotg(a);  // Tant qu'il y a un fils droit, on fait des rotations à gauche.
  a->fg=linearise(a->fg);  // Puis on linéarise le fils gauche.
  return a;
}
#else
abr linearise(abr a)
{ abr *b;
  for(b=&a;*b;b=&(*b)->fg) while((*b)->fd) *b=rotg(*b);
  return a;
}
#endif
/* Pour rééquilibrer un arbre de taille n, on fait d'abord une liste chaînée de ses n feuilles.
Puis on fusionne deux par deux ces arbres de taille 1 pour obtenir une liste d'arbres de taille
2, (sauf peut-être le dernier de la liste qui sera de taille 1 si n est impair).
Puis on fusionne ces arbres deux par deux pour obtenir une liste d'arbres équilibrés de taille 4,
etc.. On s'arrête quand la liste ne contient plus qu'un arbre équilibré de taille n.
La liste chaînée est obtenue en chaînant les noeuds selon le fils gauche. Les arbres équilibrés
sont rangés dans les fils droits des maillons. Donc la liste d'arbres vides initiale s'obtient
en linéarisant l'arbre initial. L'unique maillon de la liste finale doit être retiré. On ne
garde que son fils droit qui est l'arbre final. Il faut donc au début rajouter un noeud
dont la clé est virtuellement plus petite que toutes les clés de l'arbre initial. C'est pourquoi
avant la linéarisation, on ajoute un noeud z qui a pour fils droit l'arbre initial.
La liste est de longueur 1 quand son premier maillon est z. Le test a!=&z est donc équivalent à a->fg.
Dans la discution précédente, n est bien la taille de l'arbre a initial, c'est-à-dire son nombre
de noeuds augmenté d'un. C'est donc bien le nombre de noeuds de l'arbre (linéarisé ou pas)
augmenté du noeud z.
On aurait pu allouer z par un appel à malloc (ou à nn), mais il aurait fallu faire un appel
à free à la fin de la procédure. Il est donc plus simple, et un peu plus efficace, de déclarer
z comme une variable de type noeud locale à la procédure, qui est automatiquement détruite
à la sortie de la procédure.
b est un pointeur sur un pointeur sur un noeud, autrement dit un pointeur sur un abr, comme
dans la procédure précédente.
La fusion de deux arbres de taille 2^k en un arbre de taille 2^{k+1} se fait par une rotation
à droite : *b=rotd(*b) */
abr equilibre(abr a)     // Rééquilibre l'arbre a en un temps proportionnel à sa taille
{ noeud z={0,0,a}, **b;
  a=linearise(&z);           // a représente une liste chaînée par les fils gauches
  { int n=taille(a)-1, m, x; // n est longueur de cette liste 
    for(m=1;m<n;m+=m) ;      // m est la plus petite puissance de 2 telle que m>=n
    if(n<m) for(b=&a,x=0,n-=m/=2;*b;b=&(*b)->fg) if(x+=n,x>=m) *b=rotd(*b),x-=m;
  }               // a est une liste de taille m/2 formée d'arbres de taille 1 ou 2, bien répartis.
  while(a!=&z)    // à chaque itération sa longueur est divisée par 2.
  for(b=&a;*b && (*b)->fg;b=&(*b)->fg) *b=rotd(*b);
  return z.fd;
}
#if recursif
abr insere(abr a,elem x)       // rend l'arbre obtenu en insérant x dans a     
{ if(   !a    ) a=n2(x)              ; else  // Si a est vide on rend un nouvel arbre de taille 2
  if(x<a->clef) a->fg=insere(a->fg,x); else  // On insère x dans le fils gauche
  if(x>a->clef) a->fd=insere(a->fd,x);       // ou le droit.
  return a; 
}
#else
abr insere(abr a,elem x)
{ abr *b=&a;                   // *b est l'arbre dans lequel insérer x  :  *b=insere(*b,x) 
  while(*b && (*b)->clef!=x) b=x>(*b)->clef? &(*b)->fd : &(*b)->fg;
  if(!*b) *b=n2(x);            // *b est non nul quand x==(*b)->cle : x est déjà dans l'arbre
  return a; 
}
#endif
elem pluspetit(abr a) { while(a->fg) a=a->fg; return a->clef; }
abr enleve(abr a,elem x)
{ abr *b=&a;    // *b est l'arbre duquel enlever x : *b=enleve(*b,x)
  while(*b && (*b)->clef!=x) b=x>(*b)->clef? &(*b)->fd : &(*b)->fg;
  if(*b)        // *b est non nul donc (*b)->cle==x, c'est le noeud à supprimer.
  { abr c=*b;
    if(!c->fd) *b=c->fg, free(c); else // Si *b n'a qu'un fils on le remplace par ce fils.
    if(!c->fg) *b=c->fd, free(c); else // Cette ligne limite la récursivité à 2 niveaux.
    c->fd=enleve(c->fd,c->clef=pluspetit(c->fd));
  }
  return a;
}
int main()
{ int i;
  abr a=nn(n2(1),2,n2(3)), b=copie(a), c=eipoc(a);
  Aff(a);
  Aff(b); libere(b);
  Aff(c); libere(c);
  for(i=0;i<10;i++) a=insere(a,i*3%10*2), Aff(a);
  Aff(a);
  a=equilibre(a);
  Aff(a);
  for(i=0;i<30;i+=3) printf("%d %s\n",i,recherche(a,i)?"oui":"non");
  for(i=0;i<10;i++) a=enleve(a,i*3%10*2), Aff(a);
  return 0;
}