Direkt zum Inhalt
  1. Startseite
  2. Quests
  3. #339

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ösung

Lösung anzeigen

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 .

Feedback geben

Hey! Ich bin Alexander FufaeV, der Physiker und Autor hier. Es ist mir wichtig, dass du stets sehr zufrieden bist, wenn du hierher kommst, um deine Fragen und Probleme zu klären. Da ich aber keine Glaskugel besitze, bin ich auf dein Feedback angewiesen. So kann ich Fehler beseitigen und diesen Inhalt verbessern, damit auch andere Besucher von deinem Feedback profitieren können.

Wie zufrieden bist Du?