Datové struktury I - 2. úkol

Termín odevzdání: 13. listopadu 2016.
Způsob odevzdání: Odevzdáním na stránce https://kam.mff.cuni.cz/~ds1/.
Obecná pravidla: Prečtěte si je důkladně

Popis problému

Naimplementujte dvě varianty Splay stromů, standardní variantu z přednášky, kde se používají dvojité rotace, a naivní variantu, kde se místo dvojitých rotací použije při operaci Splay posloupnost jednoduchých rotací k přenesení zpracovávaného vrcholu do kořene. Jednoduchá rotace

Prozkoumejte chování obou datových struktur na testovacích datech vygenerovaných níže popsaným programem. Každý test začíná vložením určitého počtu N prvků pomocí operace Insert a po nich následuje posloupnost operací Find. Posloupnost operací Find zavisí na typu testu:

  • podmnožinový rovnoměrný test: operace Find vyhledává (rovnoměrně) náhodně zvolený prvek z určité podmnožiny vložených prvků velikosti T;
  • sekvenční test: specifická posloupnost operací Find.

Pro každý test změřte průměrnou délku cesty prošlé při operacích Find.

Generování dat

Pro vygenerování testovacích dat si stáhněte generátor. Spusťte ho s následujícími parametry:
  • -s XX, kde XX jsou poslední dvě číslice vašeho studentského čísla;
  • -t T, kde T je velikost vyhledávané podmnožiny;
  • -l, pokud chcete, aby vyhledávanou podmnožinou bylo posledních T prvků vložených do Splay stromu;
  • -b, pokud chcete vygenerovat data pro sekvenční test; jinak se generuje podmnožinový rovnoměrný.

Výstupem generátoru bude textový soubor, každý řádek popisuje jednu operaci na stromu:

  • # N : začátek testu pro množinu velikosti N – zrušte starý strom a založte nový (velikost množin se vám může hodit při kreslení grafů);
  • I X: vložení klíče X do stromu (pokud se klíč ve stromu už vyskytuje, operaci ignorujte);
  • F X: vyhledání klíče X ve stromu.

Na jedno spuštění generátor vytvoří sadu testů o velikostech cca 1000 až 1000000 prvků.

Výstupní grafy

Pro každý typ testu nakreslete graf závislosti průměrné délky cesty Find na velikosti množiny N:
  1. Pro strandardní verzi a podmnožinový test nakreslete do jednoho grafu šest křivek, každá pro jedno T z {10,100,1000,10000,100000,1000000}.
  2. Stejně jako předchozí, ale pro naivní implementaci Splay stromů.
  3. Spojený graf 1. a 2., kde budou tři křivky pro standardní i naivní implementaci pro T z {100,10000,1000000}.
  4. Pro standardní a naivní implementaci zakreslete do jednoho grafu průměrnou délku cesty při sekvenčním testu.

Vysvětlete tvar křivek a zdůvodnit rozdíly mezi chováním obou implementací stromů.

Příklad vstupu

# 3
I 1
I 2
I 0
F 1
F 0
F 2
# 4
I 2
I 3
I 0
I 1
F 2
F 0
F 2
F 3