Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Ein binärer Suchbaum kann im Worst Case zu einer Liste degenerieren — statt ! AVL-Bäume verhindern das durch automatische Balance nach jeder Einfügung und Löschung. Klausur-Pflicht in 11/17 WInf-Algo-Klausuren (oft mit Rotation-Aufgaben).
Klausur-Tipp: Bei AVL-Aufgaben IMMER nach jedem Insert den Balance-Faktor jedes betroffenen Knotens berechnen, von der eingefügten Position aufwärts. Erste Verletzung → Rotation. Höhen-Update nach Rotation.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Ein binärer Suchbaum kann im Worst Case zu einer Liste degenerieren — O(n) statt O(log n)! AVL-Bäume verhindern das durch automatische Balance nach jeder Einfügung und Löschung. Klausur-Pflicht in 11/17 WInf-Algo-Klausuren (oft mit Rotation-Aufgaben).
AVL-Baum: Ein binärer Suchbaum, in dem für JEDEN Knoten die Höhen seiner Teilbäume sich um höchstens 1 unterscheiden. Bei Verletzung: Rotation wiederherstellen.
Im Worst Case entartet ein BST zu einer Liste (z.B. wenn man 1, 2, 3, 4, 5 in Reihenfolge einfügt):
1 Höhe = n-1
\ Suche = O(n) ← schlecht!
2
\
3
\
4
\
5
Mit AVL bleibt der Baum balanciert:
≤ 1.44 log₂(n + 2) — also O(log n)O(log n) garantiertFür jeden Knoten:
BF(v) = h(linkes Teilbaum) - h(rechtes Teilbaum)
AVL-Eigenschaft: |BF(v)| ≤ 1 für alle v.
Links-lastig (BF=+2), Verletzung in linkem Teilbaum:
z y
/ \ / \
y T4 Rotate-Right x z
/ \ ────────────► / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
Algorithmus: y wird neue Wurzel, z wird rechter Kind von y, T3 (alter rechter Kind von y) wird linker Kind von z.
Spiegelbildlich. Rechts-lastig (BF=-2), Verletzung in rechtem Teilbaum.
Links-lastig, aber Verletzung in RECHTEM Teilbaum von linkem Kind:
Spiegelbild von LR.
| Fall | BF(Wurzel) | BF(Kind) | Aktion |
|---|---|---|---|
| LL | +2 | +1 (oder 0) | Single Right Rotation |
| RR | -2 | -1 (oder 0) | Single Left Rotation |
| LR | +2 | -1 | Left-Right Double Rotation |
| RL | -2 | +1 | Right-Left Double Rotation |
Klausur-Trick: Welche Rotation? Schaue auf das Vorzeichen-Paar (Wurzel-BF, Kind-BF). Beide gleich → Single. Verschieden → Double.
avl_insert(node, value):
1. Normaler BST-Insert
2. Aktualisiere Höhen aufwärts
3. Berechne Balance-Faktor
4. Bei Verletzung: passende Rotation anwenden
5. Wiederhole bis zur Wurzel
Wichtig: Bei AVL-Insert ist höchstens EINE Rotation nötig — nach erster Rotation ist Höhe wiederhergestellt.
Komplizierter: nach Löschung können mehrere Rotationen auf dem Pfad zur Wurzel nötig sein. O(log n) Rotationen im Worst Case.
| Baumtyp | Balance-Eigenschaft | Praxis |
|---|---|---|
| AVL | ` | BF |
| Rot-Schwarz-Baum | spezielle Färbung mit Regeln | etwas lockerer, weniger Rotationen → schnelleres Insert/Delete |
| B-Bäume | mehr als 2 Kinder pro Knoten | Datenbank-Indizes, Filesystem |
| Splay-Trees | self-adjusting (zuletzt-genutzt nach oben) | Cache-freundlich |
In der Praxis (Java TreeMap, C++ std::map) wird oft Rot-Schwarz-Baum statt AVL verwendet — etwas weniger streng balanciert, aber weniger Rotationen.
| Operation | Average | Worst |
|---|---|---|
| Search | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) |
| Rotation | O(1) | O(1) |
Alle Standard-Operationen sind O(log n) — garantiert, nicht nur "average".
1. AVL-Eigenschaft: |BF| ≤ 1 für alle Knoten. BF = h(links) − h(rechts).
2. 4 Rotation-Fälle: LL, RR, LR, RL. Erste 2 = Single, letzte 2 = Double.
3. Welche Rotation? Schaue auf Vorzeichen-Paar (Wurzel-BF, Kind-BF). Gleich → Single. Verschieden → Double.
4. Insert: max. 1 Rotation. Delete: bis zu O(log n) Rotationen.
5. Alle Operationen O(log n) garantiert.
1. Balance-Faktor falsch herum. BF = h(links) − h(rechts), NICHT umgekehrt. Bei einigen Lehrbüchern variiert das — auf Konvention achten.
2. Rotation-Richtung verwechseln. Bei Single-Right-Rotation rotiert die LINKE Kante NACH OBEN. Visualisierung üben.
3. Höhen nicht aktualisieren. Nach Insert/Rotation MUSS die Höhe jedes betroffenen Knotens neu berechnet werden — von unten nach oben.
4. Double-Rotation als 2 separate Rotationen vergessen. LR ist EINE Operation, die intern aus 2 Rotationen besteht. Reihenfolge ist FEST.
5. AVL mit BST verwechseln. AVL IST ein BST mit Zusatz-Bedingung. BST allein kann zu Liste entarten.
Geh durch jede der 4 Rotation-Fälle (LL, RR, LR, RL) Schritt für Schritt. Du siehst:
Vergleich: Single-Rotation (1 Operation) vs. Double-Rotation (2 Operationen).
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei AVL-Aufgaben IMMER nach jedem Insert den Balance-Faktor jedes betroffenen Knotens berechnen, von der eingefügten Position aufwärts. Erste Verletzung → Rotation. Höhen-Update nach Rotation.
6 Aufgaben zu AVL-Eigenschaft, Rotation-Typen, Balance-Faktor.
Klausurfragen mit Lösungen (6)
Antwort: Für jeden Knoten gilt: |Höhe(links) − Höhe(rechts)| ≤ 1
Erklärung: AVL-Eigenschaft: Balance-Faktor jedes Knotens ist ±1 oder 0. Garantiert Baum-Höhe O(log n). Bei Verletzung (BF = ±2): Rotation.
Antwort: Single Right Rotation (LL-Fall)
Erklärung: LL-Fall: links-lastig + linkes Kind auch links-lastig (oder ausgeglichen). Single Right Rotation reicht. Vorzeichen-Paar (+, +) → Single.
Antwort: Wahr
Erklärung: RICHTIG. AVL hält den Baum balanciert (Höhe ≤ 1.44 log₂(n+2)). Damit sind alle Standard-Operationen O(log n) GARANTIERT, nicht nur average. Bei normalen BSTs gibt's keine Garantie.
Typ: Wahr/Falsch
Antwort: Wenn die Verzweigung in Wurzel und betroffenem Kind unterschiedliche Richtungen hat
Erklärung: Double-Rotation, wenn Vorzeichen von BF(Wurzel) und BF(Kind) UNTERSCHIEDLICH sind. Beispiel: BF(Wurzel)=+2 und BF(linkes Kind)=−1 → LR-Fall (Left-Right Double Rotation).
Richtige Antworten: Es gibt 4 Rotation-Fälle (LL, RR, LR, RL); Rotation ist O(1); Nach Insert sind maximal 1 Rotation nötig; Höhe ist O(log n)
Erklärung: Richtig: 4 Fälle, Rotation O(1), max. 1 Rotation pro Insert, Höhe O(log n). Falsch: Es gibt viele balancierte BSTs (Rot-Schwarz, B-Bäume, Splay); AVL und Rot-Schwarz sind verwandt aber NICHT dasselbe.
Typ: Multi-Select
Zuordnungen:
Erklärung: 4 Rotation-Fälle. Erste 2 = Single (gleiche Vorzeichen), letzte 2 = Double (unterschiedliche Vorzeichen).
Typ: Zuordnung
Klausurfragen mit Lösungen (6)
Antwort: 5 (Toleranz ±1)
Erklärung: AVL-Höhe ≤ 1.44 · log₂(n+2) = 1.44 · log₂(17) ≈ 1.44 · 4.09 ≈ 5.9 → max. 5 oder 6. Realistisch: 4-5 für n=15.
Typ: Zahlen-Eingabe
Antwort: Falsch
Erklärung: FALSCH. Bei Insert reicht max. 1 Rotation, bei DELETE können bis zu O(log n) Rotationen auf dem Pfad zur Wurzel nötig sein. Wichtiger Unterschied!
Typ: Wahr/Falsch
Antwort: Nach Einfügen von 30 ist Wurzel-BF=−2, RR-Fall → Single Left Rotation, Wurzel wird 20
Erklärung: Nach 10: einzelne Wurzel. Nach 20: 10 hat rechtes Kind 20. Nach 30: 20 hätte rechtes Kind 30, also wird 10 BF=−2, 20 BF=−1 → RR-Fall → Single Left Rotation → neue Wurzel 20 mit Kindern 10 und 30.
Antwort: Rot-Schwarz-Baum
Erklärung: Java's TreeMap (und C++ std::map) nutzen Rot-Schwarz-Bäume — etwas weniger streng balanciert als AVL, dafür weniger Rotationen → schnellere Inserts/Deletes in der Praxis.
Lösungen pro Lücke:
Erklärung: AVL-Vokabular. Binärer Suchbaum, |BF|≤1, Rotation, 4 Fälle, O(log n).
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Standard-AVL-Insert-Workflow. BST → Höhen → BF → Verletzung → Rotation → fertig. Bei Delete: ggf. mehrere Rotationen.
Typ: Reihenfolge