Differences
This shows you the differences between two versions of the page.
— |
fischer:abschlussarbeiten:comparison_yfast_veb [2019-03-20 10:36] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== 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]] |