Implémentation d'un arbre rouge et noir
[Ce post est un peu à cheval entre le C++ et l'algorithmique, veuillez m'en excuser]
Bonjour tout le monde.
Je suis en train d'implémenter un arbre rouge et noir en C++. Il est évident qu'il existe de nombreuses librairies sur le net l'ayant déjà implémenté. De même l'utilisation de la STL m'avancerait beaucoup. Cependant, débutant en C++ mais aussi ne maîtrisant pas encore parfaitement les arbres équilibrés et tout ce qui va avec, j'essaye de coder tout cela moi même dans le but de mieux comprendre et de parfaire mes connaissances en C++.
Je n'ai pour l'instant qu'une partie de l'interface de la classe Arbre_RN et une partie de la classe Noeud (je l'utilise aussi pour une liste chaînée en mettant les pointeurs gauche, droite et père à NULL, la couleur, rouge ou noir, n'intervenant pas non plus).
Sans plus attendre, un petit bout de code avant quelques questions :D
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #define RED true
#define BLACK false
class noeud
{
public:
noeud ( const int & info, noeud * suiv = NULL ) // constructeur1
{
Cle = info ;
Suivant = suiv ;
Gauche = Droite = P = NULL;
Couleur = true;
}
noeud ( noeud * suiv = NULL ) {Suivant = suiv ;}
~noeud (){}
noeud * GetGauche() {return Gauche;}
noeud * GetDroite() {return Droite;}
noeud * GetP() {return P;}
int GetCle() {return Cle;}
bool GetCouleur() {return Couleur;}
private:
int Cle ;
noeud * Suivant ;
noeud * Droite ;
noeud * Gauche ;
noeud * P ;
bool Couleur;
} ; |
Et la classe Arbre_RN :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include "NOEUD.H"
class Arbre_RN
{
public:
Arbre_RN();
~Arbre_RN();
void Rotation_Gauche (const int &);
void Rotation_Droite (const int &);
void Supprimer();
void Diminuer_Cle();
void Union();
void Extraire_Minimum();
void Minimum();
void Inserer(const int &);
private:
}; |
Comme tout le monde peut le constater, c'est loint d'être complet et même parfait :lol: , mais ça va venir :wink: .
J'ai donc quelques questions, si vous pouviez y répondre ce serait bien sympathique, merci :D
J'essaye de me baser sur les algos du livre "Introduction à l'algorithmique " de Cormen. et je devrais dire de faire le plus possible comme dans le bouquin car c'est avant tout un projet d'algo et non de programmation.
:arrow: Pour la racine de l'arbre, je suppose qu'un pointeur privé sur un noeud ferait l'affaire ?
:arrow: Comment implémenter NIL de la même façon que l'algo de Cormen ? ie "Pour un arbre RN T, la sentinelle nil[T] est un objet ayant les mêmes champs qu'un noeud ordinaire. Tous les pointeurs vers NIL, donc les feuilles, sont remplacés par des pointeurs vers la sentinelle nil[T].
:arrow: La procédure Insérer prend normalement en paramètre un Noeud crée auparavant. N'est-t-il pas possible de simplement passer en paramètre sa Clé puisque c'est la seule information contenue dans le noeud non modifiée après l'insertion ?
:arrow: Question bête mais je préfere demander confirmation : l'arbre ne gère pas les noeuds... il ne gère que les pointeurs ? Donc je ne sais pas trop comment bien gérer la suppression ou la création des noeuds en mémoire. Par exemple pour la procédure Insérer, en passant juste la clé du noeud à insérer, je pensais faire un "new Noeud" et donc forcément dans la procédure Supprimer faire un "delete"....
:arrow: Pour le constructeur, tout ce que j'ai à faire, c'est de créer un noeud racine ?
:arrow: Si je veux implémenter un constructeur par copie., je vais devoir recréer tous les noeuds ? ou bien juste copier les pointeurs ? (cf questions sur la gestion de mémoire merdique)
:arrow: J'ai surement d'autres questions qui vont venir, mais ça serait bien d'eclaircir tout cela d'abord :)
Pour vous donner un peu plus une idée de ce que je fais : je dois implémenter différentes structures de données (liste, arbre RN et tas binomial) qui chacunes vont me servir de file de priorités (en l'occurrence de priorité minimum) pour implémenter divers algos sur les graphes. D'ailleurs je ne sais pas encore représenter mon graphe avec ces structures... mais chaque choses en son temps :D
Donc je vous remercie déjà d'avoir tout lu, lol. Et suis ouvert à toute suggestion, critique , manière de procéder, lien etc... car j'en aurais bien besoin :?
Mici beaucoup les amis :lol:
Re: Implémentation d'un arbre rouge et noir
Citation:
Envoyé par Nicodemus
Code:
1
2
| #define RED true
#define BLACK false |
Pourquoi un #define, alors qu'on a des constantes ? Encore qu'ici, j'utiliserai plutôt un enum, histoire d'augmenter la qualité du typage.
Citation:
Envoyé par Nicodemus
J'essaye de me baser sur les algos du livre "Introduction à l'algorithmique " de Cormen. et je devrais dire de faire le plus possible comme dans le bouquin car c'est avant tout un projet d'algo et non de programmation.
Je n'ai pas ce livre, donc désolé si je réponds à côté.
Citation:
Envoyé par Nicodemus
:arrow: Pour la racine de l'arbre, je suppose qu'un pointeur privé sur un noeud ferait l'affaire ?
Probablement, oui. Par contre, je vois pas mal de pointeurs, as-tu défini une politique de durée de vie pour les objets pointés ? A savoir, est-ce que détruire l'objet contenant le pointeur doit enclencher la destruction de l'objet pointé ou pas ?
Citation:
Envoyé par Nicodemus
:arrow: Comment implémenter NIL de la même façon que l'algo de Cormen ? ie "Pour un arbre RN T, la sentinelle nil[T] est un objet ayant les mêmes champs qu'un noeud ordinaire. Tous les pointeurs vers NIL, donc les feuilles, sont remplacés par des pointeurs vers la sentinelle nil[T].
A la base, j'aurais opté pour une constante de type noeud. Par contre, j'ai l'impression qu'un noeud stocke un pointeur vers son père. Si tel est le cas, une constante unique est peu appropriée... Et si on défini qu'un noeud est NIL son pointeur P est NULL, est*ce que ça marche ? Si oui, ajouter une simple fonction isNil peut suffire. Sinon, il faudra m'en dire plus sur la nature de NIL, P, gauche, droite et suivant avant que je m'exprime...
Citation:
Envoyé par Nicodemus
:arrow: Question bête mais je préfere demander confirmation : l'arbre ne gère pas les noeuds... il ne gère que les pointeurs ?
Ca dépend de ce que TU décides. Il ne me semblerait pas idiot que l'arbre gère ses noeuds.
Citation:
Envoyé par Nicodemus
:arrow: Si je veux implémenter un constructeur par copie., je vais devoir recréer tous les noeuds ? ou bien juste copier les pointeurs ? (cf questions sur la gestion de mémoire merdique)
Si tu copies simplement les pointeurs, modifier un arbre va du coup modifier l'autre sans qu'il soit au courant... Donc une vraie copie me semble s'imposer. En général, pour des arbres, copier un noeud est défini de manière récursive : Le noeud demande aux sous noeuds qu'il possède (et à ceux là uniquement) de se copier.
Citation:
Envoyé par Nicodemus
Pour vous donner un peu plus une idée de ce que je fais : je dois implémenter différentes structures de données (liste, arbre RN et tas binomial) qui chacunes vont me servir de file de priorités (en l'occurrence de priorité minimum) pour implémenter divers algos sur les graphes. D'ailleurs je ne sais pas encore représenter mon graphe avec ces structures... mais chaque choses en son temps :D
Donc je vous remercie déjà d'avoir tout lu, lol. Et suis ouvert à toute suggestion, critique , manière de procéder, lien etc... car j'en aurais bien besoin :?
Est-ce que l'implémentation de ces éléments de base est une fin en soi (but = apprentissage) ou pas ? Parce que ce genre de chose existe tout fait.
Re: Implémentation d'un arbre rouge et noir
Bonsoir,
Dejà un grand merci d'avoir pris le temps de répondre ! Car j'en ai grand besoin mais aussi et surtout c'est sympathique de votre part :lol:
Je vais essayer de reprendre tout ce qui a été dit méthodiquement et dans l'ordre.
Citation:
Envoyé par JolyLoic
Citation:
Envoyé par Nicodemus
:arrow: Pour la racine de l'arbre, je suppose qu'un pointeur privé sur un noeud ferait l'affaire ?
Probablement, oui. Par contre, je vois pas mal de pointeurs, as-tu défini une politique de durée de vie pour les objets pointés ? A savoir, est-ce que détruire l'objet contenant le pointeur doit enclencher la destruction de l'objet pointé ou pas ?
En fait je ne sais pas du tout justement :-(. Ma classe Abre_RN doit comporter la méthode union, qui consiste à l'union de deux arbres évidemment mais aussi à renvoyer l'arbre-résultat et à supprimer les deux arbres passés en paramètre ou au moins les vider.... Donc je pense (et au vu de ce qui est dit plus bas) qu'il serait avantageux que l'arbre gère lui même ses noeuds. Ainsi détruire l'objet contenant le pointeur doit enclencher la destruction de l'objet pointé. Mais est-ce la meilleur solution, je n'en sais trop rien.
Citation:
Envoyé par JolyLoic
Citation:
Envoyé par Nicodemus
:arrow: Comment implémenter NIL de la même façon que l'algo de Cormen ? ie "Pour un arbre RN T, la sentinelle nil[T] est un objet ayant les mêmes champs qu'un noeud ordinaire. Tous les pointeurs vers NIL, donc les feuilles, sont remplacés par des pointeurs vers la sentinelle nil[T].
A la base, j'aurais opté pour une constante de type noeud. Par contre, j'ai l'impression qu'un noeud stocke un pointeur vers son père. Si tel est le cas, une constante unique est peu appropriée... Et si on défini qu'un noeud est NIL son pointeur P est NULL, est*ce que ça marche ? Si oui, ajouter une simple fonction isNil peut suffire. Sinon, il faudra m'en dire plus sur la nature de NIL, P, gauche, droite et suivant avant que je m'exprime...
Pour être un peu plus clair à ce sujet : je cite le livre de Cormen :
Citation:
Envoyé par Cormen
Pour simplifier le traitement des conditions aux limites dans la programmation des arbres rouge-noir, on utilise une même sentinelle pour représenter NIL. Pour un arbre RN T, la sentinelle nil[T] est un objet ayant les mêmes champs qu'un noeud ordinaire. Son champ couleur vaut NOIR, et ses autres champs (pere, gauche, droite et clé) peuvent prendre des valeurs quelconques. Tous les pointeurs vers NIL, donc les feuilles, sont remplacés par des pointeurs vers la sentinelle nil[T]. On utilise la sentinelle pour pouvoir traiter un enfant NIL d'un noeud x comme un noeud ordinaire dont le parent est x.
Donc par hypothèse : NIL pourrait être une donnée privée comme la racine, à savoir un noeud dont le pointeur p vaut NULL et les autres données du noeud prennent un valeur quelconque (NULL donc). Je pense que ça serait possible. Dans pour l'insertion par exemple j'aurai besoin de vérifier : " x = NIL[T]" je pourrais peut être tout simplement vérifier si x->p vaut NULL non ?
Citation:
Envoyé par JolyLoic
Citation:
Envoyé par Nicodemus
:arrow: Question bête mais je préfere demander confirmation : l'arbre ne gère pas les noeuds... il ne gère que les pointeurs ?
Ca dépend de ce que TU décides. Il ne me semblerait pas idiot que l'arbre gère ses noeuds.
Je vais essayer de faire comme ça, l'arbre gère ses noeuds... et quand par exemple je fais l'opération union sur deux arbres, je dois recréer les noeuds pour l'arbre résultant de l'uninon et supprimer ceux des deux arbres passés en paramètre (un passé en paramètre, l'autre sera l'objet implicite surement)
Citation:
Envoyé par JolyLoic
Citation:
Envoyé par Nicodemus
:arrow: Si je veux implémenter un constructeur par copie., je vais devoir recréer tous les noeuds ? ou bien juste copier les pointeurs ? (cf questions sur la gestion de mémoire merdique)
Si tu copies simplement les pointeurs, modifier un arbre va du coup modifier l'autre sans qu'il soit au courant... Donc une vraie copie me semble s'imposer. En général, pour des arbres, copier un noeud est défini de manière récursive : Le noeud demande aux sous noeuds qu'il possède (et à ceux là uniquement) de se copier.
Nous somme donc d'accord, les noeuds sont copiés pour la création d'un nouvel arbre et ainqi chaque arbre posède ses propres noeuds.
Citation:
Envoyé par JolyLoic
Citation:
Envoyé par Nicodemus
Pour vous donner un peu plus une idée de ce que je fais : je dois implémenter différentes structures de données (liste, arbre RN et tas binomial) qui chacunes vont me servir de file de priorités (en l'occurrence de priorité minimum) pour implémenter divers algos sur les graphes. D'ailleurs je ne sais pas encore représenter mon graphe avec ces structures... mais chaque choses en son temps :D
Donc je vous remercie déjà d'avoir tout lu, lol. Et suis ouvert à toute suggestion, critique , manière de procéder, lien etc... car j'en aurais bien besoin :?
Est-ce que l'implémentation de ces éléments de base est une fin en soi (but = apprentissage) ou pas ? Parce que ce genre de chose existe tout fait.
En fait pour être plus précis, le projet est un projet d'algorithmique de Licence info. Je cite brièvement : "L'objectif de ce projet est d'implanter un algorithme pour le problème de l'arbre couvrant minimal, en l'occurrance PRIM. Une bonne implantation de cet algorithme a besoin de structures de données bien adaptées. Au début du projet on implémentera les structures de données suivantes : un arbre rouge et noir, un tas binomial, une liste chainée. Dans la deuxieme partie on implantera l'algo de prim pour chacune de ces trois structures de données. Et dans la troisieme partie on comparera les trois implantations en mesurant le temps d'execution réel (temps CPU)."
Donc j'ai du boulot 8O .
Citation:
Envoyé par SKZ81
Il est plus propre, orienté-objet parlant, que tout ce que l'arbre crée, il le détruise.
Il gèrerais donc les noeuds, l'utilisateur les accèdants via l'interface de l'arbre en utilisant les clés.
Ainsi, si l'utilisateur supprime brutalement un noeud, l'arbre supprime tous les sous-noeuds.
Merci de ton aide aussi SKZ81 :D .
Je vais procéder de cette manière, l'arbre gère ses propres noeuds. Dond ce qu'il crée, il le detruit. Par contre "l'utilisateur les accédants via l'interface de l'arbre en utilisant les clés"... Hum, par exemple si j'ai deux noeud dans l'arbre qui ont une clé identique comment faire pour les différencier ? Je n'ai peut être pas totalement saisi la notion de clé... pour moi c'est l'info qu'on stocke... je me trompe ?
Citation:
Envoyé par SKZ81
En dernier lieu, noeud devrais pour être "user-safe" renvoyer les clés des noeuds en relation avec lui.
Désolé mais je n'ai pas tres bien compris :-(
Citation:
Envoyé par SKZ81
Il manque énormément d'init dans le deuxième constructeur de noeud (père, droite, gauche, couleur, clé...)
Ce n'etait qu'un premiere jetée de code, en fait il manque plein de choses lol.
Citation:
Envoyé par SKZ81
Pour NIL, vu la structure de donnée, la solution de Loïc me parraît la bonne, je l'aurais codé ainsi :
Code:
1
2
3
4
5
| class noeud {
...
static bool isNil(int cle) {return (cle<0);}
....
}: |
Puisque getPere(), etc... renvoient les clefs.
la procédure isNil pourrait faire l'affaire oui. Par contre getPere.... ne renvoit pas la Cle.. je n'ai pas tres bien saisi.. d'ailleurs c'est encore un peu flou la notion exacte de clé.
Je pense que je vais coder un peu plus tout ça ce soir ou demain, pour mieux cerner le probleme, mes prochaines question seront plus précises et plus faciles pour vous je l'espere.
En tou cas, encore merci pour votre aide précieuse.
very thank
Re: Implémentation d'un arbre rouge et noir
Citation:
Envoyé par Nicodemus
Hum, par exemple si j'ai deux noeud dans l'arbre qui ont une clé identique comment faire pour les différencier ? Je n'ai peut être pas totalement saisi la notion de clé... pour moi c'est l'info qu'on stocke... je me trompe ?
Encore une fois à toi de fixer la poltique. Ca veut dire quoi de fusionner deux arbres (binaires)? A priori la Clé est un identifiant unique... Je me demande même si ça ne devrait pas être une variable de l'arbre, incrémenté à chaque fois que l'arbre crée un noeud.
En fait dans ce cas, la fonction insérer() devrait peut être prende en paramètre le père et la direction (droite ou gauche) et renvoyer la clé du noeud-fils crée. Quand je dis "passer le père", sa veut dire "passer la clé du père", parceque...
Citation:
Envoyé par Nicodemus
Citation:
Envoyé par SKZ81
En dernier lieu, noeud devrais pour être "user-safe" renvoyer les clés des noeuds en relation avec lui.
Désolé mais je n'ai pas tres bien compris :-(
...comme la clé est unique, elle permet de retrouver un noeud donné (ou aucun en cas d'erreur dans l'arbre). Ce mécanisme te permet de géré une interface (classe Arbre_EN) qui passe uniquement par les clefs. Ainsi l'utilisateur de ta classe (toi-même en l'occurence) n'ira pas foutre le dawa dans la structure de l'arbre. Il est important qu'elle ne soit pas corompue au moment de la destruction de l'arbre (fuites mémoire ou crash).
Citation:
Envoyé par Nicodemus
Citation:
Envoyé par SKZ81
Pour NIL, vu la structure de donnée, la solution de Loïc me parraît la bonne, je l'aurais codé ainsi :
Code:
1
2
3
4
5
| class noeud {
...
static bool isNil(int cle) {return (cle<0);}
....
}: |
Puisque getPere(), etc... renvoient les clefs.la procédure isNil pourrait faire l'affaire oui. Par contre getPere.... ne renvoit pas la Cle.. je n'ai pas tres bien saisi.. d'ailleurs c'est encore un peu flou la notion exacte de clé.
C'est pourtant justement ce que je te propose de faire... Que les fonction get{Pere|Gauche|Doite|Suivant} renvoie un entier et non un pointeur... Pour que l'utilisateur de l'arbre gère la structure de noeud de façon transparante (user-safe).
Citation:
Envoyé par Nicodemus
Je pense que je vais coder un peu plus tout ça ce soir ou demain, pour mieux cerner le probleme, mes prochaines question seront plus précises et plus faciles pour vous je l'espere.
En tou cas, encore merci pour votre aide précieuse.
very thank
Oki, à plus alors... :D
Re: Implémentation d'un arbre rouge et noir
Citation:
Envoyé par Nicodemus
Bonsoir,
Dejà un grand merci d'avoir pris le temps de répondre ! Car j'en ai grand besoin mais aussi et surtout c'est sympathique de votre part :lol:
Je vais essayer de reprendre tout ce qui a été dit méthodiquement et dans l'ordre.
Bon, je viens de me renseigner sur les reb-black tree, du coup, certains points s'éclaircissent.
Citation:
Envoyé par Nicodemus
Ma classe Abre_RN doit comporter la méthode union, qui consiste à l'union de deux arbres évidemment mais aussi à renvoyer l'arbre-résultat et à supprimer les deux arbres passés en paramètre ou au moins les vider....
Je ne vois pas trop pourquoi une fonction union devrait détruire quoi que ce soit dans ses paramètres. L'utilisateur peut légitimement encore vouloir y accèder par la suite.
Citation:
Envoyé par Nicodemus
Donc je pense (et au vu de ce qui est dit plus bas) qu'il serait avantageux que l'arbre gère lui même ses noeuds. Ainsi détruire l'objet contenant le pointeur doit enclencher la destruction de l'objet pointé. Mais est-ce la meilleur solution, je n'en sais trop rien.
Je suis d'accord sur ce point, surtout que dans l'idéal, l'utilisateur ne sait même pas qu'il existe des Noeuds dans cette classe, et donc qu'on ne peut pas lui demander de les détruire...
Citation:
Envoyé par Nicodemus
Donc par hypothèse : NIL pourrait être une donnée privée comme la racine, à savoir un noeud dont le pointeur p vaut NULL et les autres données du noeud prennent un valeur quelconque (NULL donc). Je pense que ça serait possible. Dans pour l'insertion par exemple j'aurai besoin de vérifier : " x = NIL[T]" je pourrais peut être tout simplement vérifier si x->p vaut NULL non ?
Avec le complément d'information, je pense que le mieux est de faire de ce noeud une constante de classe (c'est à dire statique), ce qui permet d'avoir un seul objet NIL pour tous tes arbres.
Citation:
Envoyé par Nicodemus
Je vais essayer de faire comme ça, l'arbre gère ses noeuds... et quand par exemple je fais l'opération union sur deux arbres, je dois recréer les noeuds pour l'arbre résultant de l'uninon et supprimer ceux des deux arbres passés en paramètre (un passé en paramètre, l'autre sera l'objet implicite surement)
J'ai l'impression que tu te diriges vers une fonction :
void ArbreRN::merge(ArbreRN autreArbre);
Une fonction de type :
ArbreRN merge(ArbreRN arbre1, ArbreRN arbre2);
Me semble tout aussi utile. Sinon, c'est un peu comme si on définissait l'opérateur +=, sans définir l'opérateur +.
Remarque : J'ai passé mes arguments par copie, et non par référence à une constante, car je crois que dans ce genre d'algo, tu vas devoir modifier les arbres au fur et à mesure de la fusion, mais ce n'est pas une raison pour détruire les arbres initiaux. Donc dans ce cas, je crée à l'appel des copies des arbres, je travaille sur ces copies, et à la fin de la fonction, les copies sont détruites automatiquement. La fonction merge (union est un mot réservé...) en elle même n'a pas à gérer de destruction.
Citation:
Envoyé par Nicodemus
En fait pour être plus précis, le projet est un projet d'algorithmique de Licence info. Je cite brièvement : "L'objectif de ce projet est d'implanter un algorithme pour le problème de l'arbre couvrant minimal, en l'occurrance PRIM. Une bonne implantation de cet algorithme a besoin de structures de données bien adaptées. Au début du projet on implémentera les structures de données suivantes : un arbre rouge et noir, un tas binomial, une liste chainée. Dans la deuxieme partie on implantera l'algo de prim pour chacune de ces trois structures de données. Et dans la troisieme partie on comparera les trois implantations en mesurant le temps d'execution réel (temps CPU)."
Si l'algorithme est globalement le même avec les trois structures, j'essaierais de partir de la définition de l'interface pour ces structures, et j'essaierais de la rendre identique. Ainsi, je n'aurais besoin d'implémenter l'algoritme qu'une seule fois pour les trois structures. C'est le principe suivi par la STL, qui défini pour chaque conteneur la notion d'itérateur, puis permet à partir d'itérateur des algorithmes qui marchent pour tous les itérateurs d'un certain type (max_element fonctionne de la même manière qu'on lui passe des itérateurs vers une liste, un vector, un deque...).
Ca risque de demander un peu plus de travail de conceptualisation, mais le résultat peut être intéressant. Voir par exemple boost::graph qui a pris une telle approche.
Citation:
Envoyé par Nicodemus
Je n'ai peut être pas totalement saisi la notion de clé... pour moi c'est l'info qu'on stocke... je me trompe ?
Quand on s'amuse avec des graphes, c'est effectivement la donnée. Dans un cas réel, il y aurait probablement de la données associée à cette clef. C'est ce que fait std::map, qui utilise en interne un red black tree. C'est possible de gérer de tels arbres avec des clefs dupliquées, mais ça n'apporte pas forcément grand'chose.
Remarque qui m'est venue en cours de rédaction :
Ta classe noeud possède 4 pointeurs. Mais ils ne sont pas identiques.
Il semble logique de dire que Droite et Gauche sont des pointeurs possèdant. Par contre, P n'est pas possèdant : Quand on détruit un noeud, on ne doit pas suivre P pour détruire le père. Le cas de suivant m'est inconnu, car je ne sais pas quel est sa définition.
Autre remarque : pour débuger tes algos, il peut être utile d'afficher tes arbres de manière graphique. Ca peut s'implémenter en 5 minutes en générant une sauvegarde dans un fichier de la structure de ton arbre au format de DOT (plus d'infos sur http://www.graphviz.org/).
