Werden Bäume von einer „Erstkind-Geschwister“ -Struktur organisiert? Wenn nein, warum nicht?

Normalerweise sind Baumdatenstrukturen so organisiert, dass jeder Knoten Zeiger auf alle untergeordneten Knoten enthält.

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

Dies scheint natürlich, bringt jedoch einige Probleme mit sich. Wenn sich beispielsweise die Anzahl der untergeordneten Knoten ändert, benötigen Sie ein Array oder eine Liste, um die untergeordneten Knoten zu verwalten.

Indem wir stattdessen nur (erste) Kind- und (nächste) Geschwisterzeiger verwenden, erhalten wir etwas, das so aussieht:

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

Diese Art von Struktur kann natürlich auch Bäume darstellen, bietet aber auch einige Vorteile. Das Wichtigste ist, dass wir uns keine Gedanken mehr über die Anzahl der untergeordneten Knoten machen müssen. Wenn es für einen Analysebaum verwendet wird, bietet es eine natürliche Darstellung für einen Ausdruck wie "a + b + c + d + e", ohne ein tiefer Baum zu werden.

Bieten Sammlungsbibliotheken solche Baumstrukturen an? Verwenden Parser eine solche Struktur? Wenn nein, aus welchen Gründen?

Bäume sind wie Listen "abstrakte Datentypen", die auf verschiedene Arten implementiert werden können. Jeder Weg hat seine Vor- und Nachteile.

Im ersten Beispiel besteht der Hauptvorteil dieser Struktur darin, dass Sie auf jedes untergeordnete Element in O (1) zugreifen können. Der Nachteil ist, dass das Anhängen eines Kindes manchmal etwas teurer sein kann, wenn das Array erweitert werden muss. Diese Kosten sind jedoch relativ gering. Es ist auch eine der einfachsten Implementierungen.

Im zweiten Beispiel besteht der Hauptvorteil darin, dass Sie in O (1) immer ein Kind anhängen. Der Hauptnachteil ist, dass der zufällige Zugriff auf ein Kind O (n) kostet. Auch es kann sein , weniger interessant für große Bäume aus zwei Gründen: es hat ein Speicher - Overhead von einem Objektkopf und zwei Zeiger pro Knoten und die Knoten zufällig über Speicher verteilt , die möglicherweise vielen Austausch zwischen dem CPU - Cache verursachen und der Speicher, wenn der Baum durchlaufen wird, was diese Implementierung für sie weniger attraktiv macht. Dies ist jedoch kein Problem für normale Bäume und Anwendungen.

Eine letzte interessante Möglichkeit, die nicht erwähnt wurde, besteht darin, den gesamten Baum in einem einzigen Array zu speichern. Dies führt zu komplexerem Code, ist jedoch in bestimmten Fällen manchmal eine sehr vorteilhafte Implementierung, insbesondere für große feste Bäume, da Sie die Kosten für den Objektkopf sparen und zusammenhängenden Speicher zuweisen können.

Fast jedes Projekt mit einem bearbeitbaren Modell oder Dokument hat eine hierarchische Struktur. Es kann nützlich sein, den 'hierarchischen Knoten' als Basisklasse für verschiedene Entitäten zu implementieren. Oft ist die verknüpfte Liste (Kindergeschwister, 2. Modell) die natürliche Art und Weise, wie viele Klassenbibliotheken wachsen, die Kinder können jedoch von unterschiedlichem Typ sein, und wahrscheinlich ist ein " Objektmodell " nicht das, was wir betrachten, wenn wir über Bäume im Allgemeinen sprechen.

Meine Lieblingsimplementierung eines Baums (Knotens) Ihres ersten Modells ist ein Einzeiler (in C #):

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

Von einer generischen Liste Ihres eigenen Typs erben (oder von einer anderen generischen Sammlung Ihres eigenen Typs erben). Das Gehen ist in eine Richtung möglich: Bilden Sie die Wurzel nach unten (Gegenstände kennen ihre Eltern nicht).

Eltern nur Baum

Ein anderes Modell, das Sie nicht erwähnt haben, ist das, bei dem jedes Kind einen Verweis auf sein Elternteil hat:

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

Das Gehen in diesem Baum ist nur in umgekehrter Richtung möglich. Normalerweise werden alle diese Knoten in einer Sammlung (Array, Hashtable, Wörterbuch usw.) gespeichert, und ein Knoten wird durch Durchsuchen der Sammlung nach anderen Kriterien als der hierarchischen Position in der Datenbank gefunden Baum, der in der Regel nicht von primärer Bedeutung wäre.

Diese übergeordneten Baumstrukturen werden normalerweise in Datenbankanwendungen angezeigt. Mit den Anweisungen "SELECT * WHERE ParentId = x" können die untergeordneten Elemente eines Knotens ganz einfach gefunden werden. Wir finden diese jedoch selten als solche in Baumknotenklassenobjekte transformiert. In Statefull-Anwendungen (Desktop-Anwendungen) können sie in vorhandene Tree-Node-Steuerelemente eingebunden werden. In zustandslosen (Web-) Anwendungen kann dies sogar unwahrscheinlich sein. Ich habe gesehen, dass ORM-Mapping-Klassengenerator-Tools beim Generieren von Klassen für Tabellen, die eine Beziehung zu sich selbst haben (chuckle), Stapelüberlauffehler auslösen.

bidirektionale schiffbare Bäume

In den meisten praktischen Fällen ist es jedoch praktisch, das Beste aus beiden Welten zu haben. Knoten, die eine Liste von Kindern haben und zusätzlich deren Eltern kennen: bidirektionale navigierbare Bäume.

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

Dies bringt viele weitere Aspekte mit sich, die berücksichtigt werden müssen:

• Wo kann die Verknüpfung und Aufhebung der Verknüpfung von Eltern implementiert werden?
  • Lass die Geschäftslogik auf dich aufpassen und lass den Aspekt aus dem Knoten (sie werden es vergessen!)
  • Knoten haben Methoden zum Erstellen von Kindern (erlaubt keine Neuordnung) (Microsofts Auswahl in ihrer System.Xml.XmlDocument-DOM-Implementierung, was mich fast verrückt gemacht hat, als ich es zum ersten Mal sah)
  • Knoten nehmen ein übergeordnetes Element in ihren Konstruktor auf (keine Neuordnung möglich)
  • in allen add (), insert () und remove () Methoden und deren Überladung der Knoten (normalerweise meine Wahl)
• Ausdauer
  • Wie man beim Fortbestehen auf dem Baum herumläuft (zum Beispiel Eltern-Links weglassen)
  • Neuerstellen der bidirektionalen Verknüpfung nach der Deserialisierung (erneutes Festlegen aller übergeordneten Elemente als Aktion nach der Deserialisierung)
• Benachrichtigungen
  • Statische Mechanismen (IsDirty-Flag), die in Eigenschaften rekursiv behandelt werden?
  • Ereignisse sprudeln durch die Eltern, durch die Kinder oder in beide Richtungen (z. B. die Windows-Nachrichtenpumpe).

Um die Frage zu beantworten : Bidirektionale schiffbare Bäume sind (in meiner bisherigen Karriere und auf meinem Gebiet) die am häufigsten verwendeten. Beispiele sind Microsofts Implementierung von System.Windows.Forms.Control oder von System.Web.UI.Control im .Net-Framework, aber auch jede DOM-Implementierung (Document Object Model) verfügt über Knoten, deren übergeordnetes Element sowie eine Aufzählung bekannt sind ihrer Kinder. Der Grund: Benutzerfreundlichkeit über einfache Implementierung. Außerdem handelt es sich normalerweise um Basisklassen für spezifischere Klassen (XmlNode kann die Basis der Tag-, Attribut- und Textklassen sein). Diese Basisklassen sind natürliche Orte, um generische Serialisierungs- und Ereignisbehandlungsarchitekturen zu platzieren.

Tree ist das Herzstück vieler Architekturen. Wenn Sie frei navigieren können, können Sie Lösungen schneller implementieren.

Ich kenne keine Container-Bibliothek, die Ihren zweiten Fall direkt unterstützt, aber die meisten Container-Bibliotheken können dieses Szenario problemlos unterstützen. In C ++ könnten Sie beispielsweise Folgendes haben:

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

Parser verwenden wahrscheinlich eine ähnliche Struktur, da Knoten mit variabler Anzahl von Elementen und untergeordneten Elementen effizient unterstützt werden. Ich weiß es nicht genau, weil ich normalerweise ihren Quellcode nicht lese.

Einer der Fälle, in denen eine Reihe von Kindern vorhanden ist, ist der, in dem Sie zufälligen Zugriff auf die Kinder benötigen. Und das ist normalerweise, wenn die Kinder sortiert werden. Beispielsweise kann der dateiähnliche Hierarchiebaum dies für eine schnellere Pfadsuche verwenden. Oder DOM-Tag-Baum, wenn der Indexzugriff sehr natürlich ist

Ein weiteres Beispiel ist, wenn die "Zeiger" für alle Kinder eine bequemere Verwendung ermöglichen. Beispielsweise können beide von Ihnen beschriebenen Typen bei der Implementierung von Baumbeziehungen mit relationalen Datenbanken verwendet werden. Ersteres (in diesem Fall Master-Detail vom übergeordneten zum untergeordneten Element) ermöglicht jedoch das Abfragen von nützlichen Daten mit allgemeinem SQL, während letzteres Sie erheblich einschränkt.