imported>Ulanwp: Fehlenden Sprachparameter eingefügt

2026-02-13T19:31:35Z

Fehlenden Sprachparameter eingefügt

Neue Seite

Ein '''balancierter Baum''' ({{enS}} oft ''self-balancing tree'') ist in der [[Informatik]] ein besonderer [[Baum (Datenstruktur)|Baum]], der eine ''maximale'' [[Höhe (Graphentheorie)|Höhe]] von <math>c\cdot\log(n)</math> garantiert, wobei <math>n</math> die Anzahl der Elemente im Baum angibt und <math>c</math> eine von <math>n</math> unabhängige Konstante ist. Manche Autoren rechnen auch Datenstrukturen dazu, die Vorkehrungen enthalten, dass die mittlere Höhe oder [[Gewichteter binärer Suchbaum#Zugriffsverteilung und gewichtete Pfadlänge|Pfadlänge]] bei jedem Baum logarithmisch bleibt.

== Problem: Entartung ==
Eine wichtige Anwendung von Bäumen in der Informatik ist deren Nutzung als [[Suchbaum]]. Die Laufzeit der wichtigsten [[Suchbaum#Operationen|Operationen in einem Suchbaum]] (Suchen, Einfügen und Löschen eines Wertes) hängt im schlechtesten Fall linear von der Höhe des Baumes ab (die Operationen haben eine [[Komplexität (Informatik)|Komplexität]] von <math>\mathcal{O}(h)</math>; <math>h</math> Höhe des Baumes).

Jeder [[k-närer Baum|''k''-näre Baum]] mit <math>n</math> Knoten hat eine Höhe von <math>h\geq\log_k (n+1)</math>; und im Durchschnitt immer noch <math>c\cdot\log_k\ n</math> für ein gewisses konstantes <math>c</math>. So sind auch die Operationen auf einem Baum mindestens der Komplexität <math>\mathcal{O}(\log_k n) = \mathcal{O}(\log n)</math>.

[[Datei:Balancierter Baum - Baum ohne Werte.svg|mini|zentriert|Beispiel für nicht balancierten Baum]]

Fügt man jedoch zum Beispiel einem Suchbaum eine große Menge bereits sortierter Daten ein, wächst dieser ungleichmäßig und hat im Extremfall eine Höhe von <math>n</math> mit der unerwünschten Folge, dass auch jede folgende Einfüge-, Such- und Löschoperation der Komplexität <math>\mathcal{O}(n)</math> ist.

[[Datei:Balancierter Baum - entarteter Suchbaum.PNG|mini|zentriert|Ein zu einer Liste entarteter Suchbaum]]

Das Ergebnis dieses einseitigen Einfügens wäre somit eine [[Liste (Datenstruktur)#Einfach verkettete Listen|einfach verkettete Liste]]; die Vorteile eines Baums wären somit zunichtegemacht

{{Siehe auch|O-Notation|Komplexität (Informatik)|titel2=Komplexität|Erwartungswert}}

== Gegenstrategie: Balance halten ==
Balancierte Bäume wurden entwickelt, um die Entartung zu verhindern und eine Höhe von <math>c\cdot\log(n)</math> zu garantieren.

Dazu verfolgt man unterschiedliche Konzepte. Allen gemeinsam ist: Man fordert spezielle Eigenschaften des Baumes,
* aus denen folgt, dass die Höhe des Baumes in jedem Fall <math>c\cdot\log(n)</math> ist.
* sodass es geeignete Such-, Einfüge- und Löschoperationen (sinnvollerweise der [[Komplexität (Informatik)|Komplexität]] <math>\mathcal{O}(h)</math>) gibt, die die speziellen Eigenschaften wahren.

Man erhält eine solche Operation, indem man die Operation der allgemeinen Suchbäume verwendet und nach jeder Ausführung an der Stelle der Änderung die Balance überprüft, adjustiert und ggf. neu balanciert. Es kann vorkommen, dass sich diese Anpassungs- und Reparatur-Welle bis zur Wurzel hinauf fortsetzt.

=== Höhenbalance ===
Nach der Höhe balancierte Bäume stellen für jeden Knoten sicher, dass die Höhe des linken Unterbaumes und die Höhe des rechten Unterbaumes nur um ein bestimmtes Verhältnis oder eine bestimmte Differenz voneinander abweichen.

Beim [[Rot-Schwarz-Baum]] wird jedem Knoten eine Farbe (Rot oder Schwarz) zugeordnet; der Baum ist bezüglich der schwarzen Knoten optimal höhenbalanciert und der Anteil der roten Knoten ist begrenzt. Diese Bäume stellen eine binäre Realisierung der [[2-3-4-Baum|2-3-4-Bäume]] dar, einer speziellen Variante der [[B-Baum|B-Bäume]].

Im [[AVL-Baum]] gilt für jeden Knoten: Die Höhe seines
linken Kindes weicht von der seines rechten Kindes um höchstens ±1 ab.

=== Balance der Knotenzahl ===
Sei <math>T</math> ein Binärbaum mit linkem Unterbaum <math>T_l</math> und rechtem Unterbaum <math>T_r</math>. Dann heißt
: <math>\rho(T) := \tfrac{|T_l|}{|T|} = 1 - \tfrac{|T_r|}{|T|}</math>
die '''Wurzelbalance''' von <math>T</math>. Dabei bedeutet <math>|T|</math> die Anzahl der [[Binärer Suchbaum#Terminologie|(externen) Blätter]] von <math>T</math>.

Ein Binärbaum wird '''von beschränkter Balance α''' genannt, wenn für jeden Unterbaum <math>T'</math> von <math> T</math> gilt:
: <math>\alpha\le \rho(T') \le 1-\alpha</math> .
Diese Art Binärbäume wurden 1972 von Reingold und Nievergelt<ref>Nievergelt, J. & Reingold, E. M. (1972) Binary search trees of bounded balance. In Proceedings of the Fourth Annual Acm Symposium on Theory of Computing. ACM, pp. 137–142.</ref> eingeführt. In der englischen Literatur heißen sie auch „weight-balanced trees“ (WBTs).<ref name="Hirai">{{cite journal |first1=Y. |last1=Hirai |first2=K. |last2=Yamamoto |year=2011 |title=Balancing weight-balanced trees |journal=J. Functional Programming |volume=21 |issue=3 |pages=287 |doi=10.1017/S0956796811000104 |url=https://yoichihirai.com/bst.pdf |language=en}}</ref>

[[#Mehlhorn|Mehlhorn]] versammelt alle Binärbäume mit beschränkter Balance α in der Menge '''BB(α)''' und beweist auf S. 181:<br />
Sei <math>\tfrac14 < \, \alpha \, \leq 1-\tfrac{\sqrt2}2</math> und ''T'' ein BB(α)-Baum. Dann haben die Operationen ''Suche''(''a'',''T''), ''Einfüge''(''a'',''T''), ''Lösche''(''a'',''T'') jeweils die [[Zeitkomplexität]] <math>\mathcal{\mathcal{O}}(\log |T|)</math>.

=== Gewichtsbalance ===
Unter dem [[Gewicht (Graphentheorie)|Gewicht]] eines Knotens sei hier die Wahrscheinlichkeit des Zugriffs auf ihn verstanden.

Ist der Baum statisch, spielen also Einfüge- oder Löschoperationen keine Rolle, so bietet sich der [[Bellman-Algorithmus]] an, der einen optimalen gewichteten binären Suchbaum konstruiert. Seine Effizienz ist auch dann gegeben, wenn die Gewichte nur ungefähr bekannt sind.

Allerdings kann bei einer [[Gewichteter binärer Suchbaum#Geometrische Verteilung|extremen Verteilung der Zugriffswahrscheinlichkeiten]] auch beim ''optimalen'' gewichteten binären Suchbaum im [[worst case]] eine lineare (nicht mehr logarithmische) Abhängigkeit der Höhe von der Anzahl herauskommen.

Sind Einfüge- oder Entfernoperationen wichtig, so sind im Prinzip auch die Gewichte zu pflegen. Im Grenzfall sogar beim Aufsuchen, da sich hierbei zumindest die Zugriffsstatistik ändert.

Dies und noch mehr leisten die [[Splay-Baum|Splay-Bäume]].

== Siehe auch ==
* [[Gewichteter binärer Suchbaum]]
* [[Bellman-Algorithmus]] (Konstruktion des optimalen gewichteten binären Suchbaums)
* [[Splay-Baum]]

== Einzelnachweise ==
<references />

== Literatur ==
* {{Anker|Mehlhorn}}[[Kurt Mehlhorn]] ''Datenstrukturen und effiziente Algorithmen'' Teubner Stuttgart 1988, ISBN 3-519-12255-3.

[[Kategorie:Suchbaum]]

Balancierter Baum - Versionsgeschichte

imported>Ulanwp: Fehlenden Sprachparameter eingefügt