Praktischer Vergleich von van Emde Boas Trees und Y-Fast Tries

Beschreibung

Y-Fast Tries und van Emde Boa (vEB) Trees sind alternativen zu vergleichsbasierten Suchbäumen. In der Theorie haben beide Datenstrukturen bessere Anfragezeiten für die Operationen Suchen, Einfügen und Löschen. Für vEB Trees gibt es schon Implementierungen, die sich in der Praxis gut schlägt (siehe hier). Y-Fast Tries sind hingeben in der Praxis noch nicht betrachtet worden. Ziel dieser Arbeit ist die Implementierung eines Y-Fast Tries auf einer 64-Bit-ARchitektur und der experimentelle Vergleich mit vEB Trees und vergleichsbasierten Suchbäumen.

Typ

Bachelor- oder Masterarbeit.

Bearbeiter

Timo Putzer

Das sollten Sie mitbringen

  • Spaß an algorithmischen Problemstellungen
  • gute Programmierkenntnisse in C++

Betreuer

Bei Interesse wenden Sie sich bitte an Johannes Fischer oder Florian Kurpicz

 
Last modified: 2018-09-21 15:03 by Johannes Fischer
DokuWikiRSS-Feed