Algorithmen & Datenstrukturen

Bäume in ADS

Von Knoten zu Komplexität: ein visuelles Cheat Sheet für Begriffe, Operationen und typische Klausurfragen.

00

Schaubilder zuerst

Erst sehen, dann benennen. Diese sechs Bilder sind die Karte für die ganze Seite.

1 · Anatomie
10 5 20 15 30 Wurzel oben · Blätter unten

Wurzel, Kanten, innere Knoten, Blätter.

2 · Suchpfad
10 5 20 15 30 Suche 15: rechts → links

Ein Vergleich pro Ebene, nicht alle Knoten.

3 · 2-3-4-Knoten
5 | 12 | 30 <5 A B >30 3 Schlüssel → 4 Suchbereiche A=5..12 · B=12..30

Das Knotenlimit kommt aus den Suchbereichen.

4 · Split
10 | 15 | 20 15 hoch 15 10 20

Mitte hoch, kleiner links, größer rechts.

5 · Delete-Problem
10|20 −20 10 aber: 10 −10 → []

Leer ist verboten: dann leihen oder verschmelzen.

6 · Laufzeitbild
8 4 12 2 6 10 14 2 4 6 8 O(log n) O(n)

Die Höhe h entscheidet: balanciert vs. Liste.

01

Mentales Modell

Ein Baum ist eine Hierarchie: oben ein Startpunkt, darunter verzweigte Entscheidungen. Jede Verzweigung führt zu einem Teilproblem.

Kernidee
Baum = verzweigte Entscheidung

Wie ein Dateisystem: ein Ordner enthält weitere Ordner oder Dateien. Eine Ebene tiefer = eine Entscheidung mehr.

Leitfrage
Was ist hier das Blatt?

Jedes Mal, wenn du einen Baum siehst, finde zuerst Wurzel und Blätter. Der Rest ergibt sich daraus.

02

Grundbegriffe

Lerne die Begriffe am konkreten Baum, nicht aus einer abstrakten Definition.

Wurzel
Innerer Knoten
Blatt
Kante
10 5 20 15 30 Höhe = 2 Kanten · Tiefe(15) = 2 Kanten · Blätter = 15, 30
Kante
10 5

Eine einzelne Verbindung zwischen zwei Knoten.

Suchpfad
10 5 20 30

Folge von Knoten, die wir beim Suchen besuchen: 10 → 20 → 30.

Definition
Knoten

Eine Box, die einen Wert speichert und 0, 1 oder mehr Kinder haben kann.

Definition
Kante

Eine einzelne Verbindung zwischen zwei Knoten.

Definition
Wurzel

Oberster Knoten, hat keinen Elternknoten.

Definition
Blatt

Knoten ohne Kinder.

Definition
Höhe

Längster Weg von Wurzel zu einem Blatt, gemessen in Kanten.

Definition
Tiefe

Abstand eines Knotens von der Wurzel, gemessen in Kanten.

Tiefe 0 [10] <- Wurzel / \ Tiefe 1 [5] [20] <- Kanten verbinden die Knoten / \ Tiefe 2 [15][30] <- Blätter
03

Binärer Suchbaum

Links kleiner, rechts größer. Diese Regel lässt die Suche ganze Teilbäume überspringen.

10 5 20 alles < 10 alles > 10
Suchpfad nach 18: 10 → 20 → links (18 < 20)
Falsch: ungeordnet
10 15 3

Suche kann Teilbäume nicht überspringen.

Richtig: Suchbaum
10 5 15

Ein Vergleich pro Ebene halbiert den Rest.

Regel
Suchbaum-Invariante

Für jeden Knoten gilt: alle Werte im linken Teilbaum sind kleiner, alle im rechten Teilbaum sind größer.

Ich kann das erklären, wenn ich an einem konkreten Baum jeden Schritt der Suche nachvollziehen kann.
04

2-3-4-Knoten

Ein Knoten darf 1, 2 oder 3 Schlüssel enthalten. Die Anzahl Schlüssel bestimmt die Anzahl Kinder.

10
1 key
10 | 20
2 keys
10 | 20 | 30
3 keys
1 Schlüssel 10 < > 2 Schlüssel 10|20 < · > 3 Schlüssel 10|20|30 < · · > Schlüssel + 1 = maximale Anzahl Kinder
Schlüssel + 1 = maximale Anzahl Kinder 1 key → 2 Kinder | 2 keys → 3 Kinder | 3 keys → 4 Kinder
Warum maximal 4 Kinder?
Die 2-3-4-Regel

Ein Knoten mit 3 Schlüsseln hat 4 Bereiche, in die ein neuer Wert fallen kann. Mehr Bereiche gibt es nicht, weil ein Schlüssel nur zwischen zwei Bereichen steht.

[10 | 20 | 30] ↓ ↓ ↓ ↓ <10 10-20 20-30 >30 → 4 Bereiche → 4 Kinder möglich [10 | 20 | 30 | 40] ↓ ↓ ↓ ↓ ↓ <10 10-20 20-30 30-40 >40 → 5 Bereiche → 5 Kinder nötig → verboten
Erlaubt
10 | 20 | 30

3 Schlüssel erzeugen 4 Suchbereiche – genau passend.

Verboten
10 | 15 | 20 | 25

4 Schlüssel erzeugen 5 Suchbereiche, maximal 4 erlaubt.

05

Insert & Split

Einfügen legt sortiert hinzu. Ist der Knoten voll, wird gesplittet: die Mitte steigt auf.

1. Einfügen mit Platz

1
Start
[10 | 20]
→
2
+ 15 einfügen
sortiert
→
3
Ergebnis
[10 | 15 | 20]

2. Split am Beispiel [4 | 9 | 15] — interaktiv

‚Split-Mechanik im 2-3-4-Baum‘ — Audio-Erklärung zur Animation

4|9|15 9 4 15 9 4 15 Mitte kleiner als 9 größer als 9 Schritt 0: Start
Wir haben einen vollen Knoten [4 | 9 | 15]. Er enthält bereits 3 Schlüssel — mehr passen nicht hinein.
Vor dem Split 4|9|15 Nach dem Split 9 4 15

3. Einfügen in einen vollen Knoten

1
Voll
[10 | 15 | 20]
→
2
+ 25
passt nicht mehr
→
3
Split
Mitte 15 hoch
→
4
Neu einfügen
25 rechts
Vor dem Split 10|15|20 Nach dem Split + Einfügen von 25 15 10 20|25
Merksatz
Einfügen vs. Splitten

Einfügen = sortiert in die passende Box legen.
Splitten = voller Knoten wird geteilt; die Mitte steigt zum Elternknoten auf.

06

Löschen aus Blättern

Löschen ist einfach, solange der Knoten danach nicht leer wird. Sonst muss repariert werden.

Einfacher Fall
10 | 20
− 20→
10

Knoten bleibt gültig.

Reparatur nötig
10
− 10→
[]

Leerer Knoten verletzt die Baumregel.

Reparatur-Strategien: Fall A: Geschwister hat > 1 Schlüssel [8] [9] / \ → / \ [6|7] [10] [6] [7|10] leihen / rotieren Fall B: Geschwister hat nur 1 Schlüssel [8] [] / \ → [6|8|10] [6] [10] verschmelzen
07

Komplexität

Suche kostet O(h), weil pro Ebene genau eine Entscheidung fällt. Die Frage ist: wie groß ist h?

n = Anzahl gespeicherter Werte h = Höhe des Baums = Anzahl Kanten von Wurzel bis tiefstes Blatt
Warum O(log n)?
Halbieren pro Ebene

In einem balancierten Baum hat jeder Knoten etwa 2 Kinder. Jede Ebene verdoppelt die Anzahl möglicher Plätze. Umgekehrt: bei n Werten brauchen wir nur etwa log₂(n) Ebenen.

Ebene 0: 1 Knoten Ebene 1: 2 Knoten Ebene 2: 4 Knoten Ebene 3: 8 Knoten ... Ebene h: 2^h Knoten Wenn n Werte gespeichert sind: n ≈ 2^h Auflösen nach h: h ≈ log₂(n) Also: Suche braucht O(h) = O(log n) Schritte
n Werte
Anzahl gespeicherter Elemente
→
h Ebenen
Höhe des Baums
→
1 Schritt/Ebene
Entscheidung pro Level
→
O(h)
Gesamtkosten der Suche
Balanciert — O(log n)
8 4 12 2 6 10 14

Jede Ebene verdoppelt die Kapazität.

Entartet — O(n)
2 4 6 8 10

Baum ist eine verkettete Liste.

Balanciert
h ≈ log₂(n)

Suche: O(log n). Jede Ebene halbiert den Rest.

Entartet
h ≈ n

Suche: O(n). Baum sieht aus wie eine verkettete Liste.

2-3-4-Baum
h = O(log n)

Insert/Delete halten den Baum balanciert: O(log n).

Big-O-Check
Bevor du O(log n) schreibst
  1. Was ist n?
  2. Was ist der zentrale Schritt?
  3. Wie viele Ebenen muss ich maximal runter?
  4. Was ist h?
  5. Ist h eher log n oder n?
08

Typische Fallen

Diese falschen Denkspuren tauchen in Testaten und Klausuren immer wieder auf.

Falsche SpurKorrektur
[10 | 15 | 20] sind drei Knoten.Das ist ein Knoten mit drei Schlüsseln.
Einfügen heißt hinten anhängen.Einfügen heißt sortiert einsortieren.
2-3-4-Knoten mit vier Schlüsseln ist okay.Vier Schlüssel erzeugen fünf Suchbereiche, maximal vier erlaubt.
Suche ist immer O(log n).Suche ist O(h). Nur wenn h = log n, wird daraus O(log n).
09

Testat-Check & Klausurdrill

Nicht nur lesen – aktiv abrufen. Erkläre jeden Begriff mit eigenen Worten.

Testat-Check
Schnellfragen
  1. Was ist ein Knoten?
  2. Was ist ein Blatt?
  3. Warum ist [10 | 20 | 30] in einem 2-3-4-Baum noch erlaubt?
  4. Warum ist [10 | 15 | 20 | 25] verboten?
  5. Was passiert beim Split von [4 | 9 | 15]?
  6. Warum ist Suche in balancierten Bäumen O(log n)?
  7. Wann wird ein Baum zu O(n)?
10-Minuten-Klausurdrill
Aufgaben
  1. Markiere im Baum 10 / 5 / 20 Wurzel, Blätter und Höhe.
  2. Wie viele Suchbereiche hat [5 | 12 | 30]?
  3. Was passiert bei [10 | 20] + 15?
  4. Was passiert bei [4 | 9 | 15] beim Split?
  5. Warum ist Suche in einem balancierten Baum O(log n)?

Lösungsskizze

  1. Wurzel 10, Blätter 5 und 20, Höhe 1 (Kanten) oder 2 (Knoten).
  2. Vier Suchbereiche.
  3. Sortiert einfügen: [10 | 15 | 20].
  4. 9 geht hoch, 4 links, 15 rechts.
  5. Pro Ebene eine Entscheidung; balancierter Baum hat etwa log₂(n) Ebenen.

Ich kann das erklären, wenn …

  • ich einen beliebigen Mini-Baum in Wurzel, Blätter, Höhe und Tiefe zerlegen kann.
  • ich an einem 2-3-4-Knoten die Anzahl Kinder aus den Schlüsseln ableiten kann.
  • ich Insert und Split am konkreten Beispiel Schritt für Schritt trace.
  • ich Big-O mit n, h und dem zentralen Schritt begründe.