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).
Erklärung
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).
Die Idee in einem Satz
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.
Warum Balance?
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:
- Höhe
≤ 1.44 log₂(n + 2), alsoO(log n) - Suche, Insert, Delete alle
O(log n)garantiert
Balance-Faktor
Für jeden Knoten:
BF(v) = h(linkes Teilbaum) - h(rechtes Teilbaum)
AVL-Eigenschaft: |BF(v)| ≤ 1 für alle v.
- BF = 0: perfekt balanciert
- BF = +1: leicht links-lastig
- BF = -1: leicht rechts-lastig
- BF = ±2: Verletzung → Rotation nötig
Rotation: das Herz des AVL
Single-Right-Rotation (LL-Fall)
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.
Single-Left-Rotation (RR-Fall)
Spiegelbildlich. Rechts-lastig (BF=-2), Verletzung in rechtem Teilbaum.
LR-Rotation (Double-Rotation)
Links-lastig, aber Verletzung in RECHTEM Teilbaum von linkem Kind:
- Erst Left-Rotation auf linkem Kind
- Dann Right-Rotation auf Wurzel
RL-Rotation
Spiegelbild von LR.
Die 4 Rotation-Fälle
| 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.
Insert in AVL
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.
Delete in AVL
Komplizierter: nach Löschung können mehrere Rotationen auf dem Pfad zur Wurzel nötig sein. O(log n) Rotationen im Worst Case.
Andere balancierte Bäume
| 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.
Komplexität
| 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".
Klausur-Faustregeln
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.
Häufige Stolpersteine
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.
Interaktiv verstehen
AVL-Rotation-Stepper
Geh durch jede der 4 Rotation-Fälle (LL, RR, LR, RL) Schritt für Schritt. Du siehst:
- Den Original-Baum mit verletzter AVL-Eigenschaft
- Welcher Fall vorliegt (Vorzeichen-Paar (BF-Root, BF-Kind))
- Die Rotation in Aktion
- Den balancierten Baum danach
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.
Praxis-Übung
AVL-Bäume & Rotation, Praxis-Übung
6 Aufgaben zu AVL-Eigenschaft, Rotation-Typen, Balance-Faktor.
Klausurfragen mit Lösungen (6)
- F1.Was ist die AVL-Eigenschaft?
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.
- F2.Welche Rotation ist nötig bei BF=+2 (Wurzel) und BF=+1 (linkes Kind)?
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.
- F3.Ein AVL-Baum garantiert Suche/Insert/Delete in O(log n) im Worst Case.
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
- F4.Wann ist eine Double-Rotation nötig?
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).
- F5.Welche Aussagen über AVL-Bäume sind RICHTIG?
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
- F6.Ordne Rotation-Fall der Bedingung zu:
Zuordnungen:
- LL-Fall → BF(Wurzel)=+2, BF(linkes Kind)=+1 → Single Right
- RR-Fall → BF(Wurzel)=−2, BF(rechtes Kind)=−1 → Single Left
- LR-Fall → BF(Wurzel)=+2, BF(linkes Kind)=−1 → Double Left-Right
- RL-Fall → BF(Wurzel)=−2, BF(rechtes Kind)=+1 → Double Right-Left
Erklärung: 4 Rotation-Fälle. Erste 2 = Single (gleiche Vorzeichen), letzte 2 = Double (unterschiedliche Vorzeichen).
Typ: Zuordnung
Klausur-Quiz
Klausurfragen mit Lösungen (6)
- F1.Ein AVL-Baum hat n=15 Knoten. Was ist die MAXIMALE Höhe?
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
- F2.Nach einem Delete in einem AVL-Baum sind höchstens 1 Rotation nötig.
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
- F3.Du fügst die Werte 10, 20, 30 in dieser Reihenfolge in einen leeren AVL-Baum ein. Was passiert?
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.
- F4.Welche Datenstruktur nutzt Java's TreeMap intern?
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.
- F5.AVL-Bäume sind {{1}}-Suchbäume mit zusätzlicher Balance-Bedingung: |BF| ≤ {{2}}. Bei Verletzung wird eine {{3}} angewandt. Insgesamt gibt es {{4}} Rotation-Fälle (LL, RR, LR, RL). Alle AVL-Operationen sind {{5}}.
Lösungen pro Lücke:
- {{1}}: binäre / binär
- {{2}}: 1
- {{3}}: Rotation
- {{4}}: 4 / vier
- {{5}}: O(log n)
Erklärung: AVL-Vokabular. Binärer Suchbaum, |BF|≤1, Rotation, 4 Fälle, O(log n).
Typ: Lückentext
- F6.Sortiere: AVL-Insert mit Rebalancierung.
Richtige Reihenfolge:
- Normaler BST-Insert (Wert an passender Stelle)
- Höhen-Update entlang des Pfades zur Wurzel
- Balance-Faktor jedes Knotens berechnen
- Erste Verletzung (|BF| = 2) finden
- Passende Rotation anwenden (LL/RR/LR/RL)
- Nach erster Rotation: fertig (max. 1 Rot. bei Insert)
Erklärung: Standard-AVL-Insert-Workflow. BST → Höhen → BF → Verletzung → Rotation → fertig. Bei Delete: ggf. mehrere Rotationen.
Typ: Reihenfolge
