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 12
- Datum: Dienstag, 10.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
Vorlesung 13
- Datum: Mittwoch, 11.12.2019
- Inhalt: Binäre Suche; Binäre Suchbäume
- Folien: HIER (PDF, 4MB)
- Weitere Links:
Binäre Suche bei Idea Instructions
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)
Große Übung 3
- Datum: Donnerstag, 12.12.2019
- Inhalt: Dynamische Datenstrukturen
- Folien: HIER
Vorlesung 14
- Datum: Dienstag, 17.12.2019
- Inhalt: Höhe von AVL-Bäumen
- Skript: HIER (PDF, 1MB>
Vorlesung 15
- Datum: Mittwoch, 18.12.2019
- Inhalt: Dynamische Operationen auf AVL-Bäume; Fibonacci-Zahlen, Weihnachtslied
- Folien:
HIER (PDF, 12MB)
Quiz mit Ergebnissen (PDF, 2MB)
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...)
Vorlesung 16
- Datum: 07.01.2020
- Inhalt: Andere dynamische Datenstrukturen
- Folien: HIER (PDF, 7.3MB)
- Weitere Links:
Wikipedia über Rot-Schwarz-Bäume
Einfügen in Rot-Schwarz-Bäume
Löschen aus Rot-Schwarz-Bäumen
Wikipedia über B-Bäume
Einfügen in B-Bäume
Löschen aus B-Bäumen
Wikipedia über Heaps
Wikipedia über Speicherhierarchien
Homepage von Erik Demaine
Homepage von Michael Bender
Animation diverser Algorithmen und Datenstrukturen