INF-DS - Datenstrukturen — Informatik · Matura-Zusammenfassung

Arrays, Listen, Stack und Queue#

~4 Min LesezeitBasisINF-DS-1.1

Datenstrukturen organisieren Daten so, dass die häufigen Operationen schnell sind - die richtige Wahl hängt vom Operationsprofil ab, nicht von „der einen besten" Struktur. Die linearen Grundbausteine sind Array, verkettete Liste, Stack und Queue (, ).

Stack (LIFO) und Queue (FIFO)

Abb. 1Stack: push/pop am gleichen Ende; Queue: enqueue hinten, dequeue vorne.

Einfach verkettete Liste

Abb. 2Jeder Knoten speichert einen Wert und einen Zeiger (next) auf den nächsten Knoten; das Listenende zeigt auf NIL. Einfügen vorne O(1), Suchen O(n).

Abb. 1 ↓Abb. 2 ↓

Ein Array liegt zusammenhängend im Speicher; daraus folgt wahlfreier Zugriff in

O(1)

, denn die Adresse jedes Elements ist Basisadresse

+

Index

\cdot

Elementgröße. Der Preis: Einfügen oder Löschen in der Mitte kostet

O(n)

, weil alle nachfolgenden Elemente verschoben werden müssen, und die Größe ist (klassisch) fest.

Eine verkettete Liste speichert je Element einen Knoten aus Daten plus einem Zeiger auf den nächsten. Damit ist Einfügen/Löschen am Anfang (oder an bekannter Stelle)

O(1)

- man hängt nur Zeiger um -, dafür gibt es keinen wahlfreien Zugriff: Das

k

-te Element erreicht man nur durch Durchlaufen, also

O(n)

. Eine doppelt verkettete Liste trägt zusätzlich einen Rückwärtszeiger.

Ein Stack arbeitet nach LIFO (Last In, First Out): `push` legt oben ab, `pop` nimmt oben weg, beides

O(1)

(). Stacks stecken überall, wo das zuletzt Begonnene zuerst beendet wird - der Aufruf-Stack bei Funktionsaufrufen, Undo-Funktionen, die Klammer-/Syntaxprüfung und die Auswertung von Postfix-Ausdrücken.

Eine Queue arbeitet nach FIFO (First In, First Out): `enqueue` hängt hinten an, `dequeue` nimmt vorne weg, beides

O(1)

. Anwendungen sind Druckwarteschlangen, die Breitensuche (BFS) und Round-Robin-Scheduler. Eine effiziente Array-Queue realisiert man als Ringpuffer (zwei Indizes laufen modulo der Kapazität), sonst kostet das Nachrücken

O(n)

. Eine Deque erlaubt Einfügen/Löschen an beiden Enden in

O(1)

.

Die Wahl folgt dem Profil: viele wahlfreie Lesezugriffe → Array; viele Einfügungen am Anfang → verkettete Liste; reines „zuletzt zuerst" → Stack; reines „der Reihe nach" → Queue. Typische Fehler: Stack und Queue (LIFO vs. FIFO) verwechseln, der verketteten Liste schnellen Random-Access zuschreiben, oder bei der Array-Queue den Ringpuffer vergessen.

Vokabeln

→ Kartei

ArrayZusammenhängender Speicherblock mit indiziertem Zugriff in $O(1)$.
verkettete ListeFolge von Knoten mit Zeigern; günstiges Einfügen, teurer Zugriff.
StackLast-in-first-out-Speicher mit push und pop.
QueueFirst-in-first-out-Speicher mit enqueue und dequeue.
RingpufferArray mit umlaufenden Indizes; Grundlage der effizienten Array-Queue.
abstrakter DatentypDefinition über Operationen und ihr Verhalten, nicht über die Implementierung.

Musterbeispiel

Klammerausdruck mit Stack prüfen

Prüfe mit einem Stack, ob die Zeichenkette "{[()]}" korrekt geklammert ist.

Initial
Leerer Stack S. Lese Zeichen von links nach rechts.
Push {
S = [ "{" ].
Push [
S = [ "{", "[" ].
Push (
S = [ "{", "[", "(" ].
Pop )
Top "(" passt zu ")"; S = [ "{", "[" ].
Pop ]
Top "[" passt zu "]"; S = [ "{" ].
Pop }
Top "{" passt zu "}"; S = [ ].
Prüfung Stack leer
Stack leer -> Ausdruck korrekt geklammert.

Ergebnis: Algorithmus liefert true. Laufzeit O(n), Speicher O(n) im Worst Case.

Schritt-für-Schritt Erklärung3 Schritte

1
Stack und Queue sind die zwei gegensätzlichsten linearen Datenstrukturen: gleicher Container, andere Bedienungsrichtung.
Stack (LIFO) und Queue (FIFO)
Abb.Stack: push/pop am gleichen Ende; Queue: enqueue hinten, dequeue vorne.
2
In jedem Compiler steckt ein Stack für die Funktionsaufrufe; in jedem Drucker eine Queue für die Druckaufträge.
3
Linked List ist immer dann sinnvoll, wenn du wenig wahlfreien Zugriff, aber häufig Einfügen vorne brauchst.
Einfach verkettete Liste
Abb.Jeder Knoten speichert einen Wert und einen Zeiger (next) auf den nächsten Knoten; das Listenende zeigt auf NIL. Einfügen vorne O(1), Suchen O(n).

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Vergleiche Stack und Queue hinsichtlich Zugriffsmuster, Laufzeitkomplexität und typischen Anwendungen. Skizziere die Datenstrukturen.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Stack und Queue werden verwechselt; LIFO gegen FIFO.
Der verketteten Liste wird schnellerer wahlfreier Zugriff zugeschrieben als dem Array; sie muss von vorn durchlaufen werden.
Bei der Array-Queue fehlt der Ringpuffer; das Verschieben macht das Entnehmen $O(n)$ .
Einfügen am Anfang wird bei Array und Liste gleich bewertet; beim Array kostet es $O(n)$ .
Der Speicheroverhead der Zeiger in der verketteten Liste bleibt unerwähnt.

Aktive Wiederholung

Implementiere in Python eine Klasse `Queue` mit den Methoden enqueue, dequeue, peek und size unter Verwendung einer verketteten Liste. Welche Laufzeit haben die Operationen?

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Pat Morin: Open Data Structures (Carleton University)

Bäume - BST, AVL und Heap#

~4 Min LesezeitStandardINF-DS-2.1INF-DS-2.2

Lineare Strukturen erzwingen

O(n)

-Suche. Bäume brechen das auf: Ein hierarchischer Aufbau mit Verzweigung erlaubt, auf jeder Stufe einen großen Teil der Daten auszuschließen - die Grundlage logarithmischer Such- und Einfügezeiten.

Ein Binärbaum hat höchstens zwei Kinder pro Knoten (links/rechts). Die Höhe

h

ist die längste Wurzel-Blatt-Distanz; ein vollständiger Binärbaum der Höhe

h

fasst bis zu

2^{h+1}-1

Knoten. Umgekehrt hat ein balancierter Baum mit

n

Knoten nur Höhe

\approx \log_{2} n

- genau daher die Effizienz.

Ein Binärer Suchbaum (BST) erfüllt die BST-Ordnung links

<

Knoten

<

rechts (). Das hat eine schöne Konsequenz: Die Inorder-Traversierung (links - Knoten - rechts) liefert die Werte in sortierter Reihenfolge. Preorder (Knoten zuerst) und Postorder (Knoten zuletzt) dienen anderen Zwecken wie Kopieren oder Löschen - die drei nicht verwechseln.

Binärer Suchbaum (BST)

Abb. 3BST-Ordnung: linker Teilbaum < Knoten < rechter Teilbaum. Die Inorder-Traversierung (links, Knoten, rechts) liefert die Werte sortiert: 1, 3, 4, 6, 7, 8, 10, 14.

Abb. 3 ↓

Suchen, Einfügen und Löschen im BST kosten

O(h)

: Man vergleicht und geht je nach kleiner/größer links oder rechts. Im balancierten Fall ist

h=O(\log n)

, im degenerierten Fall (etwa sortierte Einfügefolge) entartet der Baum zur Liste mit

h=n-1

und

O(n)

. Das Löschen eines Knotens mit zwei Kindern löst man über den Inorder-Nachfolger (den kleinsten Wert im rechten Teilbaum).

Damit die

O(\log n)

-Garantie hält, balancieren sich AVL-Bäume selbst (

|h_{l} - h_{r}| \leq 1

, mittels Rotationen - eigener Abschnitt). Eine andere Baumart ist der Heap (Min-/Max-Heap): ein vollständiger Binärbaum mit der Heap-Eigenschaft (Eltern

\leq

Kinder beim Min-Heap), Einfügen und Extract-Min in

O(\log n)

- aber nicht sortiert in der Traversierung.

Bäume sind allgegenwärtig: BSTs und AVL für sortierte Mengen und Wörterbücher, Heaps für Prioritätswarteschlangen (Dijkstra), Heapsort und Top-k-Suche, dazu Parse-Bäume, Dateisysteme und der DOM. Häufige Fehler: Inorder mit Preorder verwechseln, den Zwei-Kinder-Löschfall falsch lösen, oder den Heap für sortiert halten.

Vokabeln

→ Kartei

binärer SuchbaumBaum mit kleineren Schlüsseln links und größeren rechts jedes Knotens.
InorderTraversierung links, Knoten, rechts; beim Suchbaum sortiert.
HöheLänge des längsten Weges von der Wurzel zu einem Blatt.
AVL-BaumSelbstbalancierender Suchbaum mit Balancefaktor höchstens eins.
RotationLokale Umhängeoperation, die die Ordnung erhält und die Höhe ausgleicht.
Heap-BedingungJeder Knoten ist kleiner (bzw. größer) als seine Kinder.

Höhe eines BST mit n Knoten

h_{\min} = \lceil \log_{2}(n+1) \rceil - 1,\quad h_{\max} = n-1

Die Höhe zählt Kanten von der Wurzel zum tiefsten Blatt. Der Bestfall ist der vollständig ausgeglichene Baum, der Schlechtestfall die zur Liste entartete Kette - genau diese Spanne motiviert die Selbstbalancierung.

Musterbeispiel

Werte 8, 3, 10, 1, 6, 14, 4, 7 in einen leeren BST einfügen

Konstruiere den BST, der entsteht, wenn die Werte in der gegebenen Reihenfolge eingefügt werden.

Einfügen 8
8 wird Wurzel.
Einfügen 3
3 < 8 -> links von 8.
Einfügen 10
10 > 8 -> rechts von 8.
Einfügen 1
1 < 8, 1 < 3 -> links von 3.
Einfügen 6
6 < 8, 6 > 3 -> rechts von 3.
Einfügen 14
14 > 8, 14 > 10 -> rechts von 10.
Einfügen 4
4 < 8, 4 > 3, 4 < 6 -> links von 6.
Einfügen 7
7 < 8, 7 > 3, 7 > 6 -> rechts von 6.

Ergebnis: Inorder-Traversierung liefert 1, 3, 4, 6, 7, 8, 10, 14 - das ist die sortierte Folge.

Schritt-für-Schritt Erklärung3 Schritte

1
Im BST gilt links kleiner, rechts größer - daher liefert Inorder direkt die sortierte Liste.
Binärer Suchbaum (BST)
Abb.BST-Ordnung: linker Teilbaum < Knoten < rechter Teilbaum. Die Inorder-Traversierung (links, Knoten, rechts) liefert die Werte sortiert: 1, 3, 4, 6, 7, 8, 10, 14.
2
Wenn du bewusst sortierte Daten einfügst, entartet der BST zu einer Liste mit $O(n)$ Operationen.
3
AVL und Red-Black-Bäume balancieren automatisch, indem sie Knoten rotieren.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Konstruiere einen binären Suchbaum aus der Einfügefolge 25, 12, 36, 4, 18, 30, 50, 9. Wie lautet die Inorder-Traversierung? Diskutiere die Laufzeit der Suche im Worst Case.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Inorder und Preorder werden verwechselt.
Beim Löschen eines Knotens mit zwei Kindern wird ein beliebiges Kind hochgezogen; die Suchbaumordnung geht dabei verloren.
Der Heap wird als sortierter Baum beschrieben; seine Traversierung liefert keine sortierte Folge.
Die Höhe wird mit der Knotenanzahl verwechselt.
Es wird angenommen, jeder Suchbaum sei ausgeglichen; eine sortierte Einfügefolge entartet ihn zur Liste.

Aktive Wiederholung

Konstruiere den BST für die Einfügefolge 50, 30, 70, 20, 40, 60, 80, 10. Lies die Inorder-Traversierung ab.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Open Data Structures - Chapter 6/7 (Pat Morin)

Hashtabellen und Kollisionsstrategien#

~4 Min LesezeitVertiefungINF-DS-3.1

Sortierte Strukturen erreichen

O(\log n)

- geht es noch schneller? Hashtabellen schaffen erwartetes

O(1)

für Suchen, Einfügen und Löschen, indem sie den Schlüssel direkt in einen Array-Index umrechnen, statt ihn mit anderen zu vergleichen.

Eine Hashtabelle speichert (Schlüssel, Wert)-Paare in einem Array der Größe

m

und nutzt eine Hashfunktion

h: K \to \{0,\dots,m-1\}

, die jedem Schlüssel einen Bucket-Index zuordnet (). Eine gute Hashfunktion ist deterministisch (gleicher Schlüssel, gleicher Index), gleichverteilt (streut breit und vermeidet Häufungen) und schnell berechenbar.

Hash-Tabelle mit Separate Chaining

Abb. 4Die Hashfunktion h(k) bestimmt den Bucket-Index; Kollisionen (Ben und Eva landen in Bucket 2) werden als verkettete Liste angehängt. Lastfaktor α = n/m, Suchen erwartet O(1 + α).

Abb. 4 ↓

Da

|K|

meist viel größer als

m

ist, sind Kollisionen unvermeidlich (Schubfachprinzip): Zwei Schlüssel erhalten denselben Index. Zwei Strategien lösen das auf - Separate Chaining hängt pro Bucket eine verkettete Liste an; Open Addressing sucht bei Belegung einen anderen freien Slot (Linear, Quadratic oder Double Probing).

Der Lastfaktor

\alpha = n/m

misst die Füllung und steuert die erwartete Laufzeit: Bei Chaining ist die erwartete Suchzeit

O(1+\alpha)

, bei Open Addressing steigt sie ab

\alpha > 0{,}7

steil an (), weil freie Slots rar werden. Übersteigt

\alpha

einen Schwellwert, rehasht man:

m

verdoppeln und alle Schlüssel neu platzieren (

O(n)

, amortisiert aber günstig).

Erwartete Suchschritte vs. Lastfaktor α

Abb. 6Bei Chained Hashing wächst die erwartete Suchzeit linear mit dem Lastfaktor α = n/m. Markiert: α = 1 (im Mittel ein Element pro Bucket, etwa 2 Schritte).

Abb. 6 ↓

Beispiel

h(k)=k \bmod 7

: 19, 26, 33 und 12 landen alle in Bucket 5 (alle

\equiv 5

), 14 und 7 in Bucket 0 - eine schiefe Verteilung (), die zeigt, wie sehr es auf eine gute Hashfunktion und Tabellengröße ankommt. In der Praxis nutzen Python `dict` und Java `HashMap` ausgereifte Hashtabellen mit erwartet

O(1)

.

Kollisionen pro Bucket (m=10 Slots, n=20 Schlüssel)

Abb. 5Empirische Verteilung der Schlüssel pro Bucket bei gleichverteilter Hashfunktion (Poisson-Näherung). Hervorgehoben: der häufigste Fall (2 Schlüssel).

Abb. 5 ↓

Häufige Fehler: die Hashfunktion für injektiv halten (sie ist es nie); den Lastfaktor nicht überwachen und so in

O(n)

rutschen; oder kryptografische Hashes (SHA-256) als Tabellen-Hash einsetzen - die sind kollisionsresistent, aber viel zu langsam für diesen Zweck.

Vokabeln

→ Kartei

HashfunktionAbbildung eines Schlüssels auf einen Tabellenindex.
KollisionZwei Schlüssel erhalten denselben Index.
ChainingKollisionsbehandlung durch verkettete Listen je Bucket.
offene AdressierungKollisionsbehandlung durch Sondieren freier Plätze in der Tabelle.
LastfaktorVerhältnis von Einträgen zu Tabellenplätzen.
RehashingNeuaufbau der Tabelle mit größerer Kapazität.

Lastfaktor und erwartete Suchzeit in einer Hashtabelle

\alpha = \frac{n}{m},\qquad \mathrm{E}[\text{Suche}] = O(1 + \alpha)

$n$ ist die Zahl der Einträge, $m$ die der Tabellenplätze. Beim Chaining bleibt die Suche im Mittel konstant, solange $\alpha$ klein bleibt; übliche Implementierungen vergrößern die Tabelle ab etwa 0,75.

Musterbeispiel

Hashtabelle mit Separate Chaining

Füge Schlüssel 19, 26, 14, 7, 33, 12 in eine Hashtabelle der Größe $m=7$ mit $h(k)=k \bmod 7$ ein (Chaining).

Hashwerte
19 mod 7 = 5; 26 mod 7 = 5; 14 mod 7 = 0; 7 mod 7 = 0; 33 mod 7 = 5; 12 mod 7 = 5.
Buckets befüllen
Bucket 0: [14, 7]; Bucket 5: [19, 26, 33, 12].
Lastfaktor
$\alpha = 6/7 \approx 0{,}86$ - hoch, Performance sinkt.
Suche nach 33
Hash 5, Liste durchsuchen: 19, 26, 33 (gefunden in 3 Schritten).

Ergebnis: Bucket 5 ist stark belegt (4 von 6 Schlüsseln). Bessere Hashfunktion oder größeres $m$ würde gleichmäßiger streuen.

Schritt-für-Schritt Erklärung3 Schritte

1
Eine Hashtabelle wandelt Schlüssel in Array-Indizes um - das ist der Trick für konstante Suchzeit.
Hash-Tabelle mit Separate Chaining
Abb.Die Hashfunktion h(k) bestimmt den Bucket-Index; Kollisionen (Ben und Eva landen in Bucket 2) werden als verkettete Liste angehängt. Lastfaktor α = n/m, Suchen erwartet O(1 + α).
2
Kollisionen sind unvermeidbar (Schubfachprinzip); entscheidend ist eine schnelle Auflösung.
3
Wenn der Lastfaktor steigt, vergrößere die Tabelle und hash neu - sonst sinkt die Performance.
Erwartete Suchschritte vs. Lastfaktor α
Abb.Bei Chained Hashing wächst die erwartete Suchzeit linear mit dem Lastfaktor α = n/m. Markiert: α = 1 (im Mittel ein Element pro Bucket, etwa 2 Schritte).

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erläutere das Prinzip einer Hashtabelle. Wie werden Kollisionen behandelt? Diskutiere die Laufzeit der Suche im Best/Average/Worst Case.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Die Hashfunktion wird als injektiv angenommen; Kollisionen sind unvermeidlich.
Der Lastfaktor wird nicht überwacht; die Zugriffszeit verschlechtert sich schleichend auf $O(n)$ .
Die Sondierungsstrategie bleibt unbenannt; linear, quadratisch und Double Hashing verhalten sich verschieden.
Beim Löschen in offener Adressierung wird der Platz einfach geleert; die Sondierungskette bricht dadurch ab.
Aus der durchschnittlichen $O(1)$ -Zeit wird eine Garantie gemacht.

Aktive Wiederholung

Füge die Schlüssel 19, 26, 14, 7, 33, 12 in eine Hashtabelle der Größe $m=7$ mit $h(k)=k \bmod 7$ und Linear Probing ein. Notiere den finalen Belegungszustand.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: MDN - Map (JavaScript) (Mozilla) · CPython dict implementation notes (PSF)

Graphen und Traversierung (BFS, DFS, Dijkstra)#

~5 Min LesezeitVertiefungINF-DS-4.1INF-DS-4.2

Wenn Beziehungen wichtiger sind als Reihenfolge - Straßennetze, soziale Netzwerke, Abhängigkeiten -, ist der Graph die passende Struktur (). Ein Graph

G=(V,E)

besteht aus Knoten

V

und Kanten

E

und kann gerichtet/ungerichtet, gewichtet/ungewichtet und zyklisch/azyklisch sein.

Gewichteter gerichteter Graph (Dijkstra-Beispiel)

Abb. 7Kürzeste Wege ab A; der optimale Weg nach E führt über A->C->B->D->E mit Länge 10.

Abb. 7 ↓

Zwei Darstellungen mit gegensätzlichen Profilen: Die Adjazenzmatrix (

|V|\times|V|

) prüft eine Kante in

O(1)

, braucht aber

O(|V|^{2})

Speicher - gut für dichte Graphen. Die Adjazenzliste speichert pro Knoten seine Nachbarn, also

O(|V|+|E|)

Speicher - sparsam für die in der Praxis üblichen dünnen Graphen.

Die Breitensuche (BFS) nutzt eine Queue und besucht Knoten in wachsender Distanz von der Quelle, Ring um Ring. In ungewichteten Graphen findet sie damit kürzeste Wege; Laufzeit

O(|V|+|E|)

. Im Beispiel A-B, A-C, B-D, C-D, D-E ergibt sich ab A die Besuchsreihenfolge A, B, C, D, E mit Distanzen

0, 1, 1, 2, 3

.

Die Tiefensuche (DFS) nutzt einen Stack (oder Rekursion) und verfolgt einen Pfad bis zum Ende, bevor sie zurücksetzt. Sie ist die Basis für topologisches Sortieren (Reihenfolge bei Abhängigkeiten), Zyklenerkennung und das Finden starker Zusammenhangskomponenten (SCC); ebenfalls

O(|V|+|E|)

.

Für gewichtete Graphen mit nicht-negativen Kanten liefert Dijkstra kürzeste Wege: Man finalisiert stets den noch unbesuchten Knoten mit der kleinsten bekannten Distanz (effizient per Min-Heap) und relaxiert seine ausgehenden Kanten (). Mit Heap ist das

O((|V|+|E|)\log |V|)

. Wichtig: Bei negativen Kanten versagt Dijkstra - dann nutzt man Bellman-Ford.

Anwendungen reichen von der Navigation (kürzeste Route) über soziale Netze und Web-Crawling bis zum Compiler (ein DAG modelliert Abhängigkeiten und die Build-Reihenfolge). Häufige Fehler: BFS und DFS (Queue vs. Stack) verwechseln, Dijkstra auf negative Gewichte anwenden, oder für dünne Graphen die speicherhungrige Adjazenzmatrix wählen.

Vokabeln

→ Kartei

gerichteter GraphGraph mit einseitig gerichteten Kanten.
AdjazenzmatrixQuadratische Tabelle der Nachbarschaftsbeziehungen; $O(n^{2})$ Speicher.
AdjazenzlisteJe Knoten eine Liste seiner Nachbarn; günstig bei dünnen Graphen.
BreitensucheEbenenweises Durchlaufen mit einer Queue; findet kürzeste Wege in ungewichteten Graphen.
TiefensucheDurchlauf so tief wie möglich mit einem Stack oder rekursiv.
Dijkstra-AlgorithmusVerfahren für kürzeste Wege bei nichtnegativen Kantengewichten.

Maximale Kantenzahl im einfachen ungerichteten Graphen

|E| \leq \binom{|V|}{2} = \tfrac{|V|(|V|-1)}{2}

$|V|$ ist die Knoten-, $|E|$ die Kantenzahl. Weil die Kantenzahl quadratisch wachsen kann, lohnt die Adjazenzmatrix nur bei dichten Graphen; bei dünnen ist die Adjazenzliste mit $O(|V|+|E|)$ sparsamer.

Musterbeispiel

BFS auf einem 5-Knoten-Graph

Führe BFS auf dem Graphen A-B, A-C, B-D, C-D, D-E ab Knoten A durch.

Initial
Queue Q = [A], visited = {A}.
Schritt 1
Dequeue A. Nachbarn B, C nicht in visited -> enqueue. Q = [B, C], visited = {A, B, C}.
Schritt 2
Dequeue B. Nachbarn A (besucht), D -> enqueue. Q = [C, D], visited = {A, B, C, D}.
Schritt 3
Dequeue C. Nachbarn A, D bereits besucht. Q = [D].
Schritt 4
Dequeue D. Nachbar E -> enqueue. Q = [E], visited = {A, B, C, D, E}.
Schritt 5
Dequeue E. Keine neuen Nachbarn.

Ergebnis: Besuchsreihenfolge: A, B, C, D, E. Distanzen ab A: A=0, B=1, C=1, D=2, E=3.

Musterbeispiel

Dijkstra auf einem gewichteten gerichteten Graph

Bestimme die kürzesten Wege ab A im gerichteten Graphen mit Kanten A->B (4), A->C (2), B->C (1), B->D (5), C->B (1), C->D (8), C->E (10), D->E (2). Führe die Distanz/Vorgänger-Tabelle Schritt für Schritt.

Init
dist[A]=0, alle anderen $\infty$ . Min-Heap PQ = {(0,A)}. visited = {}.
A finalisieren (d=0)
Relaxiere A->B: dist[B]=4 (Vorg. A); A->C: dist[C]=2 (Vorg. A). PQ = {(2,C),(4,B)}.
C finalisieren (d=2)
C hat die kleinste Distanz. Relaxiere C->B: 2+1=3 < 4, also dist[B]=3 (Vorg. C); C->D: dist[D]=10 (Vorg. C); C->E: dist[E]=12 (Vorg. C). PQ = {(3,B),(10,D),(12,E)}.
B finalisieren (d=3)
Relaxiere B->C (bereits final, überspringen); B->D: 3+5=8 < 10, also dist[D]=8 (Vorg. B). PQ = {(8,D),(12,E)}.
D finalisieren (d=8)
Relaxiere D->E: 8+2=10 < 12, also dist[E]=10 (Vorg. D). PQ = {(10,E)}.
E finalisieren (d=10)
E hat keine ausgehenden Kanten. PQ leer -> fertig.

Ergebnis: Endgültige Distanzen ab A: A=0, C=2, B=3, D=8, E=10. Kürzester Weg A->E = A->C->B->D->E (Länge 10) - günstiger als der direkte A->B (4) oder A->C->E (12), weil B über C auf 3 relaxiert wird.

Schritt-für-Schritt Erklärung3 Schritte

1
Ein Graph ist die universelle Datenstruktur für Netzwerke - vom Verkehrsnetz bis zum sozialen Graph.
2
BFS und DFS sind dieselbe Idee mit unterschiedlicher Wartespeicher-Struktur: Queue oder Stack.
3
Dijkstra nutzt einen Min-Heap, um stets den naechst-naehesten Knoten zu expandieren.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Beschreibe Graphen als Datenstruktur. Vergleiche Adjazenzmatrix und Adjazenzliste. Erkläre BFS oder DFS am Beispiel eines selbst gewählten Graphen.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

BFS und DFS werden verwechselt; die eine nutzt eine Queue, die andere einen Stack.
Dijkstra wird auf Graphen mit negativen Kantengewichten angewandt.
Für dünne Graphen wird die Adjazenzmatrix gewählt; sie verschwendet Speicher.
Besuchte Knoten werden nicht markiert; das Verfahren läuft in Zyklen endlos.
Nur die Distanz wird ausgegeben, obwohl der WEG gefragt ist - dafür braucht es die Vorgänger.

Aktive Wiederholung

Gegeben Graph mit Knoten {A,B,C,D,E} und Kanten A-B, A-C, B-D, C-D, D-E. Führe BFS ab Knoten A durch und liste die Besuchsreihenfolge auf.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: CLRS - Graph Algorithms (Kap. 22-24) (MIT Press)

Selbstbalancierung - AVL-Rotationen#

~6 Min LesezeitVertiefungINF-DS-2.2

AVL-Rechtsrotation nach LL-Imbalance

Abb. 8Einfügen von 1 erzeugt am Knoten 3 Balancefaktor +2 (LL-Fall); eine Rechtsrotation an 3 stellt die Balance her.

Ein binärer Suchbaum garantiert von sich aus gar nichts. Fügt man Schlüssel in aufsteigender Reihenfolge ein, entsteht kein Baum, sondern eine Liste - und aus der versprochenen

O(\log n)

-Suche wird

O(n)

. Genau diese Entartung verhindert der AVL-Baum, indem er nach jeder Einfüge- und Löschoperation prüft, ob er noch ausgeglichen ist, und ihn nötigenfalls durch Rotationen wiederherstellt.

Das Kriterium ist der BALANCEFAKTOR eines Knotens: die Höhe seines linken Teilbaums minus die Höhe seines rechten. Erlaubt sind nur die Werte

-1

,

0

und

+1

; sobald ein Betrag von 2 auftritt, ist der Knoten unbalanciert. Wichtig ist, dass es sich um eine HÖHENDIFFERENZ handelt und nicht um eine Knotenanzahl - diese Verwechslung ist der häufigste Fehler des Abschnitts.

Repariert wird immer am UNTERSTEN unbalancierten Knoten auf dem Weg von der eingefügten Stelle zur Wurzel. Vier Fälle sind zu unterscheiden, benannt nach der Richtung der beiden Schritte zum neuen Knoten: Links-Links und Rechts-Rechts sind gerade Ketten und werden mit einer EINFACHEN Rotation behoben; Links-Rechts und Rechts-Links bilden einen Knick und brauchen eine DOPPELROTATION, also zwei aufeinanderfolgende einfache Rotationen in entgegengesetzte Richtungen.

Eine Rotation hängt drei Teilbäume um, ohne die Suchbaumordnung zu verletzen - das ist ihre entscheidende Eigenschaft. Bei einer Rechtsrotation um den Knoten

y

mit linkem Kind

x

wird

x

zur neuen Wurzel des Teilbaums,

y

wird sein rechtes Kind, und der bisherige rechte Teilbaum von

x

wird zum neuen linken Teilbaum von

y

. Die Inorder-Traversierung liefert vorher und nachher dieselbe Folge - und genau daran lässt sich die Korrektheit in der Prüfung belegen.

Der Aufwand bleibt beherrschbar: Eine Rotation kostet konstante Zeit, und nach einer Einfügung genügt höchstens eine (Doppel-)Rotation, um die Balance im ganzen Baum wiederherzustellen. Beim Löschen können dagegen bis zur Wurzel hinauf mehrere Rotationen nötig werden. In jedem Fall bleibt die Höhe eines AVL-Baums mit

n

Knoten in

O(\log n)

, und damit sind Suchen, Einfügen und Löschen alle logarithmisch.

Für die Prüfung lohnt ein festes Vorgehen: einfügen wie im gewöhnlichen Suchbaum, dann von der neuen Stelle zur Wurzel zurückgehen und die Balancefaktoren nachrechnen, den ersten Knoten mit Betrag 2 bestimmen, den Fall LL, RR, LR oder RL benennen, rotieren und zum Schluss die Inorder-Folge zur Kontrolle abschreiben. Wer den Fall ausdrücklich benennt, bevor er zeichnet, verwechselt Einfach- und Doppelrotation nicht mehr.

Vokabeln

→ Kartei

BalancefaktorHöhe des linken minus Höhe des rechten Teilbaums; erlaubt sind $-1$, $0$ und $+1$.
EinfachrotationEine Umhängeoperation; sie behebt die Fälle LL und RR.
DoppelrotationZwei entgegengesetzte Rotationen; sie behebt die Knickfälle LR und RL.
EntartungVerfall eines Suchbaums zur Liste bei ungünstiger Einfügereihenfolge.
Höhe eines BaumsLänge des längsten Weges von der Wurzel zu einem Blatt.
SelbstbalancierungAutomatische Wiederherstellung der Ausgeglichenheit nach jeder Änderung.

Balancefaktor eines AVL-Knotens

bf(v) = h(\text{links}(v)) - h(\text{rechts}(v)), \quad bf(v) \in \{-1,\,0,\,+1\}

$h$ bezeichnet die HÖHE des jeweiligen Teilbaums, nicht seine Knotenzahl. Sobald ein Betrag von 2 auftritt, ist der Knoten unbalanciert und es wird rotiert.

Obere Höhenschranke des AVL-Baums

h_{\text{AVL}} \leq 1{,}44\,\log_{2}(n+2)

Die Schranke zeigt, dass ein AVL-Baum höchstens rund 44 % höher wird als ein perfekt ausgeglichener. Damit bleiben Suchen, Einfügen und Löschen garantiert in $O(\log n)$ - anders als beim einfachen Suchbaum.

Musterbeispiel

LL-Imbalance durch Rechtsrotation beheben

Füge 3, 2, 1 in einen leeren AVL-Baum ein und stelle die Balance wieder her.

Schritt 1 - 3 einfügen
Wurzel = 3, Balancefaktor 0. Baum ist balanciert.
Schritt 2 - 2 einfügen
2 < 3, wird linkes Kind. Balancefaktor von 3 ist $+1$ (linke Höhe 1, rechte 0). Noch zulässig.
Schritt 3 - 1 einfügen
1 < 3, 1 < 2, wird linkes Kind von 2. Balancefaktor von 3 ist nun $+2$ - Verletzung. Erste zwei Kanten gehen links-links: LL-Fall.
Schritt 4 - Rechtsrotation an 3
Knoten 2 wird neue Wurzel; 1 bleibt linkes Kind, 3 wird rechtes Kind von 2.
Schritt 5 - Prüfung
Inorder vorher 1,2,3 und nachher 1,2,3 - Ordnung erhalten. Alle Balancefaktoren sind 0.

Ergebnis: Nach der Rechtsrotation ist 2 die Wurzel mit Kindern 1 und 3; der Baum ist mit Höhe 1 wieder balanciert.

Musterbeispiel

LR-Fall: Doppelrotation

Füge 5, 2, 4 in einen leeren AVL-Baum ein und balanciere.

Schritt 1
5 als Wurzel; 2 als linkes Kind (bf von 5 = +1).
Schritt 2
4 > 2, also rechtes Kind von 2; 4 < 5. Balancefaktor von 5 wird $+2$ , erste Kanten links-rechts: LR-Fall.
Schritt 3 - Linksrotation an 2
Teilbaum 2-4 wird zu 4-2: 4 wird linkes Kind von 5, 2 wird linkes Kind von 4. Jetzt liegt der LL-Fall vor.
Schritt 4 - Rechtsrotation an 5
4 wird Wurzel; 2 linkes Kind, 5 rechtes Kind.

Ergebnis: Endbaum: Wurzel 4 mit Kindern 2 und 5; Inorder 2,4,5 bleibt korrekt, Baum balanciert.

Schritt-für-Schritt Erklärung3 Schritte

1
Ohne Balancierung entartet ein BST bei sortierten Daten zur Liste - genau das verhindern AVL-Bäume.
2
Der Balancefaktor ist die Höhendifferenz der Teilbäume; sobald er +-2 erreicht, wird rotiert.
AVL-Rechtsrotation nach LL-Imbalance
Abb.Einfügen von 1 erzeugt am Knoten 3 Balancefaktor +2 (LL-Fall); eine Rechtsrotation an 3 stellt die Balance her.
3
Merksatz: gerade Kette (LL/RR) eine Rotation, Knick (LR/RL) zwei Rotationen.

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Erkläre, warum ein unbalancierter Suchbaum zur Liste entarten kann, und beschreibe, wie ein AVL-Baum das verhindert. Führe an einem selbst gewählten Beispiel eine Rotation durch.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

LR und RL werden wie LL und RR behandelt; bei einem Knick ist eine Doppelrotation nötig.
Der Balancefaktor wird als Knotenanzahl statt als Höhendifferenz berechnet.
Nach der Rotation wird die Suchbaumordnung nicht geprüft; ein Teilbaum hängt am falschen Platz.
Es wird angenommen, jeder Suchbaum sei von selbst ausgeglichen; eine sortierte Einfügefolge entartet ihn zur Liste.
Repariert wird am obersten statt am untersten unbalancierten Knoten.

Aktive Wiederholung

Füge nacheinander 10, 20, 30 in einen anfangs leeren AVL-Baum ein. Bestimme nach jedem Schritt den Balancefaktor der Wurzel, identifiziere den Imbalance-Fall und führe die nötige Rotation durch.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Open Data Structures - Scapegoat & balanced trees (Pat Morin)

Heaps und Prioritätswarteschlangen#

~5 Min LesezeitStandardINF-DS-2.1INF-DS-2.2

Min-Heap als Baum und als Array

Abb. 9Min-Heap: jeder Elternknoten ist kleiner als seine Kinder. Die Array-Einbettung nutzt Indizes 2i+1 und 2i+2 für die Kinder.

Eine Prioritätswarteschlange beantwortet eine einzige Frage effizient: Welches Element hat gerade die höchste Priorität? Ein sortiertes Array kann das in konstanter Zeit, braucht aber

O(n)

zum Einfügen; eine unsortierte Liste fügt in

O(1)

ein, sucht aber in

O(n)

. Der Heap löst beides in

O(\log n)

und ist deshalb die Standardimplementierung - unter anderem im Dijkstra-Algorithmus und in jedem Betriebssystem-Scheduler.

Ein Heap ist ein VOLLSTÄNDIGER Binärbaum, der die Heap-Bedingung erfüllt: Beim Min-Heap ist jeder Knoten kleiner oder gleich seinen Kindern, beim Max-Heap größer oder gleich. Das ist eine deutlich schwächere Forderung als beim Suchbaum - zwischen Geschwistern gilt keinerlei Ordnung. Daraus folgt unmittelbar: Eine Traversierung des Heaps liefert KEINE sortierte Folge; das leistet nur der Suchbaum per Inorder.

Weil der Baum vollständig ist, lässt er sich lückenlos in ein Array einbetten - ganz ohne Zeiger. Bei nullbasierter Zählung hat der Knoten mit Index

i

die Kinder

2i+1

und

2i+2

und den Elternknoten

\lfloor\tfrac{i-1}{2}\rfloor

. Diese drei Formeln sind der praktische Kern des Abschnitts und werden regelmäßig abgefragt; die Wurzel und damit das Minimum steht immer an Index 0.

Beim Einfügen wird das neue Element hinten angehängt und dann per SIFT-UP so lange mit seinem Elternknoten getauscht, bis die Heap-Bedingung wieder gilt. Beim Entnehmen des Minimums wird die Wurzel zurückgegeben, das LETZTE Element an ihre Stelle gesetzt und per SIFT-DOWN mit dem jeweils kleineren Kind getauscht, bis es passt. Der Umweg über das letzte Element ist nötig, damit der Baum vollständig bleibt - zöge man stattdessen ein Kind hoch, entstünde eine Lücke.

Beide Operationen laufen entlang eines Weges von der Wurzel zu einem Blatt und kosten deshalb

O(\log n)

. Bemerkenswert ist dagegen der Aufbau eines Heaps aus einem vorhandenen Array: Ruft man sift-down von der Mitte des Arrays rückwärts bis zur Wurzel auf, kostet das insgesamt nur

O(n)

und nicht

O(n\log n)

. Der Grund ist, dass die allermeisten Knoten nahe den Blättern liegen und dort nur wenige Schritte sinken können.

Daraus ergibt sich Heapsort: erst den Heap in

O(n)

aufbauen, dann

n

-mal das Minimum entnehmen. Das Verfahren sortiert in

O(n\log n)

und kommt dabei ohne Zusatzspeicher aus - anders als Mergesort. Sein Preis ist die fehlende Stabilität und ein ungünstigeres Cache-Verhalten, weshalb in der Praxis meist trotzdem Quicksort-Varianten verwendet werden.

Vokabeln

→ Kartei

HeapVollständiger Binärbaum mit Heap-Bedingung zwischen Eltern und Kindern.
Min-HeapHeap, in dem jeder Knoten kleiner oder gleich seinen Kindern ist.
sift-upAufsteigen eines neu eingefügten Elements durch Tausch mit dem Elternknoten.
sift-downAbsinken der neuen Wurzel durch Tausch mit dem kleineren Kind.
PrioritätswarteschlangeAbstrakter Datentyp mit Zugriff auf das Element höchster Priorität.
HeapsortSortierverfahren über Heap-Aufbau und wiederholtes Entnehmen; $O(n\log n)$ und in-place.

Array-Einbettung eines Binaer-Heaps

\text{Kind}(i) = 2i+1,\ 2i+2, \qquad \text{Elter}(i) = \left\lfloor \tfrac{i-1}{2} \right\rfloor

Die Formeln gelten bei nullbasierter Zählung; bei einsbasierter lauten sie $2i$ und $2i+1$ bzw. $\lfloor i/2\rfloor$ . Weil der Heap ein vollständiger Baum ist, entsteht im Array keine Lücke und es werden keine Zeiger gebraucht.

Musterbeispiel

Min-Heap aufbauen und extract-min

Füge 7, 3, 9, 1, 5 in einen leeren Min-Heap ein und entnimm danach das Minimum.

Schritt 1 - 7, 3 einfügen
[7]; dann 3 ans Ende -> [7,3], 3<7 also sift-up -> [3,7].
Schritt 2 - 9 einfügen
[3,7,9]; 9>3, kein sift-up nötig.
Schritt 3 - 1 einfügen
[3,7,9,1]; 1 an Index 3, Elter Index 1 = 7, 1<7 -> tauschen -> [3,1,9,7]; jetzt 1<3 -> tauschen -> [1,3,9,7].
Schritt 4 - 5 einfügen
[1,3,9,7,5]; 5 an Index 4, Elter Index 1 = 3, 5>3 -> kein Tausch. Heap fertig.
Schritt 5 - extract-min
Wurzel 1 entnehmen; letztes Element 5 an die Wurzel -> [5,3,9,7]; sift-down: kleineres Kind ist 3 (Index 1), 5>3 -> tauschen -> [3,5,9,7]. Heap-Eigenschaft erfüllt.

Ergebnis: Min-Heap vor Entnahme: [1,3,9,7,5]; extract-min liefert 1, danach [3,5,9,7].

Schritt-für-Schritt Erklärung3 Schritte

1
Ein Heap speichert ein Minimum (oder Maximum) so, dass es immer in konstanter Zeit verfuegbar ist.
Min-Heap als Baum und als Array
Abb.Min-Heap: jeder Elternknoten ist kleiner als seine Kinder. Die Array-Einbettung nutzt Indizes 2i+1 und 2i+2 für die Kinder.
2
Weil der Baum vollständig ist, passt er luckenlos in ein Array - Zeiger sind unnötig.
3
insert wandert mit sift-up nach oben, extract-min repariert mit sift-down nach unten.

SRDP-Aufgaben

SelbsttestAus der Fragenbank6 Punkte

Aufgabenstellung

Erkläre den Aufbau eines Binaer-Heaps und seine Array-Einbettung. Beschreibe insert und extract-min und nenne eine typische Anwendung als Prioritätswarteschlange.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Die Indexformeln werden vertauscht; Kinder stehen bei $2i+1$ und $2i+2$ , der Elternknoten bei $\lfloor\tfrac{i-1}{2}\rfloor$ .
Es wird angenommen, die Traversierung eines Heaps liefere eine sortierte Folge; das leistet nur der Suchbaum per Inorder.
Beim extract-min wird direkt ein Kind hochgezogen statt das letzte Element an die Wurzel gesetzt; der Baum verliert seine Vollständigkeit.
sift-up und sift-down werden verwechselt; insert nutzt sift-up, extract nutzt sift-down.
build-heap wird mit $O(n\log n)$ angegeben; durch die Verteilung der Knoten ist es $O(n)$ .

Aktive Wiederholung

Füge die Werte 7, 3, 9, 1, 5 nacheinander in einen anfangs leeren Min-Heap ein und gib nach jedem Einfügen die Array-Darstellung an. Führe anschließend ein extract-min durch.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: OpenDSA - Heaps and Priority Queues (Virginia Tech)