Direkt zum Inhalt
  1. Startort
  2. Quests
  3. 📖
Level 3
Level 3 setzt die Grundlagen der Vektorrechnung, Differential- und Integralrechnung voraus. Geeignet für Studenten und zum Teil Abiturienten.

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.

AVL-Baum

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.

Details zum Inhalt
  • Die Quest wurde hinzugefügt von FufaeV am .
  • Die Quest wurde aktualisiert von FufaeV am .