#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef struct inf {
    char *n,*pr;
    float s;
} *inf;

typedef struct Arbre {
    int cle;
    char color;
    struct inf E;
    struct Arbre *d,*g,*pa; // droit, gauche et pére (parent)
} *A;



A grandpere(A R){
    if(R!=NULL && R->pa!=NULL) return (R->pa->pa);
    else return NULL;
}
A oncle(A R){ A G=grandpere(R); // grand pére
    if(G==NULL) return NULL;
    else if(R->pa == G->g) return G->d;
    else return G->g;
}
// ---------------------------------------------->Rotations<-------------------------------------------------

void rotation_g(A R){ A gg=NULL,dg=NULL;
printf("\nRotation Gauche !\n");
if(R!=NULL && R->d!=NULL) {
        gg=R;//garder la racine
        if(R->d->g!=NULL) dg=R->d->g;//garder la gauche de droite de a
        R=R->d;//a devien la droite de a
        R->g=gg;
        gg->d=dg;//la doite du gauche de a devien la gauche du droite de a
        }
}
//rotation_droite
/*void rotation_d(A *R){ A dd=NULL,dg=NULL;
printf("\nRotation droite !\n");
if(*R!=NULL && R->g!=NULL) {
        dd=R;//garder la racine
        if(R->g->d!=NULL)dg=R->g->d;//garder la droite du gauche de a
        R=R->g;//a devien la gauche de a
        R->d=dd;//
        dd->g=dg;//la gauche du droite de a devien  la doite du gauche de a
        }
}*/
/*void rotation_d(A *R){ A dd=NULL,dg=NULL;
printf("\nRotation droite !\n");
if(*R!=NULL)printf("%d : ",(*R));
if(*R!=NULL && (*R)->g!=NULL) {
        dd=*R;//garder la racine
        if((*R)->g->d!=NULL)dg=(*R)->g->d;//garder la droite du gauche de a
        *R=(*R)->g;//a devien la gauche de a
        (*R)->d=dd;//
        dd->g=dg;//la gauche du droite de a devien  la doite du gauche de a
        }
}*/
void rotation_d(A *R){
A x=*R;
(*R)->g=NULL;
}
 // -----------------------------------------------------------------------------------------------------
A creation(int c, struct inf ET){
    A p=(A)malloc(sizeof(struct Arbre));
    p->E.n=(char*)malloc(sizeof(strlen(ET.n)+1));
    p->E.pr=(char*)malloc(sizeof(strlen(ET.pr)+1));
    strcpy(p->E.n,ET.n);
    strcpy(p->E.pr,ET.pr);
    p->cle=c;
    p->color='b'; // par défaut on l'associer la couleur blanc
    p->pa=NULL;
    p->d=NULL; p->g=NULL;
    return p;
}

void ajout(A p, A *r){ A R=*r; // P c'est le noeud déja créé, r la racine
    if(*r==NULL) *r=p; // si l'arbre est vide, le sommet est noire
    else {
    p->pa=*r; // comme le précédant pour les listes !
    if((*r)->cle> p->cle)  ajout(p,&(*r)->g,t);
    else ajout(p,&(*r)->d,t);
    }
eq_racine(p);
}
 // ---------------------------------------------->Equilibrage Insertion<-------------------------------------------------
void eq_racine(A R){
    if(R->pa==NULL) R->color='n'; // si le noeud est le racine on le colorer avec noire !
    else eq_test(R);
}

void eq_test(A R){
    if(R->pa->color=='n') return 0; // si le pére du noeud est noire on fair rien
    else eq_alpha_test(R);  // si'oncle est blanc
}

void eq_alpha_test(A R){
A O=oncle(R),G;
    if((O!=NULL) && (O->color=='b')){
        R->pa->color='n';
        O->color='n';
        G=grandpere(R);
        G->color='b';
        eq_racine(G); // on test si c'est le racine ( le racine doit être noire !)
    }
else eq_beta_test1(R); // la régle de béta pour l'arrêt !
}

void eq_beta_test1(A R){
    A G=grandpere(R);
    if((R == R->pa->d) && (R->pa == G->g)){ // si
        rotation_d(R->pa);
        }
    else if ((R == R->pa->g) && (R->pa == G->d)){
        rotation_g(R->pa);
    }
    printf("cle : %d\n",R->cle);
    eq_beta_test2(R);
}

void eq_beta_test2(A R){
    A G=grandpere(R);
    R->pa->color='n';
    G->color='b';
    if(R==R->pa->g) rotation_d(R);
    else rotation_g(R);
}

 // --------------------------------------------------------------------------------------------------------------------
 // ---------------------------------------------->Equilibrage Suppression<---------------------------------------------

 /*void supprimer(A *r, int c){
    if(*r==NULL) printf("Le code à supprimer n'existe pas !\n");
    else {
        if((*r)->c < c) supprimer(&(*r)->d,c);
        else if((*r)->c > c) supprimer(&(*r)->g,c);
        else {
            if((*r)->d==NULL) *r=(*r)->g;
            else if((*r)->g==NULL) *r=(*r)->d;
            else { fixer(suppmax(&(*r)->g),*r); }
        }
    }
}*/
  // --------------------------------------------------------------------------------------------------------------------

void affich(A r){
if(r!=NULL){
    /*printf("Le NOM : "); puts(r->E.n);
    printf("Le PRENOM : ");puts(r->E.pr);
    printf("Le SALAIRE : %.2f\n",r->E.s);*/
    printf("\nLe CLE : %d\n",r->cle);
    printf("Le Couleur : %c\n",r->color);
    affich(r->d);
    affich(r->g);
}
}

main(){
A *r=NULL,p=NULL;
int cle,ch,C,cc,t=0;
float salaire;
char nom[50],prenom[50];
struct inf ET;
do {
    printf("\n\n\t\t\t votre choix : "); scanf("%d",&ch);
    switch(ch){
        case 1: printf("\nDonner le nom : "); fflush(stdin); gets(nom); fflush(stdin);
                printf("\nDonner le nom : "); fflush(stdin); gets(prenom); fflush(stdin);
                printf("\nDonner la cle : "); scanf("%d",&cle); fflush(stdin);
                printf("\nDonner le salaire : "); scanf("%d",&salaire); fflush(stdin);
                ET.n=nom; ET.pr=prenom; ET.s=salaire;
                p=creation(cle,ET); free(&cle); free(&nom);
                ajout(p,&r);
                break;
        case 2: affich(r); break;
        case 3: rotation_d(&(p->pa)); break;
        //case 4: rotation_g(&x);

    }
}while(ch!=6);
return 0;
}