kdo de noel

/************************************************************************/
/* Auteur : S. Gueye							*/
/* TP : Arbres Binaires	de Recherche					*/
/* Date dernière maj : 25/11/2019					*/
/************************************************************************/

#include <iostream>
#include <fstream>
#include <algorithm>
#include "ABR.h"

using namespace std;

/****************************************/
/* Objectif : Constructeur d'un noeud dont les fils sont NULL
/* Entrées : entier x
/* Complexité : 0(1)
/****************************************/
noeud::noeud(int x)
{
	cle = x;
	fg = fd = pere =  NULL;
	h = d = 0;
}


/****************************************/
/* Objectif : Destructeur d'un noeud
/****************************************/
noeud::~noeud()
{
	if(fg)
		delete(fg);
	if(fd)
		delete(fd);
}

/****************************************/
/* Objectif : Constructeur d'un ABR
/****************************************/
ABR::ABR()
{
	r = NULL;
}


/****************************************/
/* Objectif : Constructeur d'un ABR
/****************************************/
ABR::ABR(char* filename)
{
	r = NULL;
	ifstream file(filename);
	int n,tmp,cpt = 0;

	file >> n;
	for(int i = 0; i < n ; i++){
		file >> tmp;
		if(insertion(tmp)){
			cpt++;
		}
	}

	cout << "Nombre d'éléments insérés = " << cpt << endl;
	cout << "Hauteur de l'arbre = " << hauteur() << endl;
	cout << "Affichage infixe = ";
	infixe(r);
	cout << endl;
	file.close();
}



/****************************************/
/* Objectif : Destructeur d'un AB
/****************************************/
ABR::~ABR()
{
	if(r)
		delete(r);
}

/****************************************/
/* Objectif : Accesseur à la racine r
/****************************************/
noeud* ABR::root()
{
	return(r);
}

/****************************************/
/* Objectif : Parcours infixe
/****************************************/
void ABR::infixe(noeud* x)
{
	if(x){
		infixe(x->fg);
		cout << " " << x->cle;
		infixe(x->fd);
	}
}

/****************************************/
/* Objectif : Renvoie la hauteur de l'arbre de
racine r
/****************************************/
int ABR::hauteur()
{
	return(r->h);
}

/****************************************/
/* Objectif : Insertion de "cle" dans l'arbre
/* Une cle étant un identifiant. Il faudra vérifier que celle
que l'on veut insérer n'existe pas déjà dans l'arbre.
Si oui il ne faudra pas l'insérer.

- La méthode doit renvoyer "vrai" si l'insertion a pu être faite
et "faux" sinon.
- Si l'insertion a été faite le message suivant est affiché :
		cout << "Insertion de : " << cle << " " << endl;
/****************************************/
bool ABR::insertion(int cle)
{
	noeud * y;
	noeud* x = r;
	noeud* pere = NULL;
	bool existe = false;

	while(x != NULL){

		pere = x;
		if(cle < x->cle)
			x = x->fg;
		else
		if(cle > x->cle)
			x = x->fd;
		else{
			existe = true;
			x = NULL;
		}
	}

	if(! existe){
		cout << "Insertion de : " << cle << " " << endl;
		y = new noeud(cle);

		if(pere == NULL)
			r  = y;
		else{
			y->pere = pere;
			if(cle < pere->cle){
			    pere->fg = y;
			}

			else{
			    pere->fd = y;
			}
		}

        // Réquilibrage de l'arbre à partir du père du nouveau noeud inséré.
		if(y->pere != NULL){
		    requilibre(y->pere);
		}

	}

	return(!existe);
}


/****************************************/
/* Objectif :
/* Rotation droite à partir de x
/* x et x->fg sont supposés non nuls.
/****************************************/
void ABR::rotationDroite(noeud* x)
{
	// Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
	// l'exécution
	cout << "rotationDroite................" << endl;
	noeud *G = x->fg;
	x->fg = G->fd;
	G->fd = x;

	if(x->fg!=NULL){
	    x->fg->pere = x;
	}
	if(x->pere!=NULL){
	    if(x==x->pere->fg){
	        x->pere->fg = G;
	    }
	    else{
	        x->pere->fd = G;
	    }
	}
	G->pere = x->pere;
	x->pere = G;

	// calcul de h et d pour x
	if(x->fd && x->fg){
        x->h = max(x->fg->h,x->fd->h)+1;
        x->d = (x->fg->h) - (x->fd->h);
    }
    else if((x->fg==NULL)&&(x->fd==NULL)){
        x->h = 0;
        x->d = 0;
    }
    else if(x->fg==NULL){
        x->h = (x->fd->h)+1;
        x->d = -1 - (x->fd->h);
    }
    else{
        x->h = (x->fg->h)+1;
        x->d = (x->fg->h)+1;
    }

    //calcul h et d pour G
    if(G->fd && G->fg){
        G->h = max(G->fg->h,G->fd->h)+1;
        G->d = (G->fg->h) - (G->fd->h);
    }
    else if((G->fg==NULL)&&(G->fd==NULL)){
        G->h = 0;
        G->d = 0;
    }
    else if(G->fg==NULL){
        G->h = (G->fd->h)+1;
        G->d = -1 - (G->fd->h);
    }
    else{
        G->h = (G->fg->h)+1;
        G->d = (G->fg->h)+1;
    }
    x = G;
    if(x->pere==NULL){
	    r = x;
	}
}

/****************************************/
/* Objectif : Rotation gauche à partir de x
/* x et x->fd sont supposés non nuls.
/****************************************/
void ABR::rotationGauche(noeud* x)
{
	// Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
	// l'exécution
	cout << "rotationGauche................" << endl;
	noeud *L = x->fd;
	x->fd = L->fg;
	L->fg = x;
	if(x->fd!=NULL){
	    x->fd->pere = x;
	}
	if(x->pere!=NULL){
	    if(x==x->pere->fg){
	        x->pere->fg = L;
	    }
	    else{
	        x->pere->fd = L;
	    }
	}
	L->pere = x->pere;
	x->pere = L;
	//calcul h et d pour x
	if(x->fd && x->fg){
        x->h = max(x->fg->h,x->fd->h)+1;
        x->d = (x->fg->h) - (x->fd->h);
    }
    else if((x->fg==NULL)&&(x->fd==NULL)){
        x->h = 0;
        x->d = 0;
    }
    else if(x->fg==NULL){
        x->h = (x->fd->h)+1;
        x->d = -1 - (x->fd->h);
    }
    else{
        x->h = (x->fg->h)+1;
        x->d = (x->fg->h)+1;
    }

    //calcul h et d pour L
    if(L->fd && L->fg){
        L->h = max(L->fg->h,L->fd->h)+1;
        L->d = (L->fg->h) - (L->fd->h);
    }
    else if((L->fg==NULL)&&(L->fd==NULL)){
        L->h = 0;
        L->d = 0;
    }
    else if(L->fg==NULL){
        L->h = (L->fd->h)+1;
        L->d = -1 - (L->fd->h);
    }
    else{
        L->h = (L->fg->h)+1;
        L->d = (L->fg->h)+1;
    }
	x = L;
	if(x->pere==NULL){
	    r = x;
	}
}

/****************************************/
/* Objectif : Rotation droite-gauche à partir de x
/* x et x->fd sont supposés non nuls.
/****************************************/
void ABR::rotationDroiteGauche(noeud* x)
{
	// Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
	// l'exécution
	cout << "rotationDroiteGauche.........." << endl;
	rotationDroite(x->fd);
	rotationGauche(x);

    // !!! A COMPLETER !!! //
}

/****************************************/
/* Objectif : Rotation gauche-droite à partir de x
/* x et x->fg sont supposés non nuls.
/****************************************/
void ABR::rotationGaucheDroite(noeud* x)
{
	// Ne pas effacer ce message qui sert à suivre ce qui se passe pendant
	// l'exécution
	cout << "rotationGaucheDroite.........." << endl;
	rotationGauche(x->fg);
	rotationDroite(x);

    // !!! A COMPLETER !!! //
}

/****************************************/
/* Objectif : Requilibre (si nécessaire) l'arbre en partant
de x et en remontant les pères. x est supposé non nul.
/****************************************/
void ABR::requilibre(noeud* x)
{
    //initialise la hauteur
    int vraiHauteur = x->h;

    //Calcul de h et d
    if(x->fd && x->fg){
        x->h = max(x->fg->h,x->fd->h)+1;
        x->d = (x->fg->h) - (x->fd->h);
    }
    else if((x->fg==NULL)&&(x->fd==NULL)){
        x->h = 0;
        x->d = 0;
    }
    else if(x->fg==NULL){
        x->h = (x->fd->h)+1;
        x->d = -1 - (x->fd->h);
    }
    else{
        x->h = (x->fg->h)+1;
        x->d = (x->fg->h)+1;
    }

    // Test pour rotation
    if(x->d!=0){
        if((x->d == 2)&&(x->fg->d==1)){
            rotationDroite(x);
        }
        else if((x->d==-2)&&(x->fd->d==-1)){
            rotationGauche(x);
        }
        else if((x->d==2)&&(x->fg->d==-1)){
            rotationGaucheDroite(x);
        }
        else if((x->d==-2)&&(x->fd->d==1)){
            rotationDroiteGauche(x);
        }
    }
    if((vraiHauteur != x->h)&&(x->pere)){
        requilibre(x->pere);
    }

}