Algorithmen & Datenstrukturen (AuD) Lab

🗺️ Kürzeste Wege: Dijkstra & BFS

Startknoten wählen und schrittweise die Priority Queue abarbeiten

Unbesucht Aktueller Knoten Final (abgeschlossen)

Komplexität: $\mathcal{O}((V + E) \log V)$ mit Fibonacci-Heap

Distanz-Array $d[v]$ & Vorgänger $\pi[v]$

Schritt 0

Knoten $v$	Distanz $d[v]$	Vorgänger $\pi$	Status

Min-Priority-Queue ($Q$)

Wähle Startknoten A und klicke auf „Schritt weiter“, um Dijkstra zu starten.

🌳 AVL-Baum: Höhenbalancierter Suchbaum

Balance-Faktor $BF(v) = h(\text{rechts}) - h(\text{links}) \in \{-1, 0, 1\}$

Klausur-Szenarien:

🔵 Zahl im Knoten = Schlüssel • Kleine Zahl oben = Balance-Faktor $BF$ Höhe $h \le 1.44 \log_2(n)$

Letzte ausgeführte Rotation

Keine Rotation erforderlich (Baum ist balanciert).

Ein AVL-Baum garantiert logarithmische Such-, Einfüge- und Löschzeiten $\mathcal{O}(\log n)$ durch automatische Rebalancierung nach jeder Operation.

Die 4 AVL-Rotationsfälle

1. LL (Links-Links): Einfügen in linken Teilbaum des linken Kindes $\to$ Einfache Rechtsrotation um Wurzel.

2. RR (Rechts-Rechts): Einfügen in rechten Teilbaum des rechten Kindes $\to$ Einfache Linksrotation um Wurzel.

3. LR (Links-Rechts): Einfügen in rechten Teilbaum des linken Kindes $\to$ Linksrotation an Kind, dann Rechtsrotation.

4. RL (Rechts-Links): Einfügen in linken Teilbaum des rechten Kindes $\to$ Rechtsrotation an Kind, dann Linksrotation.

📊 Sortier- & Rekursions-Simulator

QuickSort, MergeSort und HeapSort im direkten Vergleich

Vergleiche 0

Tausche / Writes 0

Rekursionstiefe 0

🧮 Master-Theorem Rechner

Für Rekursionsgleichungen $T(n) = a \cdot T(n/b) + \mathcal{O}(n^d)$

Teilprobleme $a$

Teiler $b$ ($b > 1$)

Aufwand-Grad $d$

Ergebnis & Master-Fall:

Fall 2: $a = b^d \implies 2 = 2^1$

$\mathcal{O}(n \log n)$

Der Aufwand auf jeder Rekursionsebene ist gleich groß. Typisches Beispiel: MergeSort.

🎯 Klausur-Quiz: Algorithmen & Datenstrukturen

Typische Verständnisfragen zu Komplexität, AVL-Bäumen und Graphen

0 / 5 Punkte

Frage 1 von 5

Welche Worst-Case-Laufzeit hat das Einfügen eines Elements in einen AVL-Baum mit $n$ Elementen?

🧭 A* Pathfinding Raster

Klicke auf das Raster, um Wände zu zeichnen

A* Heuristik

Der A*-Algorithmus nutzt eine Heuristik (Manhattan-Distanz), um den Kürzesten Weg effizienter als Dijkstra zu finden.

Startknoten

Zielknoten

Wand

Besucht

Kürzester Pfad

🔑 Hashing Simulator

Hash-Tabelle mit Array der Größe 11 (Linear Probing)

Hash Log

Tabelle initialisiert. Hashfunktion: h(x) = x mod 11.

Algorithmen & Datenstrukturen Lab