AVL-Bäume

AVL - BÄUME

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:

1. Die Tiefen von links und rechts werden verschieden, aber das Kriterium der Ausgeglichenheit wird nicht verletzt.
2. Die Tiefen von links und rechts werden gleich.
3. Die Ausgeglichenheit wird zerstört, und der Baum muss 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 muss 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, muss 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:

258 Worte in "deutsch"  als "hilfreich"  bewertet