1. Welt
  2. Illustrationen
  3. #1505
Alexander Fufaev

LR-Rotation (AVL-Baum)

aus dem Bereich: Illustrationen
LR-Rotation (AVL-Baum)
Will haben!Illustration mit Copyright (JPG)Vektorgrafik (SVG)

Ein AVL-Baum ist ein binärer Suchbaum, bei dem für jeden Knoten \(v\) die Höhen seiner Teilbäume maximal um 1 unterscheiden. Das heißt für den Balance-Faktor gilt stets: \(b_{v} \in \{-1,0,1\}\).

Gibt es einen Knoten, bei dem der Balance-Faktor nicht zwischen -1 und 1 liegt, dann muss der Baum "rebalanciert", um diesen zu einem AVL-Baum zu machen. In der Illustration rechts oben wird die AVL-Eigenschaft vom Knoten A verletzt: \(b_A = 2 - 0 = 2\). Um die AVL-Eigenschaft wiederherzustellen, wird LR-Rotation ausgeführt. Diese wird immer dann ausgeführt, wenn der linke Teilbaum von A einen Überhang mit einem "Knick" hat. Dazu wird zuerst, wie an einem Faden, am Knoten B nach links "gezogen" (L-Rotation), sodass sich dadurch ein Baum wie in der Illustration links oben ergibt. Anschließend wird am Knoten A nach rechts "gezogen" (R-Rotation), sodass sich dadurch ein Baum wie in der Illustration unten ergibt. Insgesamt wurde eine LR-Rotation durchgeführt.

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 7
Gäste online: 7
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.