Les arbres sont-ils organisés selon une structure «premier enfant, nextsibling»? Sinon, pourquoi pas?

Habituellement, les structures de données arborescentes sont organisées de manière à ce que chaque nœud contienne des pointeurs vers tous ses enfants.

       +-----------------------------------------+
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------------+    +---------------+    +---------------+
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Cela semble naturel, mais cela pose quelques problèmes. Par exemple, lorsque le nombre de nœuds enfants varie, vous avez besoin de quelque chose comme un tableau ou une liste pour gérer les enfants.

En utilisant uniquement les (premiers) pointeurs enfant et (suivant) frères, nous obtenons quelque chose qui ressemble à ceci:

       +-------------------+
       |        root       |
       | child    sibling  +--->NULL
       +--+----------------+
          |             
+----------------+    +----------------+    +----------------+
|    node1       |    |     node2      |    |     node3      |
| child  sibling +--->| child  sibling +--->| child  sibling +--->NULL
+--+-------------+    +--+-------------+    +--+-------------+
   |                     |                     |

Évidemment, ce type de structure peut tout aussi bien représenter les arbres, mais il offre également certains avantages. Le plus important est que nous n'avons plus à nous soucier du nombre de nœuds enfants. Lorsqu'il est utilisé pour un arbre d'analyse, il offre une représentation naturelle pour un terme comme "a + b + c + d + e" sans devenir un arbre profond.

Les bibliothèques de collections offrent-elles des structures arborescentes comme ça? Les analyseurs utilisent-ils une telle structure? Sinon, quelles en sont les raisons?

Les arbres, comme les listes, sont des "types de données abstraits" qui peuvent être implémentés de différentes manières. Chaque voie a ses avantages et ses inconvénients.

Dans le premier exemple, le principal avantage de cette structure est que vous pouvez accéder à n'importe quel enfant dans O (1). L'inconvénient est que l'ajout d'un enfant peut parfois être un peu plus cher lorsque le tableau doit être étendu. Ce coût est cependant relativement faible. C'est également l'une des implémentations les plus simples.

Dans le deuxième exemple, le principal avantage est que vous ajoutez toujours un enfant dans O (1). Le principal inconvénient est que l'accès aléatoire à un enfant coûte O (n). De plus, cela peut être moins intéressant pour les arbres énormes pour deux raisons: il a une surcharge de mémoire d'un en-tête d'objet et de deux pointeurs par nœud, et les nœuds sont répartis de manière aléatoire sur la mémoire, ce qui peut entraîner beaucoup d'échanges entre le cache du processeur et le mémoire lorsque l'arbre est parcouru, ce qui rend cette implémentation moins attrayante pour eux. Ce n'est cependant pas un problème pour les arborescences et applications normales.

Une dernière possibilité intéressante qui n'a pas été mentionnée est de stocker tout l'arbre dans un seul tableau. Cela conduit à un code plus complexe, mais est parfois une implémentation très avantageuse dans des cas spécifiques, en particulier pour les énormes arborescences fixes, car vous pouvez économiser le coût de l'en-tête de l'objet et allouer de la mémoire contiguë.

Presque tous les projets qui ont un modèle ou un document modifiable auront une structure hiérarchique. Il peut être utile d'implémenter le «nœud hiérarchique» en tant que classe de base pour différentes entités. Souvent, la liste chaînée (enfant frère, 2e modèle) est le moyen naturel de croissance de nombreuses bibliothèques de classes, mais les enfants peuvent être de types divers, et probablement un " modèle objet " n'est pas ce que nous considérons lorsque nous parlons des arbres en général.

Mon implémentation préférée d'un arbre (nœud) de votre premier modèle est un one-liner (en C #):

public class node : List<node> { /* props go here */ }

Héritez d'une liste générique de votre propre type (ou héritez de toute autre collection générique de votre propre type). La marche est possible dans un sens: former la racine vers le bas (les objets ne connaissent pas leurs parents).

Arbre parent uniquement

Un autre modèle que vous n'avez pas mentionné est celui où chaque enfant a une référence à son parent:

               null
                 |
       +---------+---------------------------------+
       |       parent                              |
       | root                                      |
       +-------------------------------------------+
          |                   |                |
+---------+------+    +-------+--------+    +--+-------------+
|     parent     |    |     parent     |    |     parent     |
|     node 1     |    |     node 2     |    |     node 3     |
+----------------+    +----------------+    +----------------+

La marche dans cet arbre n'est possible que dans l'autre sens, normalement tous ces nœuds seront stockés dans une collection (tableau, table de hachage, dictionnaire, etc.) et un nœud sera localisé en recherchant la collection sur des critères autres que la position hiérarchique dans le arbre qui ne serait généralement pas de première importance.

Ces arborescences parentales sont généralement visibles dans les applications de base de données. Il est assez facile de trouver les enfants d'un nœud avec les instructions "SELECT * WHERE ParentId = x". Cependant, nous les trouvons rarement transformés en objets de classe de nœud d'arbre en tant que tels. Dans les applications d'état (de bureau), elles peuvent être encapsulées dans des contrôles de nœud d'arbre existants. Dans les applications (Web) sans état, cela peut même être improbable. J'ai vu des outils de génération de classe ORM-mapping lancer des erreurs de débordement de pile lors de la génération de classes pour des tables qui ont une relation avec elles-mêmes (gloussement), alors peut-être que ces arbres ne sont pas si communs après tout.

arbres navigables bidirectionnels

Cependant, dans la plupart des cas pratiques, il est pratique d'avoir le meilleur des deux mondes. Les nœuds qui ont une liste d'enfants et connaissent en plus leur parent: les arbres navigables bidirectionnels.

                          null
                            |
       +--------------------+--------------------+
       |                  parent                 |
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------+-----+    +-------+-------+    +---+-----------+
|      parent   |    |     parent    |    |  parent       |
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Cela apporte de nombreux autres aspects à considérer:

• Où mettre en œuvre la liaison et la dissociation des parents?
  • laissez la logique bussiness prendre soin et laissez l'aspect hors du nœud (ils oublieront!)
  • les nœuds ont des méthodes pour créer des enfants (ne permettent pas de réorganiser) (choix Microsofts dans leur implémentation DOM System.Xml.XmlDocument, ce qui m'a presque rendu fou la première fois que je l'ai rencontré)
  • Les nœuds prennent un parent dans leur constructeur (ne permet pas de réorganiser)
  • dans toutes les méthodes add (), insert () et remove () et leurs surcharges des nœuds (généralement mon choix)
• Persistance
  • Comment marcher dans l'arbre quand il persiste (laisser de côté les liens parentaux par exemple)
  • Comment reconstruire la liaison bidirectionnelle après la désérialisation (redéfinir tous les parents comme une action post-désérialisation)
• Notifications
  • Des mécanismes statiques (drapeau IsDirty), manipulés récursivement dans les propriétés?
  • Événements, remontez à travers les parents, descendez à travers les enfants, ou les deux (pensez à la pompe à messages de Windows par exemple).

Maintenant, pour répondre à la question , les arbres navigables bidirectionnels ont tendance à être (dans ma carrière et mon domaine jusqu'à présent) les plus largement utilisés. Les exemples sont l'implémentation Microsofts de System.Windows.Forms.Control ou System.Web.UI.Control dans le framework .Net, mais aussi chaque implémentation DOM (Document Object Model) aura des nœuds qui connaissent leur parent ainsi qu'une énumération de leurs enfants. La raison: facilité d'utilisation plutôt que facilité de mise en œuvre. De plus, ce sont généralement des classes de base pour des classes plus spécifiques (XmlNode peut être la base des classes Tag, Attribute et Text) et ces classes de base sont des endroits naturels pour mettre des architectures génériques de sérialisation et de gestion des événements.

L'arbre est au cœur de nombreuses architectures, et pouvoir naviguer librement signifie pouvoir implémenter des solutions plus rapidement.

Je ne connais aucune bibliothèque de conteneurs qui prend directement en charge votre deuxième cas, mais la plupart des bibliothèques de conteneurs peuvent facilement prendre en charge ce scénario. Par exemple, en C ++, vous pourriez avoir:

class Node;  // forward reference to satisfy the compiler
typedef std::list<Node*> NodeList;
class Node : public NodeList { /* . . . */ };  // a node is also a list

Node* n = new Node;
n->push_back(new Node);
Node* tree = new Node;
tree->push_back(new Node);
tree->push_back(n);

Les analyseurs utilisent probablement une structure similaire à celle-ci, car elle prend en charge efficacement les nœuds avec un nombre variable d'éléments et d'enfants. Je ne sais pas avec certitude car je ne lis généralement pas leur code source.

Un des cas où il est préférable d'avoir la gamme d'enfants est lorsque vous avez besoin d'un accès aléatoire aux enfants. Et c'est généralement lorsque les enfants sont triés. Par exemple, l'arborescence hiérarchique de type fichier peut l'utiliser pour une recherche de chemin plus rapide. Ou arbre de balises DOM lorsque l'accès à l'index est très naturel

Un autre exemple est lorsque le fait d'avoir des "pointeurs" vers tous les enfants permet une utilisation plus pratique. Par exemple, les deux types que vous avez décrits peuvent être utilisés lors de l'implémentation de relations arborescentes avec une base de données relationnelle. Mais le premier (maître-détail du parent aux enfants dans ce cas) permettra d'interroger avec SQL général pour des données utiles, tandis que le second vous limitera de manière significative.