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, 04.12.2018
- Inhalt: Grundoperationen; Stapel und Warteschlange; Verkettete Listen; Binäre Suche
- Folien: HIER (PDF, 4MB)
- Weitere Links:
Wikipedia über Listen
Wikipedia über binäre Suchbäume
Binäre Suche bei Idea Instructions
Vorlesung 12
- Datum: Mittwoch, 05.12.2018
- Inhalt: Binäre Suchbäume
- Folien: HIER (PDF, 4MB)
- Weitere Links:
Grundlage der Darstellung: Cormen als PDF; siehe Kapitel 12, "Binary Search Trees" (In der deutschen Ausgabe ist das ebenfalls Kapitel 12.)
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)
Vorlesung 13
- Datum: Dienstag, 11.12.2018
- Inhalt: Höhe von AVL-Bäumen
- Skript: HIER (PDF, 1MB>
- Weitere Links:
Der Donald-Trump-Tracker der Washington Post
Putin begrüßt MBS beim G20-Gipfel am 30.11.2018
Taggenauer Frontverlauf im Zweiten Weltkrieg
Der Film "Theresienstadt" bei IMDb
Der Film "Theresienstadt" bei Wikipedia
Kurt Gerron bei IMDb
Wikipedia zum Holocaust
Ein Album von einem Auschwitz-Besuch
Vorlesung 14
- Datum: Mittwoch, 12.12.2018
- Inhalt: Dynamische Operationen auf AVL-Bäume; Fibonacci-Zahlen, Weihnachtslied
- Folien:
HIER (PDF, 12MB)
Liedtext - Literatur:
Goodrich/Tamassia - Data Structures and Algorithms in Java
Elektronische Ausgabe der 4.Auflage; hier: Kapitel 10.2, Seiten 599ff.
- Weitere Links:
Wikipedia über AVL-Bäume
AVL-Baum bei Idea Instructions
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: Viele weitere Beispiele, z.B. auch in Stürmen
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, 13.12.2018
- Inhalt: Binäre Suchbäume, AVL-Bäume, TREE(n)
- Folien: HIER (PDF, 7.7MB)
Vorlesung 15
- Datum: Dienstag, 18.12.2018
- Inhalt: Andere dynamische Datenstrukturen
- Folien: HIER (PDF, 7.3MB)
- Weitere Links:
Wikipedia über Rot-Schwarz-Bäume
Wikipedia über B-Bäume
Wikipedia über Heaps
Wikipedia über Speicherhierarchien
Homepage von Erik Demaine
Homepage von Michael Bender
Animation diverser Algorithmen und Datenstrukturen
Fragestunde
- Datum: Mittwoch, 19.12.2018
- Inhalt: Fragestunde. Heaps, Wachstum von Funktionen und rekursive Algorithmen
- Notizen: HIER (Die erste Seite beschreibt nur den groben Inhalt bis Kapitel 4!)
