#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
int ta=1;   // ta contient la taille de l'arbre
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.
  ++ta;                         // La taille l'arbre augmente.
  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), --ta; }
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;
  int n=taille(a), m, x;
  a=linearise(&z);           // a représente une liste chaînée par les fils gauches de longueur n.
  if(0)
  { 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.
  else
  for(b=&a;n&(n-1);b=&(*b)->fg,--n) *b=rotd(*b);  // tant que n n'est pas une puissance de 2
  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;
}
/*
Arbre équilibré.

Pour regarder si un élément se trouve dans un arbre binaire de recherche,
ou pour y ajouter ou en enlever un élément, on parcourt une seule branche de cette arbre.
Le temps pris par cette opération est donc proportionnel à la longueur de cette branche.
Donc l'insertion d'un élément dans un arbre binaire de recherche, peut prendre dans le pire des cas,
un temps proportionnel à la longueur de sa plus longue branche, qui est la hauteur de l'arbre.
Un arbre binaire de recherche de taille n a une hauteur comprise entre n-1,
dans le cas où il ne comporte qu'une seule branche et l'entier le plus proche au dessus du
logarithme binaire de n, dans le cas où toutes les branches ont à peu près la même longueur.
Pour que la recherche dans un arbre binaire de recherche soit la plus rapide possible,
on a donc intérêt à éviter qu'il y ait des branches trop longues.
On doit donc «équilibrer» les arbres binaires de recherche, ce que l'on fait en général,
en imposant à chacun de ses noeuds une certaine inégalité portant sur sa taille, sa hauteur
et celles de ses fils.
On en déduit un algorithme pour insérer (et un pour supprimer) un élément dans un arbre équilibré
de telle sorte qu'il reste équilibré.
Cette description est assez vague et correspond à des dizaines de méthodes connues différentes.

Temps de calcul d'un bon algorithme : O(ln n) ou O(ln n) amorti.

Puisque la hauteur d'un arbre de taille n est supérieure à log2(n), la recherche d'un élément
dans un arbre binaire de recherche dans le pire des cas prend au moins un temps en O(ln n).
Une méthode d'équilibrage peut donc être considérée comme satisfaisante si elle nous assure que
toute insertion ou suppression dans un arbre équilibré de taille n se fait en un temps en O(ln n).
Mais elle sera aussi satisfaisante si elle a un temps «amorti» en O(ln n), c'est-à-dire si
toute suite de k recherches, insertions et suppressions dans un arbre initialement vide et
dont la taille ne dépasse jamais n prend un temps total en O(k ln n).
Donc le temps moyen pris par une insertion, une suppression ou une recherche est en O(ln n).
Attention, ce n'est pas une espérance, ce n'est pas une propriété probabiliste.
La majoration porte sur le temps total pris par toute exécution d'un programme.


La méthode du bouc émissaire a été inventée par Igal Galperin et Ronald L. Rivest.
Scapegoat trees, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993, pages 165-174
(http://portal.acm.org/citation.cfm?id=313676)

Selon cette méthode, un arbre est équilibré si chaque sous-arbre a vérifie
hauteur(a)<= log(taille a)/log k
pour un certain réel k dans ]1,2[. Le plus petit sous-arbre non équilibré est le bouc émissaire.
Il est évidemment sacrifié. Sa structure d'arbre est détruite, et ses noeuds sont réutilisés pour
reconstruire un nouvel arbre dont toutes les branches ont presque la même longueur.
D'après Q. F Stout et B. L Warren, "Tree rebalancing in optimal time and space"
Communications of the ACM, Volume 29 ,  Issue 9  (Septembre 1986) pp: 902-908,
cette opération prend un temps proportionnel à la taille du bouc émissaire, mais elle se fait
rarement sur de gros arbres, et la méthode donne quand même un temps amorti en O(ln n).
Galperin et Rivest proposaient de noter dans chaque noeud, sa taille, sa hauteur et
s'il a été effacé ou non.
Dans : General balanced trees. Journal of Algorithms, 30: 1-28, 1999.
Arne Andersson explique que tout cela est inutile :
On peut supprimer les noeuds dès qu'ils sont inutiles.
On peut se passer de la hauteur, car au lieu de comparer le logarithme de la taille
à la hauteur, on peut le comparer à la longueur de la branche que l'on vient de rallonger.
On peut aussi se passer de la taille de chaque noeud, en ne gardant que la taille totale de l'arbre.
On ne cherche un bouc émissaire que lorsque l'on tombe sur une branche trop longue par rapport
à la taille totale de l'arbre. On calcule alors la taille des noeuds le long de cette branche,
en partant de la feuille au bout de la branche et en ajoutant à chaque fois la taille du frère,
que l'on obtient en comptant ses feuilles une par une.  On s'arrête dès qu'on trouve un noeud
de taille trop petite par rapport à la longueur de la branche déjà parcourue.
Ce noeud sera le bouc émissaire.

La relation  h<=log(t)/log(k)  peut se réécrire  t>=k^h ou t>=s en posant s=k^h.
On peut remplacer la variable h par la variable s.
Donc h=1 devient s=k et ++h devient s*=k.
En fait pour éviter de faire des calculs sur des nombres réels on prendra plutôt
s=2 et s+=(s+1)/2  avec s entier. Cela correspond à peu près à k=1.5
On peut aussi prendre s=2 et s+=s*2/3 qui correspond à k=5./3.
*/

abr bouc(abr a,elem x)
{ int ta=2, s=2;
  abr arrange(abr a)
  { if(x>a->clef) a->fd=arrange(a->fd), ta+=s?taille(a->fg):0; else
    if(x<a->clef) a->fg=arrange(a->fg), ta+=s?taille(a->fd):0; else
    return a;
    s+=(s+1)/2;
    if(s && s>ta) a=equilibre(a), s=0;  // on a touvé un bouc émissaire, s nul arrête tout.
    return a;
  }
  return arrange(a);
}
/*
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; 
}
*/
abr insere(abr a,elem x)
{ int s=2;
  abr *b=&a;                   // *b est l'arbre dans lequel insérer x  :  *b=insere(*b,x) 
  while(*b && (*b)->clef!=x) s+=(s+1)/2, b=x>(*b)->clef? &(*b)->fd : &(*b)->fg;
  if(*b) return a;             // *b est non nul quand x==(*b)->cle : x est déjà dans l'arbre        
  *b=n2(x);     
  return s>ta ? bouc(a,x) : a; // si la branche est trop longue, on cherche un bouc émissaire
}

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), --ta; else // Si *b n'a qu'un fils on le remplace par ce fils.
    if(!c->fg) *b=c->fd, free(c), --ta; 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;
}
/* 
1) Il fallait compléter la fonction bouc.

3) Ecrire un programme qui insère dans un arbre initialement vide tous les
entiers de 1 à 10^k puis les enlève.
Regarder le temps de calcul pour k=1, 2, 3, 4 et 5.

2) Dans ce programme l'arbre vide ne doit plus être représenté par le pointeur nul mais par :
noeud vide[1]={{0,vide,vide}};
Remplacer dans tous le programme les tests !a par a==vide etc.
Dans n2 remplacer 0 par vide.
Dans recherche, insere et enleve commencer par vide->clef=x; et remplacer
les tests a && a->clef!=x par a->clef!=x



Démonstration que la méthode du bouc émissaire a un temps de calcul amorti O(ln n) : 

On suppose que chaque noeud a d'un arbre binaire de recherche contient une
somme d'argent d'un montant de f(a)=max(0,|taille(fils_droit(a))-taille(fils_gauche(a))|-1).
On définit la fortune F(a) d'un arbre a comme la somme totale d'argent contenue dans tous ses noeuds.
f(a) est nul si et seulement si les tailles de ses deux fils diffèrent d'au plus 1.
Un arbre a dont tous les noeuds vérifient cette propriété, c'est-à-dire de fortune nulle
sera dit parfaitement équilibré.
On peut étudier comment varie la fortune d'un arbre lors de ses transformations.
1) Un bouc émissaire lorsqu'il est rééquilibré, perd toute sa fortune.
2) Lorsque l'on insère un élément dans un arbre (ou qu'on l'enlève de l'arbre)
sans le rééquilibrer, la somme d'argent f(a) rangée dans le noeud a, varie d'au plus un
si le noeud a se trouve sur la branche allant de la racine au nouveau noeud (ou au noeud supprimé)
et elle ne change pas si ce noeud n'est pas sur cette branche.
Donc la fortune de l'arbre n'augmente pas de plus que la longueur de cette branche.
La somme d'argent donnée à l'arbre est donc inférieure à sa hauteur.
3) Si le bouc émissaire se trouve à la distance h du noeud inséré, alors sa taille
s est trop petite par rapport à l'estimation h+1 de sa hauteur, donc s<k^(h+1).
Le fils du bouc émissaire se trouvant sur la branche menant au nouveau noeud,
a une taille x qui n'est pas trop petite par rapport à l'estimation h de sa hauteur,
donc x>k^h.
Donc s<kx.
Les tailles des deux fils du bouc émissaire sont x et s-x.
La somme d'argent rangée dans la racine du bouc émissaire est
f(a)=|x-(s-x)|-1=2x-s-1>s(2/k-1)-1.
La fortune du bouc émissaire qui est supérieure à s(2/k-1)-1 peut donc servir à payer
son rééquilibrage, qui coûte un temps O(s).

On peut déduire de tout cela que si on fait une suite de m transformations, (insertion ou
suppression) sur un arbre initialement parfaitement équilibré (par exemple vide),
selon la méthode du bouc émissaire, et que la taille de l'arbre ne dépasse jamais n,
alors à chaque opération on ne paiera pas plus que log_k(n).
Et cet argent sera suffisant pour payer tous les rééquilibrages de boucs émissaires.
Donc le temps total pris par toutes ses transformations, y compris les rééquilibrages,
sera en O(m log n).


Simplification de la méthode.
La démonstration précédente montre que la méthode du bouc émissaire marche avec un temps de
calcul acceptable pour n'importe quel k de l'intervalle ]1,2[, du moment que
les boucs émissaires sont rééquilibrés parfaitement.
Mais la procédure de rééquilibrage parfait, est un peu compliquée, et on peut se demander ce
qui se passe si on la simplifie un peu.
Lors du premier parcours de la liste chaînée des feuilles, on regroupe certaines feuilles
deux par deux de telle sorte que la longueur de la liste devienne une puissance de 2.
Dans un rééquilibrage parfait, ces arbres de taille 2 sont répartis équitablement
parmi les arbres de taille 1.
On peut, par exemple, mettre tous les arbres de taille deux en tête de liste.
Cela simplifie la procédure, puisqu'il suffit de parcourir la liste en regroupant
les feuilles deux par deux, jusqu'à ce que sa longueur soit une puissance de 2.
Les arbres obtenus ainsi ne sont plus parfaitement équilibrés. Ils ont une nette tendance
à pencher à droite. Dans le pire des cas, les deux fils de la racine sont de taille
2^h et 2^(h+1).
La démonstration précédente ne marche plus. Il faut l'adapter.
La somme d'argent rangée dans un noeud sera maintenant égale à sa taille.
La fortune T(a) d'un arbre a est donc la somme des tailles de ses noeuds.
C'est aussi la somme des longueurs des chemins menant à chacune des feuilles.
La procédure de rééquilibrage simplifiée rend un arbre de fortune T minimale.
Notons T(n) la fortune minimale d'un arbre de taille n.
T(2^h)=h 2^h
et T est affine de pente h+2 entre 2^h et 2^(h+1) pour tout entier h.
Pour tout n, le nombre T(n)/n est compris entre les parties entières inférieure et supérieure
de log2(n).
Lors du rééquilibrage d'un bouc émissaire de taille s ayant des fils de taille x >s/k et y=s-x,
sa fortune diminue d'au moins T(x)+T(y)+s-T(s) >= b*s  
pour un b >0 ne dépendant que de k, si k est suffisamment petit. 
Donc la méthode marche encore à condition de prendre k suffisamment petit.
*/