Notizen

AVL-Bäume

tagsdatenstrukturen, algorithmen

Ein binär verketteter Suchbaum heißt AVL-Baum, wenn für jeden Knoten gilt, dass sich die Höhen des linken und rechen Teilbaums um maximal 1 unterscheiden:

AVL-Eigenschaft (AVL-Balancierung):
Knoten linker Teilbaum von rechter Teilbaum von

Balance

Die Balance ist der Betrag der Höhendifferenz zwischen dem rechten Teilbaum und dem linken Teilbaum. Existiert ein Teilbaum nicht, wird verwendet.

Beispiel

graph TB
1[-1]
2[1]
4[1]
6[0]
5[0]
3[-1]
7[1]
8[-1]
11[-1]
9[0]
10[0]
12[0]
1-->2 & 3
2-->4 & 5
4-->6
3-->7 & 8
7-->9
8-->10 & 11
11-->12

Höhe von AVL-Bäumen

Sei ein AVL-Baum mit Knoten, dann gilt:

Operationen und Laufzeiten

Suche

  • Die Laufzeit der Suche lässt sich aus der Maximalhöhe ableiten
  • BC
  • WC/Misserfolg/AC

Einfügen

  • Schafft man es, beim Einfügen und Löschen die AVL-Eigenschaft in konstanter Zeit wiederherzustellen, reduziert sich die Laufzeit hier auch auf die Suche
  • Idee:
    • Die Höhe des jeweiligen Teilbaums wird in den Knoten gespeichert
    • Höhen werden beim Einfügen bzw. löschen aktualisiert
    • Die AVL-Eigenschaft wird an allen Knoten bis zur Wurzel überprüft
    • Ggf. durch Rotationen wiederhergestellt

Löschen

Das Löschen erfolgt fast gleich wie bei normalen Binärbäumen mit einem Sonderfall: Der zu löschende Knoten hat 2 Nachfolger. Dann wird wie folgt verfahren:

  • Tauschen des zu löschenden Elements mit dem In-order-Nachfolger
  • Der Knoten ist an seiner neuen Position zu löschen (erneut den Algorithmus aufrufen)

Rotationen

Rotationen werden an einem Knoten durchgeführt, wenn bei ihm die AVL-Eigenschaft verletzt ist.

Ist der……linkte Teilbaum zu hoch und……rechte Teilbaum zu hoch und…
…davon der rechte Teilbaum höher:Links-Rechts-RotationLinks-Rotation
…davon der linke Teilbaum höher:Rechts-RotationRechts-Links-Rotation

Einfachrotationen

Einfachrotationen werden durchgeführt, wenn der äußere Teilbaum zu hoch ist.

Beispiel einer Links-Rotation am Element 2:

graph TB
2-->1 & 4
4-.->3
4-->5
5-->...

Das innere Kindelement wird umgehängt:

graph TB
4-->2 & 5
2-->1
2==>3
5-->...

Rechts-Rotation

Beispiel einer Rechts-Rotation am Element 4:

graph TB
4-->2 & 5
2-->1
2-.->3
1-->...

Das innere Kindelement wird umgehängt:

graph TB
2-->1 & 4
4==>3
4-->5
1-->...

Doppelrotationen

Doppelrotationen werden durchgeführt, wenn der innere Teilbaum zu hoch ist. Sie bestehen aus zwei Einfachrotationen, was auch algorithmisch so umsetzbar ist.

Doppelrotationen rotieren zuerst einen Teilbaum, dann sich selbst.

Beispiel einer Rechts-Links-Rotation am Element 2:

graph TB
2-->1 & 5
5-->4 & 6
4-->...

Es erfolgt eine Rechts-Rotation am rechten Teilbaum mit anschließender Links-Rotation am Element:

graph TB
4-->2 & 5
5-->6
2-->1 & ...

Beispiel einer Rechts-Links-Rotation am Element 2:

graph TB
5-->6
5-->2
2-->1 & 3
3-->...

Es erfolgt eine Links-Rotation am rechten Teilbaum mit anschließender Rechts-Rotation am Element:

graph TB
3-->2 & 5
2-->1
5-->... & 6

Backlinks