Referat AVL-BAUME - Das Balancefeld eines AVL

AVL-BAUME

Ein binärer Baum heißt ausgeglichener Baum oder AVL-Baum (benannt nach seinen 'Erfindern' Adelson-Velskij und Landis), falls sich die Höhen der beiden Teilbäume um höchstens 1 unterscheiden.

Jeder Knoten eines Baumes setzt sich aus vier Informationen zusammen:

Pointer auf den linken Sohn

Pointer auf den rechten Sohn

Balancefeld

Datenfeld

Das Balancefeld eines AVL-Knotens kann die Tiefendifferenz mit zwei Bits anzeigen:

+1 der rechte Sohn ist tiefer (unbalancierter Knoten)

0 gleiche Tiefe (balancierter Knoten)

-1 der linke Sohn ist tiefer (unbalancierter Knoten)

Wird ein neuer Knoten eingefügt, sind drei Fälle zu unterscheiden:

Die Tiefen von links und rechts werden verschieden, aber das Kriterium der Ausgeglichenheit wird nicht verletzt.

Die Tiefen von links und rechts werden gleich.

Die Ausgeglichenheit wird zerstört, und der Baum muß umstrukturiert werden

Der Prozeß des Einfügens und des Löschens ist grundsätzlich gleich dem Einfügen und Löschen bei 'normalen' binären Bäumen. Es muß jedoch nach jedem Einfügen bzw. Löschen eines Knotens darauf geachtet werden ob die Balance in dem erlaubten Rahmen ist (-1,0,+1).

Um den AVL-Baum gegebenenfalls wieder in Balance bringen zu können, muß eine 'Rotation' durchgeführt werden (Links-/Rechtsrotation).

Beispiel zum Einfügen von Elementen in AVL-Bäume:

Es werden folgende Elemente eingefügt:

4 5 7 2 1 3 6

Einfügen der Zahl 4:

Einfügen der Zahl 5:

Einfügen der Zahl 7:

Einfügen der Zahl 2:

Einfügen der Zahl 1:

Einfügen der Zahl 3:

Einfügen der Zahl 6: