Redwan Albunni:
Implementierung und Analyse von Zip-Zip-Bäumen - Eine praktische Validierung zufallsbasierter Suchbäume mit reduziertem Speicherbedarf und balancierter Tiefe
Kurzbeschreibung
In meiner Bachelorarbeit untersuche ich sogenannte Zip-Zip-Bäume, eine neuartige Variante zufallsbasierter Suchbäume, die eine sehr ausgeglichene Baumtiefe bei gleichzeitig geringem Speicherbedarf versprechen. Dazu habe ich verschiedene Varianten (u. a. statische, Just-in-Time- und gewichtete Zip-Zip-Bäume) implementiert und ihre Eigenschaften experimentell im Hinblick auf Baumhöhe, durchschnittliche Tiefe, Einfügezeit und Speicherverbrauch untersucht. Diese Ergebnisse vergleiche ich mit klassischen Strukturen wie Zip-Trees, Treaps, AVL- und Rot-Schwarz-Bäumen. Ziel der Arbeit ist es zu zeigen, inwieweit die theoretischen Vorteile der Zip-Zip-Bäume in praktischen Implementierungen bestätigt werden und in welchen Anwendungsszenarien sie besonders geeignet sind.