Bonjour.

Sa peut paraitre débile... j'arrive pas a savoir si j'ai une fuite mémoire xD

Noeud* ArbreBinaire::rotationGauche(Noeud *noeud){
	Noeud *buffer = new Noeud(*noeud);
	*noeud = *(noeud->getNoeudSuperior());
	Noeud *buffer2 = new Noeud(*noeud->getNoeudInferior());
	noeud->setNoeudInferior(buffer);
	buffer->setNoeudSuperior(buffer2);

	return noeud;
}

Noeud* ArbreBinaire::rotationDroite(Noeud *noeud){
	Noeud *buffer = new Noeud(*noeud);
	*noeud = *(noeud->getNoeudInferior());
	Noeud *buffer2 = new Noeud(*noeud->getNoeudSuperior());
	noeud->setNoeudSuperior(buffer);
	buffer->setNoeudInferior(buffer2);

	return noeud;
}

A mon avis j'ai 2 delete a faire quelque part mais je sais pas ou..

Edit : Je précises que la prof nous impose un return.

-
Edité par -Crixus- 11 janvier 2021 à 0:47:13

Salut,

De base, je dirais que oui, tu as une fuite mémoire...

La raison est simple: les rotations gauches et droites sont sensées  travailler ... sur des noeuds existants. 

Il n'y a donc aucune raison d'allouer de la mémoire pour de nouveaux noeuds dans des deux fonctions et, si tu le fait, tu peux partir du principe que la mémoire allouée à ce moment là ne sera jamais libérée

Je suis d'accord... sauf que je bug pour le faire sans buffer lol.

Peut être :

Noeud*& ArbreBinaire::rotationGauche(Noeud *&noeud){
	Noeud *buffer = noeud;
	*noeud = *(noeud->getNoeudSuperior());
	buffer->setNoeudSuperior(noeud->getNoeudInferior());
	noeud->setNoeudInferior(buffer);

	return noeud;
}
Noeud*& ArbreBinaire::rotationDroite(Noeud *&noeud){
	Noeud *buffer = noeud;
	*noeud = *(noeud->getNoeudInferior());
	buffer->setNoeudInferior(noeud->getNoeudSuperior());
	noeud->setNoeudSuperior(buffer);

	return noeud;
}

-
Edité par -Crixus- 11 janvier 2021 à 1:47:43

Il "suffit" de partir d'une image précise de ta situation de départ...

Cette image est que tu as normalement deux structures qui ressemblent à

struct Noeud{
   Type valeur;
   Noeud * parent; // pas obligatoire
   Noeud * gauche;
   Noeud * droite;
};
struct ArbreBinaire{
   Noeud * racine;
};

( Cela peut être des classes ou des structures, et il peut y avoir des éléments de plus, cependant, la base indispensable s'arrête à ces différents éléments )

A partir de ces structures, tu dispose normalement de quatre données particulières:

- trois noeuds présentant les valeurs A, B et C, dont les données internes sont

valeur | parent  | gauche  | droite
   A   | nullptr | nullptr |   B
   B   |    A    | nullptr |   C
   C        B    | nullptr | nullptr

et qui pourraient donc être représentés sous une forme proche de

      A
     / \
        B
       / \
          C
         / \

- et un arbre, qui contient tes noeud, et dont le noeud "racine" pointe sur A

Ce que l'on souhaite avoir après la rotation gauche, c'est:

la racine de l'arbre qui pointe sur B et les noeud présentant les valeurs suivantes:

valeur | parent  | gauche  | droite
   A   |    B    | nullptr |   nullptr
   B   | nullptr |    A    |   C
   C        B    | nullptr | nullptr

et qui pourraient donc être représentés sous la forme de

    B
   / \
  A   C
 / \ / \

Le tout, en sachant que le noeud que tu vas transmettre à ta fonction est le noeud présentant la valeur A.  Hé bien, allons y...

Avant de commencer, il faut donc savoir que, à l'intérieur de la fonction, ton paramètre nommé noeud correspond au noeud A et que tu peux donc récupérer les deux autres noeuds (B et C) en accédant directement au pointeur "droite" des noeuds, sous une forme proche de

Noeud * rotationDroite(Noeud * noeud){
    Noeud * leB = noeud ->droite;
    Noeud * leC = leB->droite;
}

et, une fois que tu as cela, il "suffira" de corriger les différentes valeurs pour les pointeurs (gauche, droite et parent) des différents noeuds, sous une forme proche de

Noeud * rotationDroite(Noeud * noeud){
    Noeud * leB = noeud ->droite;
    Noeud * leC = leB->droite;
    // leB correspond à la racine, il n'a pas de parent
    leB->parent = nullptr; 
    // le noeud de gauche pour leB est noeud et le noeud de
    // droite est leC
    leB->gauche = noeud;
    leB->droite = leC;
    // noeud prend leB pour parent
    noeud->parent = leB;
    // il n'a pas de noeug gauche, il n'a pas de noeud droite
    noeud->gauche = nullptr;
    noeud->droite = nullptr;
    //leC fait pareil que noeud
    leC->parent = leB;
    leC->gauche = nullptr;
    leC->droite = nullptr;
    /* on renvoie la nouvelle racine de notre arbre,
     * c'est à dire leB
     */
    return leB;
}

C'est pas plus compliqué que cela

merci

le code complet :

Noeud*& ArbreBinaire::rotationGauche(Noeud *&noeud){
	Noeud *buffer = noeud;
	noeud = noeud->getNoeudSuperior();
	buffer->setNoeudSuperior(noeud->getNoeudInferior());
	noeud->setNoeudInferior(buffer);

	return noeud;
}
Noeud*& ArbreBinaire::rotationDroite(Noeud *&noeud){
	Noeud *buffer = noeud;
	noeud = noeud->getNoeudInferior();
	buffer->setNoeudInferior(noeud->getNoeudSuperior());
	noeud->setNoeudSuperior(buffer);

	return noeud;
}

Noeud* ArbreBinaire::rotationDroiteGauche(Noeud *noeud){
	noeud->setNoeudSuperior(rotationDroite(noeud));
	noeud = rotationGauche(noeud);
	return noeud;
}
Noeud* ArbreBinaire::rotationGaucheDroite(Noeud *noeud){
	noeud->setNoeudInferior(rotationGauche(noeud));
	noeud = rotationDroite(noeud);

	return noeud;
}
void ArbreBinaire::inserAVL(int v){

	insertValue(v);
	int inferior = 0;
	int superior = 0;
	if(noeud->getNoeudInferior()) inferior = desequilibre(noeud->getNoeudInferior() ); //0
	if(noeud->getNoeudSuperior()) superior = desequilibre(noeud->getNoeudSuperior() ); //2


	if( inferior-superior == 2){
		if(superior == 0){
			rotationDroite(noeud);
		}else{
			int inferiorChild = 0;
			int superiorChild = 0;
			if(noeud->getNoeudInferior()->getNoeudInferior()) inferiorChild = desequilibre(noeud->getNoeudInferior()->getNoeudInferior() );
			if(noeud->getNoeudInferior()->getNoeudSuperior()) superiorChild = desequilibre(noeud->getNoeudInferior()->getNoeudSuperior() );
			if( inferiorChild-superiorChild == 1){
				rotationDroite(noeud);
			}else{
				rotationGaucheDroite(noeud);
			}
		}
	}else if(superior-inferior == 2){
		if(inferior == 0){
			rotationGauche(noeud);
		}else{
			int inferiorChild = 0;
			int superiorChild = 0;
			if(noeud->getNoeudSuperior()->getNoeudInferior()) inferiorChild = desequilibre(noeud->getNoeudSuperior()->getNoeudInferior() );
			if(noeud->getNoeudSuperior()->getNoeudSuperior()) superiorChild = desequilibre(noeud->getNoeudSuperior()->getNoeudSuperior() );
			if( inferiorChild-superiorChild == 1){
				rotationGauche(noeud);
			}else{
				rotationDroiteGauche(noeud);
			}
		}
	}
}

-
Edité par -Crixus- 11 janvier 2021 à 15:34:31