Discussion :

[margagn]

Bonjour à tous,

Pour des fins totallement académique, je suis en train de me créer un arbre binaire de recherche en .NET 2.0. Jusqu'ici, aucun problème.

Je me suis créé une classe BinaryTreeNode qui consiste en un noeud.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
    class BinaryTreeNode<T> where T : IComparable
    {
        internal BinaryTreeNode<T> left;
        internal BinaryTreeNode<T> right;
        private T value;
 
        public BinaryTreeNode(T value)
        {
            this.value = value;
        }
    }

Puis dans une classe BinaryTree, c'est là que je retrouve mon Root (racine) et je ne suis pas tout à fait certain de comprendre comment .NET fonctionne. Voici la méthode qui me cause problème. Tout d'abord, pour que cette méthode fonctionne, j'ai du ajouter le mot clef REF afin de passer par référence mon noeud, même si je croyais qu'un objet était toujours passé par référence en .NET. Est-ce que j'ai manqué quelque chose?

Code :

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

1
2
3
4
5
6
7
8
        public void Add(ref BinaryTreeNode<T> node, T value)
        {
            if (node == null)
                node = new BinaryTreeNode<T>(value);
            else
                if (node.Value.CompareTo(value) > 0) Add(ref node.left, value);
                else if (node.Value.CompareTo(value) < 0) Add(ref node.right, value);
        }

Secundo, comment cette méthode peut fonctionner? J'appel la méthode Add récursivement et lui passe une référence vers Left ou Right qui sont NULL. Comment c'est possible? Dans ce contexte, .NET créé le noeud et ce nouveau noeud fera référence à son précédent. Comment ca fonctionne? .NET renvoie donc un pointeur vers la zone mémoire qui contient un pointeur vers un noeud Left ou Right? Est-ce que c'est cela ?

Merci de votre aide!

Martin

[cinemania]

Salut Martin,

Tout d'abord, toute classe instanciée est manipulée par sa référence.
Ainsi

BinaryTreeNode<T> btn; signifie que btn contiendra non pas un objet BinaryTreeNode mais bien une référence vers un tel objet.

Cela aurait été différent si tu avait déclaré BinaryTreeNode comme étant un struct, car là, les objets sont manipulés par valeur et non référence, donc directement.

Lorsque tu écrit ta méthode Add avec un ref tu fait en sorte que le code généré ne manipule pas la référence de l'objet, mais la référence de la référence de l'objet. En c++ natif t'aurais écrit ca : BinaryTreeNode**...

Ensuite il y a un problème d'ordre conceptuel. En effet, lorsque l'on créé une classe de ce type, soit l'encapsulation d'une structure de données.
Le client se fou complètement de connaitre l'implantation interne. Ce qui signifie que ce n'est pas à lui de manipuler les BinaryTreeNode, pourtant avec ta méthode Add, c'est ce que cela revient à faire.
Imagine si tu avais due manipuler toi meme les structures internes de la classe Dictionary pour l'adjonction, suppression ou meme recherche, quel en aurait été l'intérêt ?

Cela mis de côté... Ta classe BinaryTree aurait plutot due ressembler à ceci

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
 
class BinaryTree<T>  where T : IComparable
{
  private BinaryTreeNode<T> _root;
  ...
 
  public void Add(T value)
  {
    BinaryTreeNode<T> node = new BinaryTreeNode<T>(value);
    if (_root == null) _root = node;
    else 
    {
      BinaryTreeNode<T> pnode = _find(_root, value);
      if (value.CompareTo(pnode.Value) > 0)
        pnode.right = node;
      else
        pnode.left = node;
    }
  }
 
  ...
 
  private BinaryTreeNode<T> _find(BinaryTreeNode<T> current, value)
  {
    BinaryTreeNode<T> subnode = (value.CompareTo(current.Value) > 0) ? current.right : current.left; 
    return (subnode != null) ? _find(subnode, value) : current;
  }
 
  ...
}

Petite explication :
Dans cette implantation, tu as un membre qui remprésente le noeud racine de ton arbre, par défaut si l'arbre est vide il vaut null. Si tu ajoute une valeur à ce moment là, tu créer le noeud racine.

Dans le cas où l'arbre n'est pas vide, tu cherche le noeud parent dans l'arbre (méthode _find), puis tu lui ajoute le noeud que tu viens de créer pour stocker la valeur à ajouter à l'arbre.

Attention : Cette méthode ne vérifie pas que la valeur est déjà présente, donc si tu as des doublons, les doublons ne serons jamais retournés par la méthode de recherche, sauf si tu fait une méthode spécifique.

Cela fonctionne uniquement parce qu'en C# tout est référence (sauf type natif ou struct)
quand tu fait objet.membre tu accède au membre nommé de l'objet.
Tu n'a pas a te poser de question pour savoir si objet est l'objet lui même ou une référence vers celui-ci ! (éternelle question en C++ natif...)

Autre point qui fait que ta méthode est dangereuse : Tu donne accès induit aux références internes vers les noeuds, ce qui n'est pas ce qui se fait de mieux sauf si tu tiens abolument à poser d'énormes problèmes lors des liaisons de tes noeuds entre eux. S'il ce produit le moindre bug dans ta méthode pour une raison X ou Y cela peut avoir des conséquences grave sur la cohérence de ton arbre.

[margagn]

Merci cinemania de ta super explication!