Balancierter Baum

Grundidee und Nutzen

Ein balancierter Baum ist in der Informatik ein Baum, der eine maximale Höhe von c · log(n) garantiert. Dabei ist n die Anzahl der Elemente im Baum und c eine Konstante, die nicht von n abhängt. Manche Autoren zählen auch Datenstrukturen dazu, die sicherstellen, dass die mittlere Höhe oder die mittlere Pfadlänge bei jedem Baum logarithmisch bleibt.

Balancierte Bäume sind besonders wichtig bei Suchbäumen. In einem Suchbaum hängen die wichtigsten Operationen, nämlich Suchen, Einfügen und Löschen eines Wertes, im schlechtesten Fall linear von der Höhe h des Baumes ab. Ihre Komplexität ist also O(h). Wenn die Höhe logarithmisch in der Anzahl der Elemente bleibt, können diese Operationen effizient bleiben.

Problem der Entartung

Jeder k-näre Baum mit n Knoten hat mindestens die Höhe h ≥ log_k(n + 1). Im Durchschnitt liegt die Höhe immer noch bei c · log_k n für eine konstante Zahl c. Daher haben Operationen auf einem Baum mindestens die Komplexität O(log_k n) = O(log n).

Das Problem entsteht, wenn ein Suchbaum ungleichmäßig wächst. Fügt man zum Beispiel eine große Menge bereits sortierter Daten in einen Suchbaum ein, kann der Baum im Extremfall die Höhe n erreichen. Dann haben auch spätere Einfüge-, Such- und Löschoperationen die Komplexität O(n). Ein solcher Baum ist praktisch zu einer einfach verketteten Liste entartet; damit gehen die Vorteile der Baumstruktur verloren.

Balance als Gegenstrategie

Balancierte Bäume wurden entwickelt, um diese Entartung zu verhindern. Sie garantieren eine Höhe von c · log(n). Dafür verlangt man besondere Eigenschaften des Baumes, aus denen folgt, dass die Höhe in jedem Fall logarithmisch bleibt.

Gleichzeitig müssen geeignete Such-, Einfüge- und Löschoperationen existieren, die diese Eigenschaften erhalten. Sinnvollerweise haben diese Operationen eine Komplexität von O(h), also abhängig von der Höhe des Baumes. Typisch ist, dass man zunächst die Operation eines allgemeinen Suchbaums ausführt und danach an der veränderten Stelle die Balance überprüft, anpasst und den Baum bei Bedarf neu balanciert. Diese Anpassungs- und Reparatur-Welle kann sich bis zur Wurzel fortsetzen.

Höhenbalance

Bei nach Höhe balancierten Bäumen wird für jeden Knoten kontrolliert, wie stark sich die Höhen des linken und rechten Unterbaums unterscheiden dürfen. Die Abweichung kann durch ein bestimmtes Verhältnis oder durch eine bestimmte Differenz begrenzt sein.

Ein Beispiel ist der Rot-Schwarz-Baum. Dort erhält jeder Knoten eine Farbe, Rot oder Schwarz. Der Baum ist bezüglich der schwarzen Knoten optimal höhenbalanciert, und der Anteil der roten Knoten ist begrenzt. Rot-Schwarz-Bäume sind eine binäre Realisierung der 2-3-4-Bäume, einer speziellen Variante der B-Bäume.

Ein weiteres Beispiel ist der AVL-Baum. In einem AVL-Baum gilt für jeden Knoten: Die Höhe seines linken Kindes weicht von der Höhe seines rechten Kindes um höchstens ±1 ab.

Balance der Knotenzahl

Bei der Balance der Knotenzahl betrachtet man, wie viele Blätter in den Unterbäumen liegen. Sei T ein Binärbaum mit linkem Unterbaum T_l und rechtem Unterbaum T_r. Dann heißt ρ(T) := |T_l| / |T| = 1 − |T_r| / |T| die Wurzelbalance von T. Dabei bezeichnet |T| die Anzahl der externen Blätter von T.

Ein Binärbaum heißt von beschränkter Balance α, wenn für jeden Unterbaum T' von T gilt: α ≤ ρ(T') ≤ 1 − α. Solche Binärbäume wurden 1972 von Reingold und Nievergelt eingeführt. In der englischen Literatur heißen sie auch „weight-balanced trees“ (WBTs).

Mehlhorn fasst alle Binärbäume mit beschränkter Balance α in der Menge BB(α) zusammen. Er beweist: Ist 1/4 < α ≤ 1 − √2/2 und T ein BB(α)-Baum, dann haben die Operationen Suche(a,T), Einfüge(a,T) und Lösche(a,T) jeweils die Zeitkomplexität O(log |T|).

Gewichtsbalance

Bei der Gewichtsbalance bedeutet das Gewicht eines Knotens die Wahrscheinlichkeit, mit der auf ihn zugegriffen wird. Wenn der Baum statisch ist, also Einfüge- und Löschoperationen keine Rolle spielen, kann der Bellman-Algorithmus verwendet werden. Er konstruiert einen optimalen gewichteten binären Suchbaum. Seine Effizienz bleibt auch dann erhalten, wenn die Gewichte nur ungefähr bekannt sind.

Bei einer extremen Verteilung der Zugriffswahrscheinlichkeiten kann allerdings selbst beim optimalen gewichteten binären Suchbaum im schlechtesten Fall eine lineare, also nicht mehr logarithmische, Abhängigkeit der Höhe von der Anzahl entstehen.

Wenn Einfüge- oder Entfernoperationen wichtig sind, müssen grundsätzlich auch die Gewichte gepflegt werden. Im Grenzfall betrifft das sogar das Aufsuchen, weil sich dabei zumindest die Zugriffsstatistik ändert. Diese Anforderungen und mehr leisten Splay-Bäume.