B-Bäume und Rot-Schwarz-Bäume

Rot-Schwarz-Bäume sind eine Weiterentwicklung von Binär-Bäumen, auf der alle Operationen mit logarithmischem Zeitaufwand durchführbar sind. B-Bäume sind Bäume mit mehr als zwei Nachfolgern pro Knoten, die besonders geeignet sind, um in großen Datensätzen die Zahl der Plattenzugriffe zu minimieren.

Die Ausarbeitung war Teil eines Referats im Grundstudium-Seminar über Algorithmen aus verschiedenen Anwendungsgebieten. Sie enthält Informationen über die genannten Baumarten sowie Grundzüge der Implementierung von Rot-Schwarz-Bäumen in der funktionalen Programmiersprache Haskell.

Der Vortrag entstand gemeinsam mit Falk Schubert im Rahmen des Seminars “Streifzüge durch die Algorithmik”.