1. Domácí úkol - vyhledávání v splay-stromech

Čtěte prosím tuto stránku celou a pozorně.

Zadání

Implementujte vyhledávání ve splay-stromech.

Splay-stromy

Splay-strom je binární vyhledávací strom. Od obyčejného vyhledávacího stromu se liší jen odlišnou implementací operací, datové struktury jsou stejné.

Nejdůležitější implementací ve splay-stromě je operace SPLAY(x). Tato operace probíhá podle následujícího algoritmu:

1. Pokus o vyhledání vrcholu, který reprezentuje vstupní hodnotu x. Vyhledávání probíhá stejně jako v obyčejném stromě. Hodnota x může, ale nemusí být ve stromě přítomna. V případě nalezení vrcholu bude algoritmus dál pracovat s nalezeným vrcholem, jinak bude dál pracovat s posledním vrcholem navštíveným během vyhledávání.
2. Pomocí posloupnosti rotací je vrchol přenesen do kořene stromu.

Rotace ve splay-stromech

Při operaci SPLAY(x) mohou nastat tři druhy rotací:

1. Je-li otec vrcholu t kořen stromu, přesuneme t jednoduchou rotací do kořene.
2. Je-li vrchol t, otec t a děd t v jedné přímce, provedeme dvojitou rotaci tak, aby t zaujal místo děda a vrcholy byly opět v jedné přímce.
3. Jsou-li vrcholy t, otec t a děd t cik-cak, provedeme dvojitou rotaci tak, aby t byl mezi dědem a otcem.

Při každé rotaci se vrchol t dostane výš, nakonec tedy musí skončit v kořeni.

Operace vyhledávání prvku ve splay-stromech

Vyhledání prvku x probíhá tak, že se nejprve provede operace SPLAY(x) a potom se hodnota x porovná s hodnotou prvku reprezentovanou kořenem stromu. Je-li prvek x ve stromě, bude po operaci SPLAY(x) v kořeni.

Na stránce http://www.cs.technion.ac.il/~itai/Courses/ds2/framesplay/index.html můžete najít animovanou verzi operace MEMBER(x) (vyžaduje java-skript).

Formát vstupu a výstupu

Vaším úkolem bude doplnit kód do funkce function member(T: PTree;x : Integer) : Boolean; v unitě splay.pas. Hlavní program je v souboru main.pas, kde je umístěný kód pro načítání vstupních dat a kontrolu výsledného stromu. Výsledek kontroly je zapsán do souboru vysledek.txt.

Vstupní soubor vstup.txt je posloupnost trojic řádků. Každá trojice odpovídá jenomu testu. První řádek z trojice je posloupnost prvků, jejichž postupným přidáváním vznikne počáteční strom. Na druhém řádku je hodnota prvku, který se má najít a Boolean (reprezentovaný jako 0 nebo 1) s hodnotou správné návratové hodnoty funkce member. Na třetím řádku je posloupnost prvků odpovídající výpisu výsledného stromu po vyhledání prvku v preorderu.

Popis algoritmu, který máte implementovat, je jednoznačný. Výsledný strom musí mít identický tvar se stromem ze vstupního souboru.

Potřebné zdrojové soubory a testovací data najdete v souboru splay.tar.

Pravidla

• Nemodifikujte typ TTree.
• Při implementaci member nepoužívejte new.

Tipy

Vytvořte samostatnou proceduru splay.

Napište si pro ladící účely proceduru, která vám vypíše obsah stromu na obrazovku, jistě se vám bude hodit.

Poznámky

• Formát vstupu a výstupu je povinný, jeho nedodržení je považováno za chybu.
• Program kromě vstupního textového souboru nesmí požadovat žádná data (ani z klávesnice).
• Do programu prosím vložte komentář se svým jménem a příjmením.
• Řešení posílejte mailem na adresu hruska (zavináč) popelka (tečka) ms (tečka) mff (tečka) cuni (tečka) cz s předmětem zprávy PGM - splay a s přiloženým souborem splay.pas.
• Po odeslání mailu s domácím úkolem by vám měla přijít zpět zpráva s potvrzením příjmu.
• Neposílejte .exe soubory.
• V případě jakýchkoliv nejasností nebo problémů mi pošlete mail.

Termíny

Termín zadání: 21.3.2007.
Termín odevzdání: 8.4.2007 včetně.
Termín oprav: 15.4.2007 včetně.