Kapitola 1
Státnice - Dynamizace datových struktur

1.1 Úvod

Mnoho datových struktur podporuje velice efektivní operaci MEMBER, ale nemá operace INSERT a DELETE. Úkolem dynamizace je právě tyto operace do jakékoliv obecné struktury co nejefektivněji doplnit.

Zobecněný vyhledávací problém

Zobecněný vyhledávací problém je libovolná funkce – pro prvek a nějakou množinu vrací nějakou hodnotu.

Struktura je statická struktura řešící vyhledávací problém (neboli S-struktura) , je-li dán algoritmus, který pro zkonstruuje datovou strukturu a algoritmus, který pro a spočte .

Struktura je semidynamická, pokud navíc existuje algoritmus, který pro a zkonstruuje S-strukturu .

Struktura je dynamická, pokud navíc existuje algoritmus, který pro a zkonstruuje S-strukturu .

Ve všech následujících operacích budeme uvažovat jen rozložitelný vyhledávací problém:

- Vyhledávací problém je rozložitelný, pokud existuje binární operace na univerzu taková, že pro disjunktní a platí .

To platí pro situaci, která nás nejvíc zajímá – pokud funkce provádí operaci MEMBER nad nějakou datovou strukturou. Jiné problémy (patří do konvexního obalu množiny?) ale rozložitelné nejsou.

Navíc budeme předpokládat, že funkce lze spočítat v konstantním čase. Označme

- čas na vyčíslení , pokud

- paměťový prostor potřebný k reprezentaci -prvkové množiny

- čas na vytvoření struktury pro

Pro asymptotické odhady budeme předpokládat, že funkce , a jsou neklesající.

1.2 Semidynamizace

Vytvoříme semidynamickou strukturu, jejíž čas operace INSERT bude velmi rychlý a navíc se nám moc nepokazí doba pro provedení operace MEMBER. Základní idea je podobná jako v binomiálních haldách – roztrháme reprezentovanou množinu na sadu disjunktních podmnožin o velikosti (takové množiny jsou neprázdné pro odpovídající jedničkám v binárním zápisu čísla .

Formálně budeme mít spojový seznam S-struktur odpovídajících množinám , potom seznam spojových seznamů , které obsahují prvky jednotlivých množin, a nakonec pomocnou dynamickou strukturu (např. binární vyhledávací strom). To všechno dohromady zjevně vyžaduje jen paměti (celkem reprezentujeme pořád stejně prvků a vyhledávací stromy i spojáky jsou ).

Struktura se používá k “rychlému” testování před INSERTem, zda nechceme vkládat prvek, který už v množině máme, případně před DELETEM, jestli nechceme mazat neexistující prvek. Pro jednoduchost to v popisech operací vynecháme.

Operace MEMBER

Operace MEMBER potom projde všechny neprázdné množiny a zavolá MEMBER na nich. Výsledek spojí za pomoci funkce .

To celkem dává složitost MEMBERu , protože hledáme v max. dílčích množinách.

Protože jakékoliv mocniny rostou rychleji než logaritmus, platí, že pokud pro nějaké , pak je operace MEMBER .

Operace INSERT

Operace INSERT najde nejmenší takové, že . Potom vezme všechny (ty jsou neprázdné) a spolu s vkládaným prvkem je slije do jedné množiny (zahodí S-struktury pro všechna , zkonkatenuje spojáky a na jejich základě zkonstruuje novou S-strukturu ). Nová množina má správný počet prvků, protože .

V odhadu amortizované složitosti využijeme fakt, že S-struktura pro se tvoří jen tehdy, když existují S-struktury pro všechny . Tj. S-struktura o velikosti prvků se konstruuje znovu až po dalších INSERTech. Amortizovaně tak vychází :

.

Podobně jako pro MEMBER platí, že pokud pro nějaké , pak je složitost operace INSERT .

Operace INSERT se zaručeným nejhorším časem

Protože někdy nestačí mít INSERT rychlý amortizovaně, byla vytvořena jeho varianta, která zaručuje rozumnou rychlost i v nejhorším případě. Dělá se to prostým rozložením potřebných operací do všech volání. Musíme ale povolit i požadavky na naši strukturu – místo max. jedné množiny pro každou velikost odpovídající mocnině dvou budeme mít max. 4 takové množiny , z nichž poslední navíc bývá zkonstruovaná jen částečně (“rozpracovaná”).

Označme počet množin jako , přičemž , pokud neexistuje žádná množina velikosti . Algoritmus potom vypadá následovně:

1. Vytvoří se jednoprvková a zvýší (tj. i odpovídající S-struktura)

2. Pro první souvislý úsek, kde :

1. Provedeme dalších konstrukce S-struktury

2. Pokud jsme tím tuto S-strukturu dotvořili, vezmeme první dvě struktury “o patro níž” ( a ) a připravíme je prvním krokem k sloučení. Zároveň je odtud odebereme a přečíslujeme zbylé. Jejich započaté sloučení přidáme na úroveň .

3. Pokud jsme v posledním kroku (, t.ž. ) vytvořili druhou strukturu stejné velikosti na nejvyšším dosaženém “patře”, připravíme první krok sloučení těchto dvou největších struktur, přemístíme jejich započaté sloučení “o patro výš” a odebereme původní struktury.

Díky tomu, že počet kroků volíme tak šikovně, vždycky dotvoříme strukturu právě včas na to, abychom mohli vytvářet další stejné velikosti. Navíc, protože se provede jen kroků pro každé , odpovídá složitost v nejhorším případě amortizované složitosti původní operace INSERT.

1.3 Dynamizace

Při úplné dynamizaci navíc požadujeme efektivní algoritmus DELETE. Přidáme další předpoklad, a to, že na naší původní S-struktuře existuje operace FAKE-DELETE (ta spočívá v označení nějakého prvku jako “smazaného”, aniž by se smazal skutečně – dál tedy zabírá místo a prodlužuje operace).

Základní ideou oproti semidynamizaci navíc je, že se budeme snažit za každou cenu zajistit, aby všechny naše pomocné S-struktury stále obsahovaly alespoň osminu “nesmazaných” prvků a přestavovat je až poté, co počet “smazaných” překročí tuto mez. Formálně naše S-struktury reprezentují vlastně množiny , kde (a ).

Asymptoticky tak zaručíme, že množin (a pomocných S-struktur) bude stále jen logaritmicky mnoho a paměťové nároky taky zůstávají asymptoticky stejné. Struktura je tedy stejná jako pro (základní) dynamizaci. Navíc jsou nyní spojové seznamy prvků přímo provázané s S-strukturami (protože už nepoznáme podle velikosti seznamu, ke které S-struktuře vlastně patří).

Operace MEMBER pak pracuje úplně stejně, jen nakonec zkontroluje, zda nalezený prvek nebyl označen jako “smazaný” (a případně ho pak nevrátí).

Operace INSERT

Algoritmus operace INSERT() je následující:

1. Najdi nejmenší takové, že .

2. Vytvoříme (včetně S-struktury a spojáku). To splňuje požadavky na velikost , jinak by pro nebylo nejmenší.

3. Položíme pro .

Díky zachovávané minimální velikosti vytvářené množiny máme složitost amortizovaně stejnou jako v případě semidynamizace.

Operace DELETE

Odebrání prvku z naší dynamické struktury vypadá následovně:

1. Odstraníme ze spojáku

2. Vyřešíme čtyři různé případy podle velikosti množiny , která obsahuje prvek :

1. Je-li jen jednoprvková, prostě zahodím struktury s ní spojené.

2. Je-li (tj. ještě mám víc než osminu prvků “platných”), provedeme pouze FAKE-DELETE.

3. Je-li buď prázdná, nebo dost velká (), můžeme ji s prohodit. Pro “nové” pak vytvoříme novou S-strukturu.

4. Je-li neprázdná, ale moc malá na prohození s , potom je určitě můžeme sloučit a získáme novou množinu, která splňuje velikostní omezení pro . Pro ni vyrobíme novou S-strukturu.

Amortizovaná složitost celé operace DELETE je , kde je čas potřebný na operaci FAKE-DELETE a je potřeba na vyhledání prvku. Odhadneme, kolikrát se dělá skutečné přestavění S-struktur. Pokud , pak DELETE může nově vytvořit jen nebo . Z jejich podmínek velikosti (v algoritmu) vidíme, že mezi dvěma DELETE pro stejné (přičemž ) se musí provést aspoň -krát FAKE-DELETE (a libovolný počet DELETE na jiných množinách). Amortizovaná složitost vytváření S-struktur tak vychází:

I se současně prováděnými operacemi DELETE se amortizovaná složitost operací INSERT zachovává. Aby INSERT vytvořil podruhé strukturu pro , musí opět nastat . Protože DELETE nikdy nevytvoří strukturu s víc než polovinou skutečně zaplněnou, musí se do té doby provést aspoň INSERTů, čímž získáme stejnou situaci jako u semidynamizace.

_____________________________________________________________________________________________________________________________________________________