Datové struktury I - NTIN066 - ZS 2015/2016 - 3. úkol

Pravidla

• Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší „inspirace“.
• Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí „inspirací“. Výjimku tvoří odevzdání kódu.
• Úkol a možné postupy řešení můžete probírat s ostatními, avšak respektuje výše uvedené o nesdílení kódu. To znamená: společná diskuse je povolena, ale programujte sami.
• Povolená jsou řešení v jazycích C/C++ (doporučený jazyk), Java a C#.
• Používejte standardní konstrukce svého programovacího jazyka, ale už ne speciální knihovní funkce. Celou datovou strukturu musíte naprogramovat samostatně.
• Řešení, která nejsou ve shodě s těmito pravidly, nebudou hodnocená.

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 použijte už zkompilovaný generátor /afs/ms.mff.cuni.cz/u/b/babkm5am/ds1/hw3/splaygen dostupný v unixové laboratoři Rotunda. 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;
• -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.

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

Odevzdání

Pošlete e-mail s předmětem tvaru 'HW3-55973318' (t.j. HW3-studentské číslo) s těmito přílohami:

• zdrojový text, na kterém jste vše naměřili (pokud je složen z více souborů, zabalte je ZIPem nebo TARem do jednoho),
• PDF s grafy a komentáři.

Tělo e-mailu nechť obsahuje údaje podle tohoto vzoru:

Jmeno: Jiří Fink
Pseudonym pro vysledky na webu: Tomáš Marný
Cviceni: pondeli-12:20-lichy