AVL-Bäume

Beschreibung / Inhalt
Das Dokument behandelt das Thema AVL-Bäume, auch bekannt als ausgeglichene Bäume. Diese sind binäre Bäume, bei denen die Höhen der beiden Teilbäume um höchstens 1 unterscheiden. Jeder Knoten eines AVL-Baums setzt sich aus vier Informationen zusammen: Pointer auf den linken und rechten Sohn, Balancefeld und Datenfeld. Das Balancefeld kann die Tiefendifferenz mit zwei Bits anzeigen, +1 für einen tieferen rechten Sohn, -1 für einen tieferen linken Sohn und 0 für gleiche Tiefe. Beim Einfügen eines neuen Knotens müssen drei Fälle unterschieden werden: Tiefen von links und rechts unterscheiden sich, Tiefen sind gleich und Ausgeglichenheit wird zerstört. Durch Rotation (Links-/Rechtsrotation) wird der AVL-Baum wieder in Balance gebracht. Das Einfügen von Zahlen in einen AVL-Baum wird anhand eines Beispiels verdeutlicht. Nach jedem Einfügen oder Löschen eines Knotens muss auf die Balance im erlaubten Rahmen (-1,0,+1) geachtet werden.
Direkt das Referat aufrufen

Auszug aus Referat
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 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 ...
Direkt das Referat aufrufen