Discussion :

[Nicodemus]

[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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 , mais ça va venir .
J'ai donc quelques questions, si vous pouviez y répondre ce serait bien sympathique, merci

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.

Pour la racine de l'arbre, je suppose qu'un pointeur privé sur un noeud ferait l'affaire ?

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].

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 ?

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"....

Pour le constructeur, tout ce que j'ai à faire, c'est de créer un noeud racine ?

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)

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

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

[JolyLoic]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

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é.

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 ?

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...

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.

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.

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

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.

[SKZ81]

Je suis globalement d'accord avec tout ce qu'a dis Loïc, je complète juste un peu...
Pour ce qui est de la gestion mémoire...
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.
Pour accèder aux noeuds, il faudra renvoyer une reférence, et implémenter le constructeur par recopie de noeud. En dernier lieu, noeud devrais pour être "user-safe" renvoyer les clés des noeuds en relation avec lui.

Pour la racine, dans le cas où il aurait la propriété de toujours possèder une racine, une variable membre de type Noeud. Sinon un pointeur.

Il manque énormément d'init dans le deuxième constructeur de noeud (père, droite, gauche, couleur, clé...)

Pour insérer, cf plus haut, il me semble mieux qu'il n'y ai QUE la version prenant la cle.

Pour NIL, vu la structure de donnée, la solution de Loïc me parraît la bonne, je l'aurais codé ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
class noeud {
...
  static bool isNil(int cle) {return (cle<0);}
....
}:

Puisque getPere(), etc... renvoient les clefs.

[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
Je vais essayer de reprendre tout ce qui a été dit méthodiquement et dans l'ordre.

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.

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 :

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 ?

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)

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.

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

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 .

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 .
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 ?

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 :-(

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.

Pour NIL, vu la structure de donnée, la solution de Loïc me parraît la bonne, je l'aurais codé ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[SKZ81]

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...

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).

Pour NIL, vu la structure de donnée, la solution de Loïc me parraît la bonne, je l'aurais codé ainsi :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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).

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...

[JolyLoic]

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
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.

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.

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...

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.

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.

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.

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/).