Kapitel 4: Dynamische Datenstrukturen
Datenstrukturen ermöglichen die effzientere Umsetzung von Algorithmen und den schnelleren Zugriff auf Informationen. In diesem Kapitel betrachten wir Aufgabenstellungen, die sich aus der dynamischen Verwaltung von Daten ergeben, die sich insbesondere durch Einfügen und Löschen ergeben.
Vorlesung 11
- Datum: Dienstag, 05.12.2017
- Inhalt: Grundoperationen; Stapel und Warteschlange; Verkettete Listen; Binäre Suche
- Folien: HIER (PDF, 6MB)
- Weitere Links:
Wikipedia über Listen
Wikipedia über binäre Suchbäume
Vorlesung 12
- Datum: Mittwoch, 06.12.2017
- Inhalt: Binäre Suchbäume
- Folien: HIER (PDF, 4MB)
- Weitere Links:
Ein 20-Minuten Video zu binären Suchbäumen auf Englisch mit indischem Akzent (Teil 1, 20 min)
Ein anderes Video mit Java-Code und amerikanischem Akzent (Teil 1, 14min)
Große Übung 4
- Datum: Donnerstag, 07.12.2017
- Inhalt: Wiederholung der asymptotischen Notationen und konvexe Hülle (als Zusatzmaterial, da zeitlich nicht geschafft)
- Folien: HIER (PDF, 1.6MB)
Vorlesung 13
- Datum: Dienstag, 12.12.2017
- Inhalt: Andere dynamische Datenstrukturen
- Folien: HIER (PDF, 6.7MB)
- Weitere Links:
Wikipedia über Rot-Schwarz-Bäume
Wikipedia über B-Bäume
Wikipedia über Heaps
Wikipedia über Speicherhierarchien
Home Page von Michael Bender
Animation diverser Algorithmen und Datenstrukturen
Vorlesung 14
- Datum: Dienstag, 19.12.2017
- Inhalt: Höhe von AVL-Bäumen
- Skript: HIER (PDF, 19MB)
Vorlesung 15
- Datum: Mittwoch, 20.12.2017
- Inhalt: Dynamische Operationen auf AVL-Bäume; Fibonacci-Zahlen, Weihnachtslied
- Folien:
HIER (PDF, 38MB)
Liedtext - Weitere Links:
Wikipedia über AVL-Bäume
Gemeine Schafgarbe: Eine Pflanze, deren Blütenstand aussieht wie ein AVL-Baum
Wikipedia über Rotation in Suchbäumen (englisch)
Wikipedia über Fibonacci-Zahlen
Fibonacci Numbers and Nature: Seite mit vielen Bildern und Beziehungen
Fibonacci Numbers in Nature: Verschiedene Blüten und Pflanzen (viele davon in der Vorlesung verwendet!)
Dr. Steel's Fibonacci Sequence ("Clickin' and tickin' with the equation of phi!" - "Make me Fibonacci!" - Rappin' for the sake of science...)
Große Übung 5
- Datum: Donnerstag, 21.12.2017
- Inhalt: Binäre Suchbäume und AVL-Bäume
- Folien: HIER (PDF, 5.1MB)
- Notizen:Einfügen, Löschen, Fälle bei Rotationen, Logarithmisch viele Rotationen (ACHTUNG: Diese Notizen sind mit vorsicht zu genießen. Sie sind spontan entstanden, enthalten kaum Details und verraten nicht, was abseits dieser Bilder geschehen ist.)
