Diskussion:Balancierter Baum

Komplett neugeschrieben 136.199.8.128 8. Jul 2005 16:13 (CEST)

Ich habe den Artikel jetzt komplett neu geschrieben. Balance wird jetzt definiert über $h=O(\log n)$; so sind jetzt alle Balance-Konzepte, die ich kenne (AVL, Rot-Schwarz, B-Baum, Gewichtsbalancierter Baum) erfasst und werden erwähnt.

Ich freue mich auf Eure Verbesserungen, unter anderem zu folgenden Problemen:

• Es ist mir nicht gelungen, auf die Suchbäume als Beispiel zu verzichten – die sind zwar die Anwendung balancierter Bäume, mathematisch jedoch eine Erweiterung des Baum-Konzepts.
• Habe ich den Beitrag von Bodo Thiesen berücksichtigt, dass balancierte Bäume nicht Binärbäume sein müssen? Mein Verweis auf die $k$-nären Bäume verwirrt, glaube ich, mehr als er klarstellt.

Ich finde den Verweis auf k-näre Bäume sehr wichtig und ergänze die Link-Liste unten um 234-Bäume

Balancierte Bäume müssen nicht unbedingt zur Höhe $log_{2}n$ balanciert sein, eigentlich kann man Bäume zu allen Funktionen $f(n)\in \Omega (\log _{2}n)$ balancieren (siehe O-Notation). Besipielsweise ist jeder Baum zu $h=n$ balanciert, da seine Höhe immer kleiner als n ist. In diesem entarteten Fall erhält man ein linke bzw. rechte lineare liste. Sollte die Definition von Balance nicht auf allgemeine Funktionen der Knotenzahl erweitert werden? oder verwirrt das zu sehr?

Weil eine Komplexität von O(log n) erreichbar sind, interessiert man sich halt nicht für asymptotisch schneller wachsende Bäume. Jedenfalls nicht, wenn es um Datenstrukturen geht, aber auch theoretisch scheinen mir die "allgemeineren" balancierten Bäume nicht viel herzugeben. Für den Artikel finde ich die Definition mit O(log n) auf jeden Fall gut, alles andere wäre mE Theoriefindung.

Balancierter Baum? Gibt denn sowas?

In den mir bekannten deutschen Fachbüchern werden die "balancierten" Bäume als "ausgeglichene" benannt. Meines Erachten ist der Begriff "ausgeglichener Baum" der deutsche Fachbegriff für den englischen "balanced tree" und "balancierte Bäume" eine falsche Übersetzung.

Deshalb würde ich vorschlagen "balanciert" durch "ausgegelichen" zu ersetzen.

In der deutschen Fachliteratur existieren beide Begriffe. Im Noltemeier, der etwas älter ist und keine Übersetzung aus dem Englischen ist, wird der Begriff balancierter Baum verwendet. Im Sedgewick, einem neueren, aus dem englischen übersetzten Buch, wird "ausgeglichen" verwendet. Daher schlage ich ein Verschieben nach "ausgeglichener Baum" vor, was ja auch eine Weiterleitung von "balancierter Baum" erzeugt. Ich kann das nicht selbst vornehmen, da ich gerade erst eingestiegen bin.

Fehler in der Höhenbalance

"Diese Bäume stellen eine binäre Realisierung der 2-3-4-Bäume dar, einer speziellen Variante der B-Bäume."

Diese Aussage ist nicht korrekt, da bei jedem B-Baum die Blätter in derselben Ebene liegen. Ein Rot-Schwarz-Baum ist somit (normalerweise) kein 2-3-4 Baum und kein B-Baum.

Ganz abgesehen davon IST der 2-3-4- Baum der (einzige) binäre B-Baum. Ein B-Baum ist zwar immer balanciert, die Umkehrung gilt aber nicht. (nicht signierter Beitrag von 194.166.213.199 (Diskussion) 14:24, 7. Jul 2013 (CEST))

Was ist k?

k-närer Baum, log_k.... und nirgends ist k definiert. Muss man das immer erst jedem Autoren einprügeln dass er erst mal seine Variablen definiert und erklärt bevor er drauflosschreibt? Immer wieder der selbe Fehler.

Dass es immer noch so richtig pampige Leser gibt !? Immer dieselben mit dieser irren Pampigkeit. Dass er überhaupt nicht erstmal ein bisschen Manieren lernt ? Er will doch was, oder? --92.196.33.71 19:45, 19. Mai 2019 (CEST)