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

==== Beschreibung ====
[[https://en.wikipedia.org/wiki/Y-fast_trie|Y-Fast Tries]] und [[https://en.wikipedia.org/wiki/Van_Emde_Boas_tree|van Emde Boas (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 [[http://algo2.iti.kit.edu/dementiev/files/veb.pdf|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 [[staff:fischer|Johannes Fischer]] oder [[staff:kurpicz|Florian Kurpicz]]