Baumbalancierung: AVL-Bäume

4.1 Probleme unbalancierter Bäume

Bei normalen (unbalancierten) Bäumen können beim Hinzufügen von Elementen unangenehme Effekte auftreten.

1. Erhöhung der Baumhöhe:

In unbalancierten Bäumen kann die Höhe n (wobei n die Anzahl der Knoten ist) erreichen, was zu einer Verschlechterung der Leistung führt.

Die Ausführungszeit der grundlegenden Operationen (Suche, Einfügen, Löschen) wird im schlimmsten Fall O(n).

2. Ungleichmäßige Verteilung der Knoten:

In unbalancierten Bäumen können einige Teilbäume deutlich mehr Knoten enthalten als andere, was zu einer ineffizienten Speichernutzung und einer längeren Verarbeitungszeit führt.

3. Verschlechterung der Ausführungszeit der Operationen:

In unbalancierten Bäumen erfordern die Such-, Einfüge- und Löschvorgänge mehr Zeit aufgrund der erhöhten Baumhöhe.

Beispiel eines unbalancierten Baumes:

In diesem Beispiel verwandelt sich der Baum tatsächlich in eine verknüpfte Liste, und die Ausführungszeit der Operationen wird linear.

4.2 Definition eines AVL-Baumes und seine Eigenschaften

Ein AVL-Baum (benannt nach seinen Erfindern Adelson-Velsky und Landis) ist eine Art balancierter binärer Suchbaum, bei dem für jeden Knoten der Höhenunterschied seiner linken und rechten Teilbäume nicht mehr als 1 beträgt.

Eigenschaften eines AVL-Baumes:

1. Balancierung:

Der Höhenunterschied zwischen dem linken und dem rechten Teilbaum eines Knotens beträgt nicht mehr als 1.

Dies gewährleistet eine Baumhöhe von O(log n), wobei n die Anzahl der Knoten ist, was eine effiziente Ausführung von Such-, Einfüge- und Löschoperationen garantiert.

2. Binärer Suchbaum:

Ein AVL-Baum hat alle Eigenschaften eines binären Suchbaumes: Für jeden Knoten sind alle Schlüssel im linken Teilbaum kleiner als der Schlüssel des Knotens, und alle Schlüssel im rechten Teilbaum sind größer als der Schlüssel des Knotens.

3. Automatische Balancierung:

Nach jeder Einfüge- oder Löschoperation wird der Baum balanciert, um seine Eigenschaften zu erhalten.

4.3 Beispiele für die Balancierung von Bäumen

Rotationen sind Operationen, die durchgeführt werden, um das Gleichgewicht in einem AVL-Baum nach dem Einfügen oder Löschen von Knoten wiederherzustellen. Es gibt vier Arten von Rotationen: links, rechts, links-rechts und rechts-links.

1. Linksdrehung (Left Rotation):

Bei der Linksdrehung wird der Knoten x nach oben verschoben und sein rechter Kindknoten y wird sein Elternknoten. Der linke Teilbaum von y wird zum rechten Teilbaum von x.

2. Rechtsdrehung (Right Rotation):

Bei der Rechtsdrehung wird der Knoten x nach oben verschoben und sein linker Kindknoten y wird sein Elternknoten. Der rechte Teilbaum von y wird zum linken Teilbaum von x.

3. Links-Rechts-Drehung (Left-Right Rotation):

Zuerst wird eine Linksdrehung am linken Kindknoten durchgeführt und dann eine Rechtsdrehung am Knoten selbst.

4. Rechts-Links-Drehung (Right-Left Rotation):

Zuerst wird eine Rechtsdrehung am rechten Kindknoten durchgeführt und dann eine Linksdrehung am Knoten selbst.

4.4 Grundlegende Operationen in AVL-Bäumen

Die grundlegenden Operationen in AVL-Bäumen umfassen Einfügen, Löschen und Suchen.

Einfügen (Insertion)

Ein neuer Knoten muss in den AVL-Baum eingefügt und, falls erforderlich, balanciert werden.

Schritte:

1. Einfügen des Knotens:
   • Beginne mit der Wurzel des Baumes und finde rekursiv den richtigen Platz für den neuen Knoten, indem du seinen Wert mit den aktuellen Knoten vergleichst.
   • Füge den neuen Knoten an der gefundenen Stelle ein, wie in einem normalen binären Suchbaum.
2. Aktualisieren der Höhen:
   • Nach dem Einfügen aktualisiere die Höhen aller Knoten auf dem Weg vom neuen Knoten zur Wurzel.
3. Balancierung des Baumes:
   • Überprüfe das Gleichgewicht jedes Knotens auf dem Weg vom neuen Knoten zur Wurzel.
   • Wenn das Gleichgewicht eines Knotens gestört ist (der Höhenunterschied zwischen dem linken und rechten Teilbaum größer als 1 ist), führe die entsprechende Drehung durch, um das Gleichgewicht wiederherzustellen.

Beispiel:

2. Löschen (Deletion)

Ein Knoten muss aus dem AVL-Baum entfernt und, falls erforderlich, balanciert werden.

Schritte:

1. Suche und Löschung des Knotens:

• Beginne mit der Wurzel des Baumes und finde rekursiv den zu löschenden Knoten.
• Entferne den Knoten wie in einem normalen binären Suchbaum:
• Wenn der Knoten ein Blatt ist, entferne ihn einfach.
• Wenn der Knoten einen Nachkommen hat, ersetze den Knoten durch seinen Nachkommen.
• Wenn der Knoten zwei Nachkommen hat, finde den kleinsten Knoten im rechten Teilbaum (oder den größten im linken), kopiere seinen Wert in den zu entfernenden Knoten und entferne rekursiv den kleinsten Knoten im rechten Teilbaum.

2. Aktualisieren der Höhen:

• Nach dem Löschen aktualisiere die Höhen aller Knoten auf dem Weg vom entfernten Knoten zur Wurzel.

3. Balancierung des Baumes:

• Überprüfe das Gleichgewicht jedes Knotens auf dem Weg vom entfernten Knoten zur Wurzel.
• Wenn das Gleichgewicht eines Knotens gestört ist, führe die entsprechende Drehung durch, um das Gleichgewicht wiederherzustellen.

Beispiel:

3. Suche (Search)

Ein Knoten mit einem bestimmten Wert muss in einem AVL-Baum gefunden werden.

Schritte:

1. Rekursive Suche:

• Beginne mit der Wurzel des Baumes und vergleiche rekursiv den gesuchten Wert mit den aktuellen Knoten.
• Wenn der Wert kleiner als der aktuelle Knoten ist, gehe zum linken Teilbaum.
• Wenn der Wert größer als der aktuelle Knoten ist, gehe zum rechten Teilbaum.
• Wenn der Wert mit dem aktuellen Knoten übereinstimmt, gib diesen Knoten zurück.

Beispiel: