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
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
( 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
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
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
"Etre vrai, peu le peuvent."
Friedrich Nietzsche
"Etre vrai, peu le peuvent."
Friedrich Nietzsche
"Etre vrai, peu le peuvent."
Friedrich Nietzsche