Discussion :

[Salamandre92]

Bonsoir !

Ça fait un certain temps que je n'ai pas fait de C++, mais je ne crois pas être tombée sur un problème comme ça auparavant. Je vous explique.

Je cherche à construire un arbre binaire de recherche, et mon code se compile sans erreur. J'ai donc une classe Node et une classe Tree :

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
 
 
class Tree
{
    // Attributes
 
    int m_nbNodes;
 
    public :
    std::vector<Node> m_nodes;
 
    // Methods
 
    Tree();
    int getNbNodes();
    Node* getRoot();
    bool addNode(std::string key,int order);
 
 
 
};

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
33
34
35
36
37
38
39
40
41
42
 
class Node
{
    // Attributes
 
    std::string m_key;
    int m_order;
    Node* m_left;
    Node* m_right;
 
 
    //Methods
    public:
 
    Node();
 
    Node(std::string key, int order);
 
    std::string getKey();
 
    int getOrder();
 
    Node* getLeft();
 
    Node* getRight();
 
    void changeKey(std::string newKey);
 
    void changeOrder(int newOrder);
 
    void changeRight(Node* newRight);
 
    void changeLeft(Node* newLeft);
 
    void show();
 
    void addLeft(Node* son);
 
    void addRight(Node* son);
 
 
};

Je veux ajouter des nouveaux noeuds : "head","foot","often" et "coffee", dans cette ordre. Voila le code d'ajout d'un nouveau noeud :

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
33
34
35
36
37
38
39
40
41
42
43
 
bool Tree::addNode(std::string key,int order)
{
    Node* newNode= new Node(key,order);
    Node* tmpNode;
    Node* tmpFather;
    string keyComp;
    if(m_nbNodes != 0)
    {
        tmpNode = &m_nodes[0];
        do
        {
            tmpFather = tmpNode;
            keyComp =tmpNode->getKey();
            if(key>keyComp)
            {
                tmpNode = tmpNode->getRight();
                if(!tmpNode)
                {
                    tmpFather->changeRight(newNode);
                    break;
                }
            }
            else if(key<keyComp)
            {
                tmpNode = tmpNode->getLeft();
                if(!tmpNode)
                {
                    tmpFather->changeLeft(newNode);
                    break;
                }
            }
            else
            {
                cout<<"This word is already in the tree."<<endl;
                return false;
            }
        }while(tmpNode);
    }
    m_nodes.push_back(*newNode);
    m_nbNodes++;
    return true;
}

Jusqu'à often, tout se passe bien : "head" est la racine, "foot" est son fils gauche, "often" est son fils droit, et ces derniers n'ont pas de fils. Quand je veux ajouter "coffee", à l'intérieur de la fonction tout se passe bien (en particulier, la ligne 29 tmpFather->changeLeft(newNode); est bien effectuée, les changements d'adresses sont corrects). Problème : une fois sorti de la fonction, le programme oublie qu'il a changé la valeur du fils gauche de "foot".

Du coup je me suis dit que c'est tmpFather qui n'est pas bien relié au noeud qui a un fils gauche vide, mais dans ce cas là je ne comprends pas pourquoi ça n'a pas raté lors de l'assignation de "foot" en tant que fils gauche de "head".

Quelqu'un a une idée de ce qui se passe ? J'ai passé l'aprem dessus sans comprendre d'où ça venait.

Merci d'avance

[koala01]

Salut,

Tu parles d'une fonction changeLeft qui fonctionne, ... Mais pas trop, visiblement, et tu ne nous donne pas cette fonction...

Nous aurions bien plus facile à t'aider si nous disposions du code de cette fonction (et des autres fonctions de la classe Node, tant qu'à faire)

[Salamandre92]

Salut,

Tu parles d'une fonction changeLeft qui fonctionne, ... Mais pas trop, visiblement, et tu ne nous donne pas cette fonction...

Nous aurions bien plus facile à t'aider si nous disposions du code de cette fonction (et des autres fonctions de la classe Node, tant qu'à faire)

Bien sûr les voici :

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <string>
#include <iostream>
#include "Node.h"
 
using namespace std;
 
/************************************************/
// Constructors
 
Node::Node()
{
    m_key = "";
    m_order = -1;
    m_left = NULL;
    m_right = NULL;
 
}
 
Node::Node(string key, int order)
{
    m_key = key;
    m_order = order;
    m_left = NULL;
    m_right = NULL;
 
}
 
/************************************************/
// Access
 
string Node::getKey()
{
    return m_key;
}
 
int Node::getOrder()
{
    return m_order;
}
 
Node* Node::getLeft()
{
    return m_left;
}
 
Node* Node::getRight()
{
    return m_right;
}
 
/************************************************/
// Change attributes
 
void Node::changeKey(string newKey)
{
    m_key = newKey;
}
 
void Node::changeOrder(int newOrder)
{
    m_order = newOrder;
}
 
void Node::changeRight(Node* newRight)
{
    m_right = newRight;
}
 
void Node::changeLeft(Node* newLeft)
{
    m_left = newLeft;
}
 
 
/************************************************/
// Other methods
 
void Node::show()
{
    cout<<"Key : "<<m_key<<endl;
    if(m_left) cout<<"Left : "<<m_left->getKey()<<endl;
    else cout<<"No left son"<<endl;
    if(m_right) cout<<"Right : "<<m_right->getKey()<<endl;
    else cout<<"No right son"<<endl;
}
 
/************************************************/
 
 
void Node::addLeft(Node* son)
{
    m_left = son;
}
 
void Node::addRight(Node* son)
{
    m_right = son;
}

Quand je dis que la fonction changeLeft fonctionne, je veux dire qu'elle fonctionne correctement quand j'ajoute "foot" à l'arbre, et quand je fais le débuggage en m'arrêtant sur l'ajout de "coffee", et que je regarde la valeur de m_left du tmpFather après la ligne 29, c'est bien celle de newNode.

[Matt_Houston]

Po, po, po.. grosse confusion dans la conception ici.

et mon code se compile sans erreur.

C'est loin d'être une garantie ça, particulièrement en C++.


Qui est propriétaire des Nodes ? I.e. : chargé de leur création, référencement et destruction ?

En lisant la définition de Tree, on a l'impression que c'est lui qui gère, puis en lisant celle de Node, on comprend que tu n'as pas réussi à choisir entre deux implémentations distinctes de la même structure de données.

De plus, le code suivant :

Code :

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

1
2
3
4
5
    Node* newNode= new Node(key,order);
 
    // ...
 
    m_nodes.push_back(*newNode);

...montre que tu ne contrôles pas ce que tu fais. Tu réalises ici une copie des données de l'instance de Node que tu as initialisée, tu places cette copie dans le vecteur, puis la fonction termine. L'instance originale référencée par newNode existe toujours, mais est définitivement perdue.

D'une manière générale, lorsque tu as un new sans delete correspondant (et que tu n'utilises pas de pointeurs intelligents), c'est qu'il y a un souci.


Revenons à :

Je cherche à construire un arbre binaire de recherche

Ok. De ce que je comprends de ton exposé, tu mélanges ces deux façons de faire (clic !). Soit on stocke tous les noeuds dans un tableau unique (soit de pointeurs si les noeuds sont gros, soit de noeuds directement) et le référencement est implicite (calcul d'index), soit on réalise un chaînage dynamique où chaque noeud est alloué séparément et responsable du référencement de ses enfants : c'est l'implémentation récursive.

Si tu optes pour la première méthode, la bonne manière de faire serait d'utiliser un std::vector<std::unique_ptr<Node> > mais je doute que tu aies assez d'expérience pour appréhender les move semantics (la plupart du temps, on enseigne le C++ aux étudiants sans les bases IMHO). Je te conseille donc un std::vector<Node>, ou à la limite un std::vector<Node *> si l'allocation dynamique est une contrainte de l'énoncé. Identifies aussi les noeuds grâce à leur index au sein du tableau (un entier) plutôt que grâce à des pointeurs.

Si tu optes pour la seconde méthode, oublie le vector voire même la classe Tree. Tu n'as besoin que de Nodes qui référencent des Nodes.

[Salamandre92]

Po, po, po.. grosse confusion dans la conception ici.



C'est loin d'être une garantie ça, particulièrement en C++.


Qui est propriétaire des Nodes ? I.e. : chargé de leur création, référencement et destruction ?

En lisant la définition de Tree, on a l'impression que c'est lui qui gère, puis en lisant celle de Node, on comprend que tu n'as pas réussi à choisir entre deux implémentations distinctes de la même structure de données.

J'avoue que je ne comprends pas ta question et ta remarque. Pourquoi représenteraient-ils une même structure de données ? Un arbre est un ensemble de noeuds ordonnés, non ?

De plus, le code suivant :

...montre que tu ne contrôles pas ce que tu fais. Tu réalises ici une copie des données de l'instance de Node que tu as initialisée, tu places cette copie dans le vecteur, puis la fonction termine. L'instance originale référencée par newNode existe toujours, mais est définitivement perdue.

D'une manière générale, lorsque tu as un new sans delete correspondant (et que tu n'utilises pas de pointeurs intelligents), c'est qu'il y a un souci.

L'introduction du new dans mon code est due au fait que grâce à ça j'ai pu résoudre un autre problème. Je n'ai pas mis de delete de manière délibérée, parce que j'ai besoin que cette nouvelle instance référencée par newNode existe toujours à la fin de la fonction. Son adresse est conservée dans le tableau m_nodes et en tant que fils gauche ou droit d'un autre noeud. Mais tu as raison, je devrais mettre un delete dans le cas où la clé est déjà utilisée dans l'arbre.

Revenons à :


Ok. De ce que je comprends de ton exposé, tu mélanges ces deux façons de faire (clic !). Soit on stocke tous les noeuds dans un tableau unique (soit de pointeurs si les noeuds sont gros, soit de noeuds directement) et le référencement est implicite (calcul d'index), soit on réalise un chaînage dynamique où chaque noeud est alloué séparément et responsable du référencement de ses enfants : c'est l'implémentation récursive.

Si tu optes pour la première méthode, la bonne manière de faire serait d'utiliser un std::vector<std::unique_ptr<Node> > mais je doute que tu aies assez d'expérience pour appréhender les move semantics (la plupart du temps, on enseigne le C++ aux étudiants sans les bases IMHO). Je te conseille donc un std::vector<Node>, ou à la limite un std::vector<Node *> si l'allocation dynamique est une contrainte de l'énoncé. Identifies aussi les noeuds grâce à leur index au sein du tableau (un entier) plutôt que grâce à des pointeurs.

Si tu optes pour la seconde méthode, oublie le vector voire même la classe Tree. Tu n'as besoin que de Nodes qui référencent des Nodes.

Ce n'est pas un énoncé, c'est un stage où je suis libre de faire ce que je veux, du moment que ça marche (et je ne suis pas une informaticienne ^^). Je dois, entre-autres, implémenter un dictionnaire de mots, et l'arbre binaire me sert à tester rapidement si un mot appartient au dictionnaire, et si oui, me donner sa position dans le dictionnaire (c'est l'attribut "m_order" du noeud) pour ensuite faire d'autres opérations.

Je pense que si d'ici la fin du week-end je n'ai pas trouvé de solution, je recommencerai l'implémentation avec une méthode récursive, je pense. Je m'étais inspirée du tuto de C sur ce site, qui ne proposait pas une implémentation récursive. Merci !

[dalfab]

Bonjour,

S'il n'y a pas de contrainte d'énoncé et que l'objectif est de mettre en place un dictionnaire, il y a beaucoup plus simple en C++. Il faut utiliser un voir std::map qui gère les collections de type dictionnaire.
Ici aussi, tu as la possibilité de mettre dedans des objets s'ils sont petits, ou des unique_ptr<> ou des des shared_ptr<>, les pointeurs simples sont à éviter. La notation semble lourde mais le résultat est puissant et optimum.
Exemple avec unique_ptr:

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
struct MaClasse {
   int a;
   double b;
   MaClasse( int a , double b ) : a(a) , b(b) {}
};
 
// définition d'un objet monDictionnaire associant une chaîne de caractère à chaque MaClasse par arbre trié
std::map< std::string,std::unique_ptr< MaClasse > >  monDictionnaire;
 
// ajout ou remplacement dans dictionnaire
monDictionnaire["uneClef"] = std::make_unique<MaClasse>( 1 , 2.3 );
 
// recherche optimisée dans dictionnaire (et modifier l'élément)
std::unique_ptr< MaClasse > pClasseLue = monDictionnaire["uneClef"];
pClasseLue->a = 4;
 
// vérifier si un mot est dans le dictionnaire (et le modifier)
auto itr = monDictionnaire.find("uneClef");
if ( itr != monDictionnaire.end() ) { // a été trouvé
   auto pClasseLue = itr->second;
   pClasseLue->a = 4;
}
 
// supprimer
monDictionnaire.erase( std::string("uneClef") );
 
// parcourir tout le dictionnaire
for ( auto itm : monDictionnaire )
   std::cout << "clef:" << itm.first << " a:" << itm.second->a << " b:" << itm.second.b << "\n";

[JolyLoic]

Ce n'est pas un énoncé, c'est un stage où je suis libre de faire ce que je veux, du moment que ça marche (et je ne suis pas une informaticienne ^^). Je dois, entre-autres, implémenter un dictionnaire de mots, et l'arbre binaire me sert à tester rapidement si un mot appartient au dictionnaire, et si oui, me donner sa position dans le dictionnaire (c'est l'attribut "m_order" du noeud) pour ensuite faire d'autres opérations.

Dans ce cas, ne réinvente pas la roue : Utilise std::map, c'est exactement un arbre de recherche équilibré, mais encapsulé dans une interface qui masque ça et te présente le tout comme un dictionnaire clef/valeur.
Si tu n'as pas besoin d'ordre entre tes éléments, juste de recherche rapide, tu peux aussi regarder std::unordered_map, sachant que les deux ont une interface très proche, et qu'il est facile de basculer de l'un à l'autre.

[Matt_Houston]

J'avoue que je ne comprends pas ta question et ta remarque.

Ma remarque porte sur la gestion mémoire. En programmation générale, il existe une notion d'ownership (propriété) sur les ressources octroyées au programme par le système d'exploitation. Leur libération devant la plupart du temps être explicite, il convient d'identifier à tout moment l'objet responsable du cycle de vie de chacune de ces ressources. Ici dans ton programme, on a du mal à appréhender le partage des responsabilités entre Tree et Node.

Pourquoi représenteraient-ils une même structure de données ? Un arbre est un ensemble de noeuds ordonnés, non ?

Un arbre est une structure récursive : un noeud est toujours la racine d'un arbre à part entière, et un arbre est un agrégat d'arbres.

L'introduction du new dans mon code est due au fait que grâce à ça j'ai pu résoudre un autre problème. Je n'ai pas mis de delete de manière délibérée, parce que j'ai besoin que cette nouvelle instance référencée par newNode existe toujours à la fin de la fonction. Son adresse est conservée dans le tableau m_nodes et en tant que fils gauche ou droit d'un autre noeud. Mais tu as raison, je devrais mettre un delete dans le cas où la clé est déjà utilisée dans l'arbre.

Tu as raison, mon affirmation précédente en gras est abusive puisque la référence est effectivement conservée par le noeud parent (je lis en diagonale, souvent ça suffit et parfois non ) même si le bloc mémoire n'est pas toujours libéré. C'est toutefois alambiqué comme implémentation (cf. point précédent) !


La solution immédiate à ton problème global est effectivement celle communiquée par les autres intervenants.

[koala01]

J'avoue que je ne comprends pas ta question et ta remarque. Pourquoi représenteraient-ils une même structure de données ? Un arbre est un ensemble de noeuds ordonnés, non ?

En fait, la notion d'arbre n'est qu'une "abstraction" qui permet de cacher la complexité propres aux noeuds, et chaque noeud pourrait être considéré comme "un arbre à part entière". Allez, observe un peu les noeuds suivants

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
         8
        /  \
       /    \
      /      \
     4         12
    /\        / \
   /  \      /   \
  2    6   10    14
 /\   /\   /\    /\
1  3 5  7 9 11 13  15

Le noeud qui contient la valeur 8 représente le noeud racine de l'ensemble des (15) valeurs représentées. Nous pouvons donc créer un arbre binaire (équilibré) qui contient les 15 valeurs en utilisant ce noeud comme "point de départ".

Mais, si je ne suis intéressé que par les valeurs qui vont de 4 à 7 (ou par les valeurs qui vont de 9 à 15), et que j'ignore (volontairement) les noeuds dont les valeurs ne correspondent pas à ce dont j'ai besoin, je me rend compte que le noeud représentant la valeur 4 (respectivement le noeud représentant la valeur 12) regroupe toutes les valeurs qui m'intéressent! Et je peux donc considérer ce noeud (4 ou 12) comme... la racine de l'arbre regroupant les valeurs qui m'intéressent.

Il en irait tout à fait de même si je n'était intéressé que par les valeurs allant de 1 à 3, de 5 à 7, de 9 à 11 ou de 13 à 15! Et mieux encore : si je n'étais intéressé que par la valeur 1, 3, 5, 7, 9, 11, 13 ou 15, je pourrais tout aussi bien considérer chacun de ces noeud comme... la racine d'un arbre qui ne contient qu'un seul noeud.

D'une certaine manière, nous pouvons donc dire que la notion de noeud est la représentation "physique" de la valeur qu'il contient et des relations qui le lient aux autres valeurs, alors que la notion d'arbre représente la manière dont on va pouvoir manipuler ces valeurs et l'ensembles des services que l'on est en droit d'attendre de leur part

[Salamandre92]

En suivant vos conseils, je me suis épargné beaucoup de travail et de sommeil grâce à map, que je ne connaissais pas du tout ! Je vous dois une fière chandelle

Juste une question toutefois : vu que c'est clairement un ABR qu'il y a dans map, est-ce que l'ordre d'insertion des mots du dictionnaire influence l'efficacité de la recherche de mot ensuite ? Je sais que pour un ABR classique que l'on construit soi-même, il vaut mieux éviter l'ordre alphabétique puisqu'alors l'arbre se résume à une chaîne. Est-ce que l'objet map se réorganise à chaque insertion pour optimiser l'organisation de ses paires ?

[JolyLoic]

Oui, l'arbre se rééquilibre au cours de l'insertion. Si tu es intéressée en terme d'algorithme, ce qui est utilisé est un red-black tree.

[Salamandre92]

Merci beaucoup ! je mets le sujet en résolu