Level 3
Aufgabe mit Lösung AVL-Baum erstellen
Konstruiere aus dem folgenden Key-Array einen AVL-Baum:
[72, 100, 80, 44, 11, 59, 6, 19, 62, 14]
Lösungstipps
Füge die Knoten nacheinander in den Baum und prüfe, ob der Balance-Faktor für jeden Knoten erfüllt ist. Wenn nicht, rotiere die Knoten mittels L-, R-, RL- oder LR-Rotation.
Lösungen
Lösung
Folgende Illustration stellt einen fertigen AVL-Baum dar.
Zuerst wird ein Knoten mit Key 72 erzeugt. Dann wird Key 100 in den rechten Teilbaum eingefügt, da 100 > 72 (siehe Eigenschaft eines Suchbaums). Die AVL-Eigenschaft, dass der Balance-Faktor \(b_v\) für jeden Knoten \(v\) betragsmäßig höchstens 1 ist, ist nicht verletzt: \(b_{72} = 1 - 0 = 1\). (Für Blätter gilt stets, dass der Balance-Faktor 0 ist, also hier \(b_{100} = 0\)).
Dann wird ein Knoten mit dem Key 80 eingefügt. Die AVL-Eigenschaft ist verletzt, denn \(b_{72} = 2 - 0 = 2 \) ist größer als 1. Führe RL-Rotation aus.
Füge 44 ein. AVL-Eigenschaft ist für alle Knoten erfüllt: \(b_{80} = 1 - 2 = -1\), \(b_{72} = 0 - 1 = -1\).
Key 11 einfügen. AVL-Eigenschaft verletzt, denn \(b_{72} = 0 - 2 = -2\) größer als 1. Führe R-Rotation von 72 aus.
Key 59 einfügen. Wieder ist die AVL-Eigenschaft verletzt: \(b_{80} = 1 - 3 = -2\). Führe LR-Rotation aus.
Füge 6 ein. Füge 19 ein. Füge 62 ein.
Füge 14 ein. Jetzt ist die AVL-Eigenschaft verletzt: \(b_{72} = 2 - 4 = -2\). Führe R-Rotation aus.
Alle Keys wurden in einen AVL-Baum hinzugefügt. Fertig.