DE 
English
Українська
Polski🌳 AVL-Baum — Selbstbalancierende Rotationen
Fügen Sie Schlüssel in einen AVL-Baum ein und löschen Sie sie, während sich die Balance-Faktoren nach jeder Änderung aktualisieren. Kippt ein Teilbaum über ±1, stellen einfache und doppelte Rotationen die Höhenbalance automatisch wieder her.
Über diese Simulation
Ein AVL-Baum, benannt nach seinen Erfindern Georgy Adelson-Velsky und Evgenii Landis (1962), ist der früheste selbstbalancierende binäre Suchbaum. Jeder Knoten speichert einen Balance-Faktor gleich der Höhe seines linken Teilbaums minus der Höhe seines rechten Teilbaums, und der Baum hält die Invariante ein, dass dieser Wert stets im Bereich {−1, 0, 1} bleibt.
Häufig gestellte Fragen
Warum muss der Balance-Faktor im Bereich {−1, 0, 1} bleiben?
Dieser Bereich ist genau die Schwelle, die die Baumhöhe nachweislich bei O(log n) hält. Adelson-Velsky und Landis bewiesen, dass ein Baum, der diese Invariante einhält, eine Höhe von höchstens etwa 1,44·log₂(n+2) hat, sodass Balance-Faktoren von ±1 genug Flexibilität für effiziente Einfügungen bei garantiert logarithmischer Höhe bieten.
Was ist der Unterschied zwischen einer einfachen und einer doppelten Rotation?
Eine einfache Rotation (LL- oder RR-Fall) behebt eine Unbalance, die durch einen Teilbaum verursacht wird, der auf derselben Seite wie sein eigenes schweres Kind schwer ist — eine Zeigerumschreibung genügt. Eine doppelte Rotation (LR- oder RL-Fall) behandelt eine 'Zickzack'-Unbalance, bei der das schwere Kind zur entgegengesetzten Seite neigt, und erfordert zwei Rotationen: zuerst am Kind, um es in einen einfachen Rotationsfall umzuwandeln, dann am Knoten selbst.
Wie vergleicht sich ein AVL-Baum mit einem Rot-Schwarz-Baum?
Beide garantieren eine Höhe von O(log n), aber AVL-Bäume erzwingen eine strengere Balance-Invariante, was zu kürzeren Bäumen und schnellerer Suche führt. Rot-Schwarz-Bäume lockern die Balance-Bedingung (der längste Wurzel-zu-Blatt-Pfad darf bis zu doppelt so lang sein wie der kürzeste), was weniger Rotationen beim Einfügen und Löschen bedeutet. Das macht AVL-Bäume vorteilhaft für lesehäufige und Rot-Schwarz-Bäume für schreibhäufige Arbeitslasten.
Warum kann das Löschen Rotationen auf jeder Ebene bis zur Wurzel erfordern, im Gegensatz zum Einfügen?
Eine Einfügung fügt nur einem Teilbaum Höhe hinzu, sodass höchstens eine Rotation (einfach oder doppelt) nötig ist, um die Balance wiederherzustellen; danach ist die Höhe des Teilbaums wie vor der Einfügung. Ein Löschen kann die Höhe eines Teilbaums verringern, und diese Verringerung kann sich nach oben fortpflanzen und potenziell eine Rebalancierungsrotation bei jedem Vorfahren auf dem Pfad zur Wurzel auslösen — im schlimmsten Fall bis zu O(log n) Rotationen.