Ist ein Baum mit Knoten, die auf das übergeordnete Element verweisen, noch ein Baum?

8

Wenn wir für jeden Knoten in einem Baum auf den übergeordneten Knoten verweisen, haben wir dann noch einen Baum (per Definition)?

Die Wikipedia-Definition lautet:

In der Informatik ist ein Baum ein weit verbreiteter abstrakter Datentyp (ADT) oder eine Datenstruktur, die dieses ADT implementiert und eine hierarchische Baumstruktur mit einem Stammwert und Teilbäumen von Kindern simuliert, die als Satz verknüpfter Knoten dargestellt werden.

Geben Sie hier die Bildbeschreibung ein

data-structures trees Mohsen
quelle
3
Was lässt dich daran zweifeln?
2
Solange die übergeordneten und die untergeordneten Links unterschiedlich sind, können Sie davon ausgehen, dass die untergeordneten Links den Baum bilden und die übergeordneten Links nur ein Implementierungsdetail sind.
Mouviciel

Antworten:

16

Ein Baum ist ein zusammenhängender azyklischer Graph. In dem Fall, in dem wir "übergeordnete" Links haben, wäre dies nur ein ungerichteter Baum, aber definitiv immer noch ein Baum. Wenn Sie angeben würden, dass es sich bei dem Beispiel um ein gerichtetes Diagramm handelt, wird es nicht als Baum betrachtet (aber es gibt natürlich keine Möglichkeit, anhand des beabsichtigten Codes zu erkennen).

Einige "Bäume" der Informatik enthalten beispielsweise Verknüpfungen von jedem Knoten zurück zur Wurzel oder Verknüpfungen entlang jeder Ebene eines B + -Baums. Ein Informatiker würde diese Dinge wahrscheinlich immer noch Bäume nennen, ein Mathematiker nicht.

U2EF1
quelle
1
+1, um darauf hinzuweisen, dass übergeordnete Links (Links in beide Richtungen) das Diagramm einem ungerichteten Diagramm entsprechen.
Giorgio
Können wir sagen, dass ein azyklischer Graph ein Baum ist?
Mohsen
4
@ Mohsen Ein (gerichteter) azyklischer Graph, der einen Knoten mit zwei Eltern enthält, ist kein Baum
Izkata
@Mohsen: Sie können einen Baum auch als Diagramm mit einem bestimmten Wurzelknoten definieren, sodass ein eindeutiger Pfad von der Wurzel zu einem anderen Knoten vorhanden ist. Natürlich gibt es azyklische Graphen, die diese Definition nicht erfüllen.
Giorgio
-2

Folgen wir dieser Definition. Werde sicher die ans bekommen.

Ein verbundener Graph G wird als Baum bezeichnet, wenn durch das Entfernen einer seiner Kanten G getrennt wird. Da das oben angegebene Diagramm diese Aussage nicht unterstützt, können wir nicht sagen, dass das angegebene Diagramm ein Baum ist.

Für weitere Informationen können Sie diesen Link fortsetzen.

http://win.ua.ac.be/~vanhoudt/graph/trees.pdf

tauchen
quelle
1
Sie verwenden hier den Standpunkt des Mathematikers. Beachten Sie, dass U2EF1 in ihrer Antwort sagt: Ein Informatiker würde diese Dinge wahrscheinlich immer noch Bäume nennen, ein Mathematiker nicht. . Ihre Antwort ist in dieser Hinsicht im Grunde dieselbe wie die von Uiquité.
Martijn Pieters
Das zitierte Papier geht von ungerichteten Graphen aus. Diese Definition von Bäumen ist für einen gerichteten Graphen nicht geeignet, da (a) erwähnt werden muss, dass DAGs einschließlich Bäume höchstens schwach verbunden sein können, und weil (b) sie mehrere Wurzelknoten zulässt. Beachten Sie nun, dass der Graph in der Frage ein gerichteter Graph ist (wenn auch einer mit Backlinks) und dass es immer noch ein Konzept eines Wurzelknotens gibt (Hierarchie wird durch vertikale Position bezeichnet). Eine bessere Definition für einen gerichteten Baum wäre: „Ein (gerichteter) Baum ist leer oder hat genau einen Wurzelknoten, von dem aus alle Knoten erreichbar sind“.
Amon