Selbstbalancierende Bäume¶

🚀 AVL-Bäume - Selbstbalancierende Binärbäume¶

📚 1️⃣ Was ist ein AVL-Baum?¶

Ein AVL-Baum ist ein selbstbalancierender binärer Suchbaum (BST).
Er wurde nach seinen Erfindern Adelson-Velsky und Landis benannt.

✅ Eigenschaft: Für jeden Knoten gilt: $$BF = Höhe (linker Teilbaum)−Höhe (rechter Teilbaum) ≤1$$
Das heißt: Die Höhe der linken und rechten Teilbäume darf sich um maximal 1 unterscheiden.
BF = +1: Linker Teilbaum ist um 1 höher → leicht nach links geneigt.
BF = 0: Beide Teilbäume sind gleich hoch → perfekt balanciert.
BF = -1: Rechter Teilbaum ist um 1 höher → leicht nach rechts geneigt.

🔍 Pseudo-Code

FUNKTION insert(node, key):
    WENN node leer:
        GIB neuen Knoten mit key zurück

    WENN key < node.key:
        node.left = insert(node.left, key)
    ANDERNFALLS:
        node.right = insert(node.right, key)

    AKTUALISIERE Höhe von node
    balance = Balance-Faktor(node)

    // 4 Rotationsfälle
    WENN balance > 1 UND key < node.left.key:
        GIB rechts-rotation(node)    // LL-Fall

    WENN balance < -1 UND key > node.right.key:
        GIB links-rotation(node)     // RR-Fall

    WENN balance > 1 UND key > node.left.key:
        node.left = links-rotation(node.left)  // LR-Fall
        GIB rechts-rotation(node)

    WENN balance < -1 UND key < node.right.key:
        node.right = rechts-rotation(node.right)  // RL-Fall
        GIB links-rotation(node)

    GIB node zurück

⚡ 4️⃣ AVL-Rotationen zur Balancierung¶

Wenn ein AVL-Baum aus dem Gleichgewicht gerät, wird er durch Rotationen korrigiert. Es gibt 4 Rotationstypen:

🔗 Studyfix - Studyfix

1️⃣ LL-Rotation (Links-Links-Fall):

Ungleichgewicht: Neuer Knoten wurde im linken Teilbaum des linken Kindes eingefügt.
Lösung: Rechtsrotation (Right Rotation)

➡️ Nach Rechtsrotation:

    2
   / \
  1   3

2️⃣ RR-Rotation (Rechts-Rechts-Fall):

Ungleichgewicht: Neuer Knoten wurde im rechten Teilbaum des rechten Kindes eingefügt.
Lösung: Linksrotation (Left Rotation)

➡️ Nach Linksrotation:

    2
   / \
  1   3

3️⃣ LR-Rotation (Links-Rechts-Fall):

Ungleichgewicht: Neuer Knoten wurde im rechten Teilbaum des linken Kindes eingefügt.
Lösung: Zweifache Rotation:
1. Linksrotation am linken Kind
2. Rechtsrotation am unbalancierten Knoten

➡️ Nach Doppelrotation:

    2
   / \
  1   3

4️⃣ RL-Rotation (Rechts-Links-Fall):

Ungleichgewicht: Neuer Knoten wurde im linken Teilbaum des rechten Kindes eingefügt.
Lösung: Zweifache Rotation:
1. Rechtsrotation am rechten Kind
2. Linksrotation am unbalancierten Knoten

➡️ Nach Doppelrotation:

    2
   / \
  1   3

🚀 5️⃣ AVL-Baum Einfügen (Insert)¶

Normal einfügen (wie in einem BST).
Balance-Faktoren berechnen.
Rotation anwenden, falls der Baum aus dem Gleichgewicht ist.

✅ Beispiel: AVL-Einfügeoperation¶

Einfügen der Knoten in dieser Reihenfolge: 10 → 20 → 30

1️⃣ Füge 10 ein:

2️⃣ Füge 20 ein:

  10
    \
     20

- Balance-Faktor von 10: -1 (ok)

3️⃣ Füge 30 ein:

Balance-Faktor von 10: -2 (ungleichgewichtig) → RR-Fall
✅ Lösung: Linksrotation bei 10. ➡️ Nach Rotation:
```
    20
   /  \
  10   30
```

🚀 9️⃣ Laufzeitanalyse¶

Suchen, Einfügen, Löschen: O(log⁡n)O(\log n)O(logn)
Balancierung: O(log⁡n)O(\log n)O(logn) durch Rotationen
Speicherkomplexität: O(n)O(n)O(n)

🎯 1️⃣0️⃣ Fazit¶

✅ AVL-Bäume sind immer balanciert, daher sehr effizient für Suchoperationen.
✅ Rotationen (LL, RR, LR, RL) halten den Baum ausgeglichen.
✅ Laufzeit für alle Operationen: $O(log⁡n)$
✅ Anwendungen: Datenbanken, Indexstrukturen, Speichermanagement.

🚀 Rot-Schwarz-Bäume - Selbstbalancierende Binärbäume¶

📚 1️⃣ Was ist ein Rot-Schwarz-Baum?¶

Ein Rot-Schwarz-Baum ist ein selbstbalancierender binärer Suchbaum (BST), der sicherstellt, dass der Baum immer ungefähr balanciert bleibt.
Er ist eine Alternative zu AVL-Bäumen, verwendet jedoch eine andere Strategie zur Balancierung, die effizienter für häufige Einfügungen und Löschungen ist.

🔑 2️⃣ Eigenschaften von Rot-Schwarz-Bäumen¶

Jeder Knoten ist entweder rot oder schwarz.
Die Wurzel ist immer schwarz.
Alle Blätter (NIL-Knoten) sind schwarz.
Ein roter Knoten hat keine roten Kinder (keine zwei roten Knoten direkt hintereinander).
Jeder Pfad von der Wurzel zu einem Blatt hat die gleiche Anzahl schwarzer Knoten (schwarze Höhe).

Diese Regeln sorgen dafür, dass der Baum immer logarithmisch hoch bleibt, was schnelle Such-, Einfüge- und Löschoperationen ermöglicht.

📊 3️⃣ Balance-Konzept: Schwarze Höhe¶

Die schwarze Höhe eines Knotens ist die Anzahl der schwarzen Knoten auf dem Weg von diesem Knoten bis zu einem Blatt.
Wichtige Regel: Alle Pfade von der Wurzel zu den Blättern müssen die gleiche schwarze Höhe haben.

🚀 4️⃣ Insert (Einfügen) in einen Rot-Schwarz-Baum¶

✅ Schritt-für-Schritt:¶

Füge den Knoten wie in einem normalen BST ein.
Färbe den neuen Knoten immer ROT.
Verletzen der Rot-Schwarz-Regeln?
- Falls ja, werden Rotationen und Umfärbungen angewendet.
Stelle sicher, dass die Wurzel am Ende immer SCHWARZ ist.

🔍 Pseudo-Code Vereinfacht - Insert

INSERT(node, key):
    Füge key normal wie im BST ein
    Färbe den neuen Knoten ROT

    WHILE (Elternknoten ROT):
        IF (Elternknoten ist linkes Kind):
            WENN Onkel ROT:
                Färbe Eltern & Onkel SCHWARZ, Großeltern ROT
                Setze Großeltern als neuen Knoten
            ANDERNFALLS:
                WENN der Knoten ein rechtes Kind ist:
                    Linksrotation am Elternknoten
                Rechtsrotation am Großelternknoten
                Farben von Eltern & Großeltern umkehren

        (Symmetrischer Fall für rechtes Kind)

    Wurzel immer SCHWARZ färben

🔄 Rotationen:¶

Linksrotation (Left Rotation): Dreht eine Kante nach links.
Rechtsrotation (Right Rotation): Dreht eine Kante nach rechts.

Diese Rotationstypen helfen dabei, die Balance des Baums wiederherzustellen.

🗺️ Beispielgraph¶

🔗 Studyfix - Studyfix

🚩 5️⃣ Delete (Löschen) in einem Rot-Schwarz-Baum¶

✅ Schritt-für-Schritt:¶

Lösche den Knoten wie in einem BST.
Falls ein schwarzer Knoten gelöscht wird:
- "Doppelschwarz"-Problem kann auftreten (Ungleichgewicht).
Lösen durch:
- Rotationen
- Umfärbungen
- Transfer schwarzer Höhe

🚀 B-Bäume - Selbstbalancierende Suchbäume für große Datenmengen¶

📚 1️⃣ Was ist ein B-Baum?¶

Ein B-Baum ist eine selbstbalancierende Baumstruktur, die speziell für den Einsatz in Datenbanken und Dateisystemen entwickelt wurde.
Er kann mehrere Schlüssel pro Knoten speichern und hat mehr als zwei Kinder → generalisierter AVL-Baum.

✅ Eigenschaft: Effizient für große Datenmengen, da er weniger tief ist (im Vergleich zu AVL/Red-Black-Bäumen).
✅ Optimal für Festplatten & Speicherzugriffe, da große Blöcke auf einmal verarbeitet werden.

🔑 2️⃣ Eigenschaften eines B-Baums (Ordnung m)¶

Ein B-Baum der Ordnung m hat:

Maximal $m−1$ Schlüssel pro Knoten
Mindestens $⌈m/2⌉ - 1$ Schlüssel pro Knoten (außer der Wurzel)
Maximal $m$ Kinder pro Knoten
Jeder interne Knoten mit $k$ Schlüsseln hat genau $k+1$ Kinder
Alle Blätter sind auf derselben Ebene → Baum ist immer balanciert.

🔗 Studyfix - Studyfix

✅ 8️⃣ Fazit¶

B-Bäume sind optimal für große Datenmengen.
✅ Insert: Einfügen + Split bei Überlauf.
✅ Delete: Löschen + Merge/Redistribute bei Unterlauf.
✅ Anwendungen: Datenbanken, Dateisysteme (z.B. NTFS, MySQL, PostgreSQL).