Benjamin Bortfeld

Experimenteller Vergleich verschiedener binärer Suchbäume unter verschiedenen Abfragesequenzen

Betreuer: Prof. Dr. Wolfgang Mulzer
Abschluss: Diplom
Abgabedatum: 19.07.2012

Kurzbeschreibung

Binäre Suchbäume sind eine der wichtigsten Datenstrukturen der Informatik. Jeder Informatiker kennt die balancierten Varianten, wie den AVL-Baum oder den Rot-Schwarz-Baum, von denen die ältesten bereits in den 1960er Jahren entwickelt wurden. Doch auch in neuerer Zeit beschäftigt sich die Forschung mit binären Suchbäumen, um das Verwalten großer Datenmengen effizienter zu gestalten. Ein Forschungzweig beschäftigt sich dabei mit den dynamischen binären Suchbäumen. Das sind Bäume, die ihre Struktur auch bei Suchen ändern können. Zwei interessante dynamische Bäume wurden erst 2007 und 2010 vorgestellt: der Tango- und der Zipper-Baum. Sie versprechen in der Theorie eine gute Performance, aber praktische Untersuchungen zu ihnen gibt es nocht nicht. Aus diesem Grund wollen wir in dieser Arbeit Tango- und Zipper-Bäume experimentell untersuchen und mit anderen Bäumen vergleichen. Damit erhoffen wir uns, diese Bäume in Hinsicht auf ihre Laufzeit für ihren Einsatz unter realen Bedingungen besser einschätzen zu können. Da Tango- und Zipper-Bäume keine Möglichkeit bieten, Elemente einzufügen nachdem sie einmal aufgebaut wurden, beschäftigen wir uns nur damit zu untersuchen, wie effizient die Bäume für verschiedene Abfragesequenzen sind.