Datenstrukturen realisieren abstrakte Datentypen so, dass die Operationen der Datentypen besonders effizient ausgeführt werden können. Beispiele von Datenstrukturen sind balancierte Bäume und Hashtabellen. Datenstrukturen können mit objektorientierten Programmiersprachen als Klassen zur Verfügung gestellt werden. In der Vorlesung werden verschiedene Datenstrukturen behandelt, die über die in Informatik III behandelten Datenstrukturen hinausgehen, unter anderem die sogenannten dynamischen Bäume von Sleator und Tarjan, Range-Query-Strukturen und Suffix-Bäume.
