Diskussion:Baum (Datenstruktur)

Kapitel aus Baum (Graphentheorie) (dort gelöscht, könnte für diesen Artikel übernommen werden)

Gewurzelte Bäume, insbesondere Out-Trees, werden häufig als Datenstruktur verwendet. Bei beschränkter Ordnung können diese so implementiert werden, dass jeder Knoten einen festen Satz an Variablen oder ein Array für die Referenzen auf seine Kinder enthält. Häufig besitzen die Knoten auch eine Referenz auf ihren Elternknoten (back pointer). Ein Baum unbeschränkter Ordnung kann implementiert werden, indem man statt Arrays dynamische Listen verwendet. In Programmiersprachen ohne dynamische Listen hat sich auch ein Verfahren bewährt, bei dem ein allgemeiner Baum durch einen Binärbaum implementiert wird:

Die rötliche Linie zeigt dabei den realisierten allgemeinen Baum, während die Pfeile die tatsächlichen Zeigerstrukturen repräsentieren. Das Grundprinzip besteht darin, dass ein Zeiger jeweils auf das am weitesten links stehenden Kind zeigt, während der andere auf den rechten Geschwister-Knoten verweist. Hierbei ist zwar ein direkter Zugriff auf einzelne bestimmte Kind-Knoten nicht mehr möglich, da man sich über die Geschwister voranarbeiten muss. Dafür ist diese Implementierung sehr speichereffizient.

Unterschied zu Gewurzelter Baum

Und dann gibt es noch

• Out-Tree und
• In-Tree

Da könnte man mal einiges zusammenlegen. --Siehe-auch-Löscher (Diskussion) 13:13, 21. Jan. 2016 (CET)

Krasses Beispiel für einen sog. "Naja"-Artikel

Wenn man sich überlegt, daß der Artikel richtigerweise das Problem das Auffindens des Tuple-Inhaltes an den Anfang stellt, dann ist doch irgendwie klar, daß der Weg, wie durch das Geflecht der Einträge geschritten wird das eigentliche Thema ist, ob die Verweis-Information am Ende eines Tuples stehen ( also schreitend bis zum Ziel durch den (Binär-)- oder Hierarchischen Baum ) oder in einem verweisenden Index. Wie machen das denn nun aktuelle Datenbanken ? --Martin (mhonline) 02:29, 10. Jul. 2019 (CEST) (unvollständig signierter Beitrag von Mhonline (Diskussion | Beiträge) )

"Breitensuchebaum" (Bildunterschrift)

Was soll ein Breitensuchebaum sein? Wie sucht man darin? (nicht signierter Beitrag von 84.63.67.134 (Diskussion) 09:44, 3. Feb. 2020 (CET))

Ein Breitensuchebaum ist das Ergebnis der Breitensuche, eben ein Baum. In der Grafik ist die Reihenfolge der traversierten Elemente dargestellt. Habe die Titelgrafik jedoch bereits geändert.--DixMartin (Diskussion) 20:47, 3. Feb. 2020 (CET)

komplett überarbeitet am 2.2.20

@DixMartin:

• Der "Breitensuchebaum" ist ziemlich unwichtig. Ich würde die Abb., die ja bei der Seiteninfo mit angezeigt wird, nicht so weit nach oben hängen. Lieber den normalen binären Suchbaum.

geändert in DS Baum. erl.

• "logarithmischer Zeit gegenüber linearer Zeit bei Feldern": Die binäre Suche im Array ist durch Bäume nicht zu übertreffen. Nur wenn Modifikationen hinzukommen, sind die dort nicht logarithmisch lösbar.

Zitat aus Artikel Binäre Suche: Der Such-Algorithmus entspricht auch der Suche in einem binären Suchbaum, wenn man das Array als solchen interpretiert: das mittlere Element ist die Wurzel, die Mitten der so entstehenden Hälften die Wurzeln der entsprechenden Teilbäume und so fort. Der aus dieser Interpretation resultierende Binärbaum ist sogar ein sog. vollständig balancierter Binärbaum, also ein Binärbaum, bei dem die Längen der Pfade von den Blättern zur Wurzel sich um höchstens 1 unterscheiden. ...

Teilt man nicht in der Mitte, so ist das Ergebnis immer noch ein binärer Suchbaum, jedoch ist er u. U. nicht balanciert und nicht optimal.

Die große Überlegenheit des binären Suchbaums gegenüber der binären Suche im Array liegt erstens im besseren Verhalten bei Einfügungen und Löschungen, bei denen im Mittel ein linearer Aufwand anfällt. :Bei Bäumen gibt es auch in diesen Fällen Implementierungen mit garantiert logarithmischer Laufzeit. Dort ist auch die Speicherverwaltung einfacher, da Änderungen nicht das ganze Array betreffen, sondern :sich mit dem Entstehen oder Verschwinden eines Elementes direkt verbinden lassen. Zweitens können Bäume besser als das Array an Häufigkeiten angepasst werden. Wenn aber das Array schon fertig sortiert ist und sich dann nicht mehr ändert und Zugriffswahrscheinlichkeiten keine Rolle spielen, ist das Array ein gutes Verfahren.

--> Die Binärsuche findet, wenn man so will, also auch im Binärbaum statt. (Andersherum könnte man argumentieren, dass es keine Datenstruktur Baum gäbe, weil Speicher heutzutage immer linear angeordnet ist.)

• "Fibonaci-Bäume" raus aus den Suchbäumen, weil sie Modifikationen (Einfügungen und Löschungen) nicht kennen. (Sie dienen fast nur für gewisse Abschätzungen bei den AVL-Bäumen.)

erl.

• Begriffe wie Elter/Kind und Vorfahr/Nachfahr werden gebraucht und müssen erklärt werden. Den "Terminologie"-Abschnitt würde ich unbedingt VOR dem Abschnitt über die Baumsorten bringen, weil er für alle gilt.

erl.

Soviel erstmal. --Nomen4Omen (Diskussion) 11:32, 3. Feb. 2020 (CET)

@Nomen4Omen:Vielen Dank für die Anmerkungen, AW s.o. und im Artikel.--DixMartin (Diskussion) 21:34, 3. Feb. 2020 (CET)

@DixMartin:

Der Sinngehalt deines Einschubs

"--> Die Binärsuche findet, wenn man so will, also auch im Binärbaum statt. (Andersherum könnte man argumentieren, dass es keine Datenstruktur Baum gäbe, weil Speicher heutzutage immer linear angeordnet ist.)"

erschließt sich mir leider nicht. Der wesentliche Unterschied zwischen den beiden Strukturen ist, dass bei der Binärsuche im Array eine Indizierung (also Rechnungen +,-,×,÷) mit Speicheradressen (Indizes) stattfindet, wogegen im Baum Zeiger zum Zuge kommen, die nur einen Zweck bezüglich der Speicherzuordnung zu erfüllen haben und deren zahlenmäßiger Wert ohne sonstige Bedeutung ist. --Nomen4Omen (Diskussion) 19:16, 5. Feb. 2020 (CET)

@Nomen4Omen:Das ist korrekt. M.E. ist der wesentliche Unterschied zwischen Array und Baum jedoch nicht die physikalische Umsetzung des Zugriffs (Adressindex vs Zeiger), sondern die zugrundeliegende (gedankliche) Daten-Struktur. Diese ist linear bzw. verzweigend. Dadurch ergeben sich eben lineare oder logarithmische Zugriffszeiten - wie auch bei der Binärsuche. Aber: ja, diese gedankliche (Baum-)Struktur wird mittels Array abgebildet. Seis drum: Im Artikel habe ich einen Hinweis zur Binärsuche angebracht. --DixMartin (Diskussion) 22:44, 5. Feb. 2020 (CET)

@DixMartin:
Tut mir echt leid, dass ich dich wieder nicht voll und ganz verstehe.

„... (gedankliche) Daten-Struktur. Diese ist linear bzw. verzweigend. Dadurch ergeben sich eben lineare oder logarithmische Zugriffszeiten ...“

Schienen wir uns nicht soeben einig zu sein, dass die Zugriffszeiten in BEIDEN Fällen logarithmisch sind? Genauer: im direkten Zugriff (das ist die Suche mit Schlüssel) logarithmisch, im sequentiellen Zugriff auf das einzelne Objekt total konstant (Array) vs. im Mittel konstant (Baum).
Ein wesentlicher Unterschied kommt erst dann heraus, wenn Dynamik ins Spiel kommt – sprich: eingefügt bzw. gelöscht wird. Das kann im Baum (weil er, wie du sagst, „gedanklich verzweigend“ [so ein wunderbar schönes erleuchtetes Wort!] ist,) besser gelöst werden als im Array, wo ggf. Platz geschaffen werden muss durch Verschiebungen, die linear kosten.
Aber ohne Dynamik sind die beiden asymptotisch gleich gut lösbar – mit leichten Geschwindigkeits- und Programmtechnik-Vorteilen für das Array. Der Satz

„So erfolgt beispielsweise eine Suche nur in logarithmischer Zeit gegenüber linearer Zeit bei Feldern (zu Details vergleiche Artikel Binärsuche).“

ist also falsch, weil die auch im Array – wie in Binäre Suche gezeigt – logarithmisch arbeitet: maximal $\lceil \log _{2}(n+1)\rceil =\lfloor \log _{2}(n)+1\rfloor$ Vergleichsschritte, d.h. Zeitkomplexität ${\mathcal {O}}(\log \ n)$. --Nomen4Omen (Diskussion) 15:00, 17. Feb. 2020 (CET)

Solange du die Ähnlichkeit der Binärsuche und Binärbaumsuche nicht siehst können wir glaub ich ewig weiterdiskutieren. Um das Thema abzukürzen: Du hast ja einen gute Alternative zur Suche mit den Einfüge- und Löschoperationen erwähnt. Vorschlag: Ersetzte meinen Satz mit Suche durch eine Einfüge-/oder Löschoperation. --DixMartin (Diskussion) 22:08, 17. Feb. 2020 (CET)

Elternteil

Habe ich bei Halbwaisen schon mal gehört, aber in diesem Zusammenhang noch nie. Es kommt auch einmal Elternknoten vor, was ich wesentlich besser finde. Auch bei Geschwistern, Kindern ist es kein Schaden -knoten dranzuhängen (was man natürlich, wenn's sehr oft vorkommt, mal weglassen kann). Ich plädiere – und habe es bei den Binärbäumen ohne Proteste durchgehalten – sogar für Elter und Elterknoten (ohne "n" in der Mitte), was gleichzeitig ausdrückt, dass es viele Geschwister, aber nur einen wikt:Elter geben kann (im Ggs. zur menschlichen Familie). Die Engländer haben parent (im Singular). –Nomen4Omen (Diskussion) 23:20, 19. Mai 2021 (CEST)

Elternteil habe ich auch bei klassischer Vater-Mutter-Kind-Familie gehört, wobei der eine Teil Vater und der andere Teil Mutter ist. Beim Wurzelbaum gibt es jedoch nur einen Elter. Wenn man das Gendern nicht ganz so wichtig nimmt, wäre auch einfach Vater-Knoten oder kurz Vater geeignet.--DixMartin (Diskussion) 23:23, 20. Mai 2021 (CEST)

Alles völlig richtig! Leider hat man das Gendern nicht ganz allein in der Hand.

Viele WP-Artikel haben bei solchen Begriffsbestimmungen eine Stelle, wo sie mehrere Möglichleiten erwähnen, sich für den Rest des Artikels aber für eine entscheiden. –Nomen4Omen (Diskussion) 08:33, 21. Mai 2021 (CEST)

Vorsicht Redundanz

Erst kürzlich habe ich die Redundanzdiskussion zwischen Baum (Graphentheorie) und Baum (Datenstruktur) aufgelöst. Erster Artikel zeigt das abstrakte Konstrukt, zweiter zeigt dessen Anwendung für bspw. Suchalgorithmen. Durch die jüngsten Ergänzungen verschwimmen die Grenzen wieder ein wenig. Insbesondere den bereits unter Baum (Graphentheorie)#Programmierung vorhandenen Baumtest finde ich eher unpassend, weil die Datenstruktur Baum die Baumeigenschaft immanent besitzt und daher nicht noch getestet werden muss.--DixMartin (Diskussion) 23:23, 20. Mai 2021 (CEST)