Warum wachsen Bäume nach unten?

Warum wachsen Bäume in der Informatik nach unten?

Ich habe das Gefühl, dass es auf einen Drucker zurückgeht und dass ein Programm, das einen Baum durchläuft, zuerst die Wurzel druckt und den Begriff eines bodenlosen Papierstapels verwendet, um die unbestimmten Rekursionsniveaus auszudrücken, die auftreten können.

Verweise:

Bäume wachsen nach unten und haben ihre Wurzeln oben auf der Seite und ihre Blätter unten

Von ON HOLY Kriegen und ein Plädoyer für den Frieden .

Konventionell werden Bäume nach unten gezogen

Aus dem Wikipedia-Artikel über Baumdatenstrukturen.

Echte Bäume wachsen von der Wurzel aufwärts bis zum Himmel, aber Bäume der Informatik wachsen von der Wurzel abwärts

Aus David Schmidts Vorlesungsskripten .

computer-science conventions maxpolk
quelle

Warum sind Mannlöcher rund?

Job

Bäume in alle Richtungen in der Natur gewachsen ... aufwärts, abwärts usw.

CaffGeek

@Job Damit die Kanaldeckel nicht hineinfallen. FTFY. :-)

Gary Rowe

@GaryRowe: Eine weit verbreitete Lüge. Schachtabdeckungen sind in erster Linie rund, weil sie die Enden von Rohren abdecken und Rohre rund sind. Rohre sind rund, weil 1) sie gleichmäßig belastet werden und 2) der Querschnitt für einen bestimmten Umfang maximiert wird. Insgesamt maximiert es die Stärke und Kapazität des Rohrs, die Sie aus einer bestimmten Materialmenge erhalten können.

Jerry Coffin

@ JerryCoffin: Also ... Bäume wachsen nach unten, weil runde Rohre stärker sind als quadratische? ;)

FrustratedWithFormsDesigner

Antworten:

Nur eine Vermutung:

Baumstrukturen wachsen nach unten (Wurzel oben, Blätter unten), weil die Leute vom oberen Rand der Seite nach unten lesen. Wenn Sie einen großen Baum zeichnen, der sich über mehrere Seiten erstreckt, wäre es außerdem umständlich, den Leser zu bitten, ein paar Seiten weiterzuspringen und dann rückwärts zu arbeiten.

Unabhängig davon, ob die Konvention aus dem oben erläuterten Grund oder aus einem anderen Grund begann, setzen wir die Praxis heute genau deshalb fort, weil es sich um eine Konvention handelt. Wir haben entsprechende Begriffe wie den Knoten der obersten Ebene (dh die Wurzel), die nicht so sinnvoll wären, wenn wir die Struktur mit der Wurzel unten zeichnen würden.

Caleb
quelle

@BruceEdiger: Ich gehe davon aus, dass es nur um unterschiedliche Konventionen geht.

FrustratedWithFormsDesigner

@BruceEdiger Das ist etwas ganz anderes. Das kartesische Koordinatensystem wurde vor 375 Jahren eingeführt, daher ist es ziemlich selbstverständlich, sich an diese Konvention zu halten. Grafiksysteme (X11, QuickDraw, Quartz unter iOS) verwenden häufig ein gespiegeltes Koordinatensystem. Ich denke, das hat nichts damit zu tun, wie wir Bäume malen.

Caleb,

IMHO geht der Grund für die umgedrehten Koordinaten auf die Zeit zurück, in der man Terminals hatte. Da der angezeigte Text in der oberen linken Ecke beginnt und die tatsächliche Auflösung variieren kann, war es eine sehr vernünftige Entscheidung, (0,0) als obere linke Ecke festzulegen.

FUZxxl,

@BruceEdiger-Bildschirmkoordinaten werden im Wesentlichen von (x, y) zum Speicherort des Pixels / Zeichens abgebildet. Video-Display-Controller, die für die Zuordnung des Speichers zu einem Bild verantwortlich sind, beginnen an Position 0 in der oberen linken Ecke. Daher ist es eine natürliche Abbildung, (0,0) dort zu haben, da Sie den Speicherort nur mit (y * 80 + x) erhalten können. Dokumentation für den 8-Bit-Computer Ich habe dies gelernt mit: datamuseum.dk/w/images/5/5b/RC702_Tech_Man.pdf

Wenn Sie einen Baum von Hand zeichnen, ist es schwierig zu wissen, wie viel Platz Sie benötigen, und es ist auch schwierig, die Noten ordentlich zu gestalten, ohne vorher die darüber liegende Ebene zu zeichnen. Daher neigen Sie dazu, zuerst die Wurzel zu zeichnen und sie oben zu platzieren, damit Sie mit Ihrem Text fortfahren können, wo immer auf der Seite der Baum endet.

Ian

Die Konvention scheint aus dem Coffman-Graham-Algorithmus zu stammen, der entworfen wurde:

"... zum Anordnen der Elemente einer teilweise geordneten Menge in einer Folge von Ebenen. Der Algorithmus wählt eine Anordnung so, dass ein Element, das in der Reihenfolge nach dem anderen kommt, einer niedrigeren Ebene zugeordnet wird und dass jede Ebene eine Nummer hat von Elementen, die eine festgelegte Breite W nicht überschreiten. "

Ihre Arbeit von 1972 ( PDF ) zeigt einen gerichteten azyklischen Graphen, der von oben nach unten gezeichnet wird. Es ist ein kurzer Schritt, einen Baum auf die gleiche Weise darzustellen.

In diesem Artikel über Layered Graph Drawing finden Sie einige weitere Kommentare zu dieser Visualisierung .

Gary Rowe
quelle

Die Kunst der Computerprogrammierung: Grundlegende Algorithmen, Band 1 - Grundlegende Algorithmen, wurde 1968 veröffentlicht und enthielt einen Abschnitt 2 über Bäume. Kann jemand, der dieses Buch besitzt, überprüfen, ob Diagramme herabwachsende Bäume zeigen? In diesem Fall weist die Geschichte auf eine Konvention hin, die noch früher begonnen hat. Ich frage mich auch, ob die Informatik diese Konvention schon vor 1960 aus der Mathematik übernommen hat. Wolfram zeigt, dass Bäume 1857 untersucht wurden.

maxpolk

@maxpolk Knuth zeichnet seine Bäume mit der Wurzel nach oben ein und erörtert seine Entscheidung (Abschnitt 2.3, S. 311 in der 3. Ausgabe), die Wurzel nach unten umzuwandeln, bevor die erste Ausgabe veröffentlicht wird. Es läuft darauf hinaus, dass "der größte Teil der vorhandenen Literatur von oben nach unten geht und wir ein konsistentes Modell für Diskussionszwecke benötigen" (80% laut Knuths Umfrage).

Ross Patterson

Zeichnen aus dem top > downund left > rightsind in der Informatik populär, weil dies die Startanweisungen in schriftlichem Englisch sind. In Anbetracht der Tatsache, dass die meisten Informatikarbeiten in englischer Sprache verfasst sind, ungeachtet der Muttersprache des Verfassers, wäre dies die am weitesten verbreitete Möglichkeit, Diagramme zu zeichnen.

Für einen englischsprachigen Leser ist es am natürlichsten, ein Diagramm aus top > downoder left > rightals eine der anderen Alternativen zu lesen .

Durchsuchen Sie images.google.com nach directed tree graphund überprüfen Sie die Ergebnisse. Die einzigen Baumdiagramme, die ich finden konnte , waren UML-Klassendiagramme, und nur deshalb, weil UML diese Konvention für Klassendiagramme gewählt hat. Alle anderen UML-Diagramme gehen left > rightoder up > down.

Ich würde es in Betracht ziehen, gerichtete Baumdiagramme down > upso unnatürlich wie das Lesen der am häufigsten geposteten E-Mail-Threads zu lesen. was zu sagen ist völlig unnatürlich.

quelle