1. Welt
  2. Quests
  3. #1501
Alexander Fufaev

AVL-Baum erstellen

aus dem Bereich: Quests

Deine Aufgabe ist...

Konstruiere aus dem folgenden Key-Array einen AVL-Baum:

[72, 100, 80, 44, 11, 59, 6, 19, 62, 14]

Allgemeine 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 anzeigen

Folgende Illustration stellt einen fertigen AVL-Baum dar.

AVL-Baum (Binärer Suchbaum) mit 10 Knoten Speichern | Info
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.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 1
Gäste online: 1
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.