INF-DS - Datenstrukturen — Informatik · Matura-Zusammenfassung

Arrays, Listen, Stack und Queue#

BasisINF-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).

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.

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 verwechselt (LIFO vs. FIFO).
Annahme, dass Linked List effizienteren Random-Access als Array hat.
Bei Array-Implementierung von Queue wird das "Verschieben" beim dequeue vergessen oder das Ring-Buffer-Konzept nicht erklärt.

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?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

Bäume - BST, AVL und Heap#

StandardINF-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.

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.

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

Höhe eines BST mit n Knoten

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 mit Preorder verwechselt.
Löschen eines BST-Knotens mit zwei Kindern nicht über Inorder-Nachfolger/Vorgänger gelöst.
Heap wird mit BST verwechselt (Heap ist nicht sortiert in Traversierung).

Aktive Wiederholung

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

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

Hashtabellen und Kollisionsstrategien#

VertiefungINF-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 + α).

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).

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).

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.

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

Lastfaktor und erwartete Suchzeit in einer Hashtabelle

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

Hashfunktion als injektiv angenommen.
Lastfaktor nicht überwacht -> $O(n)$ Verschlechterung.
Probing-Strategie nicht eindeutig (Linear vs. Quadratisch vs. Double Hashing) erklärt.

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.

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)#

VertiefungINF-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.

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.

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

Maximale Kantenzahl im einfachen ungerichteten Graphen

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 verwechselt (Queue vs. Stack).
Dijkstra mit negativen Kantengewichten anwenden (-> falsch; Bellman-Ford verwenden).
Adjazenzmatrix für dünne Graphen wählen.

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.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

Selbstbalancierung - AVL-Rotationen#

VertiefungINF-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 AVL-Baum ist ein BST mit der Balancebedingung: für jeden Knoten gilt

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

(Balancefaktor in

\{-1,\,0,\,+1\}

).

Wird die Bedingung beim Einfügen/Löschen verletzt (

|bf| = 2

), stellen Rotationen die Balance in

O(1)

wieder her.

Vier Fälle: LL (Rechtsrotation), RR (Linksrotation), LR (Links-Rechts-Doppelrotation), RL (Rechts-Links-Doppelrotation).

Die Fallunterscheidung richtet sich nach der Richtung der ersten zwei Kanten vom unbalancierten Knoten zum neu eingefügten Blatt.

Eine Rotation verändert die Wurzel des betroffenen Teilbaums, bewahrt aber die BST-Ordnung (Inorder bleibt gleich).

Durch die Balance bleibt die Höhe stets

h \leq 1{,}44 \cdot \log_{2}(n+2)

; alle Operationen sind garantiert

O(\log n)

.

Alternativen mit ähnlicher Garantie: Rot-Schwarz-Bäume (weniger strikt balanciert, dafür weniger Rotationen) und B-Bäume (für externe Speicher/Datenbanken).

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

Balancefaktor eines AVL-Knotens

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

Obere Höhenschranke des AVL-Baums

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/RL mit LL/RR verwechselt: bei Knick (zickzack) ist eine Doppelrotation nötig, nicht eine Einfachrotation.
Balancefaktor als Knotenanzahl statt als Höhendifferenz berechnet.
Nach der Rotation BST-Ordnung nicht geprüft; Kinder falsch umgehängt.
Annahme, dass jeder BST automatisch balanciert sei - sortierte Einfügefolge entartet ohne Selbstbalancierung zur Liste.

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.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

Heaps und Prioritätswarteschlangen#

StandardINF-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.

Ein Binaer-Heap ist ein vollständiger Binärbaum mit Heap-Eigenschaft: bei einem Min-Heap ist jeder Knoten

\leq

seine Kinder, beim Max-Heap

\geq

.

Wegen der Vollständigkeit lässt sich der Heap luckenlos in ein Array einbetten: Kinder von Index

i

liegen bei

2i+1

und

2i+2

, der Elternknoten bei

\lfloor (i-1)/2 \rfloor

.

Operationen: insert (einfügen am Ende, dann sift-up) und extract-min/max (Wurzel entnehmen, letztes Element nach oben, dann sift-down) - beide

O(\log n)

.

Das Minimum/Maximum steht stets an der Wurzel und ist in

O(1)

ablesbar (peek).

Ein Heap ist nicht vollständig sortiert: nur die Eltern-Kind-Relation gilt, Geschwister sind unsortiert.

Build-Heap aus

n

Elementen kostet überraschend nur

O(n)

(nicht

O(n \log n)

), wenn man von unten nach oben sift-down anwendet.

Hauptanwendung: Prioritätswarteschlange (Dijkstra, A, Huffman-Codierung, Ereignissimulation) und Heapsort* (

O(n \log n)

, in-place).

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

Array-Einbettung eines Binaer-Heaps

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

Index-Formeln vertauscht (Kind $2i+1$ vs. Elter $\lfloor (i-1)/2 \rfloor$ ).
Annahme, ein Heap liefere bei Traversierung eine sortierte Folge (das tut nur der BST per Inorder).
Beim extract-min nicht das letzte Element an die Wurzel gesetzt, sondern direkt das kleinere Kind hochgezogen ohne Vollständigkeit zu wahren.
sift-up und sift-down verwechselt (insert nutzt sift-up, extract nutzt sift-down).

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 anschliessend ein extract-min durch.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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