Vladan Majerech - NTIN067 Datové struktury 2

Last Modified: 25.4.2025

Valid HTML 4.01 Strict

Index

odkazy, přednáška 1, přednáška 2, přednáška 3, přednáška 4, přednáška 5, přednáška 6, přednáška 7, přednáška 8, přednáška 9, přednáška 10

Přednášky budu nahrávat, prosím připomínat, pokud bych zapomněl.

Odkazy na obdobné stránky

stránky mj, k předmětu z předchozích let, moje předloňské přednášky

Přednáška 1

Po přehledu probíraných témat a popisu používaného výpočetního modelu (zapomněl jsem zmínit konvenci, že používáme jako defaultní základ logaritmu dvojku) jsme začali řešit statické slovníky.

Po přehledu podobných struktur pro daný problém (používal jsem k popisu chování $O$, ale vhodnější by bylo $\Theta$) jsem nejprve ukázal metodu derandomizace na základě kriteriální funkce ... randomizovanou typicky se zhoršující konstantou 2 (jak v kriterální funkci tak v čase) a deterministickou nezhoršující kriteriální funkci, ale vyžadující volbu parametrů po bitech a vyhodnocování střední hodnoty zohledňující zafixované bity. Časová složitost deterministické varianty je násobena počtem volených bitů (základem je výpočet střední hodnoty kriteriální funkce).

Následně jsme probrali FKS1984 perfektní hašování s indirekcí. Stačil nám k tomu c-univerzální hešovací systém. A $n$ prvkovou množinu jsme bezkonfliktně zahešovali do tabulky velikosti $O(n)$ randomizovaně v čase $O(n)$ (evidentně neumím numericky počítat, pokud 4 prvky padnou na stejnou adresu, jedná se o $6={4 \choose 2}=4\cdot 3/2$ kolizí, nikoli 10 a $1={2 \choose 2}=2\cdot 1/2$ nikoli 2), s tím, že hešovací funkci spočteme v $O(1)$ s nejvýš dvěmi výpadky keší. Dvoustupňová hešovací funkce bude mít $O(n)$ parametrů. Vzhledem k bezkoliznosti je čtení v $O(1)$ worst case.

Pak jsme začali HMP2000 cestu k worst case času $O(n\log n)$ tvorby bezkonfliktní hašovací funkce metodou postupného zvětšování univerza (evidentně osvětlení tabule není příliš kompatibilní se schopnostmi kamery). Pro univerzum velikosti $2^{\log n+O(1)}$ je identita vyhovující hešovací funkcí.
Dalším krokem bylo rozšíření na univerzum velikosti $2^{2\log n+O(1)}$. Ukázali jsme si, jak čtverec rozměrů $cn\times cn=2^r\times 2^r$, $c>2$ s libovolnými $n$ hodnotami, můžeme xorováním řádků s nově volenými konstantami setřást tak, aby počet sloupcových konfliků klesl na $n/2$. Stejná metoda po transponování povede k tomu, že z $n/2$ řádkových konfliktů získáme sloupcově bezkonfliktní zobrazení, tedy cílovou hešovací funkci. To jsme zatím neukázali. Skončili jsme s tím, že jsme schopni vhodné konstanty volit i deterministicky po bitech tedy v celkovém worst case čase $O(n\log n)$. Příště nás čeká důkaz bezkonfliktosti po druhém průchodu a další rozšiřování univerza.

Přednáška 2

Vše nasvědčuje tomu, že druhá přednáška byla nahrána bez zvuku:(, každopádně bez osvětlení tabule je záznam čitelný po celou dobu. Čtyři roky stará nahrávka by měla být dostupná v SIS v informacích k předmětu. Věřím tomu, že je dostupná pro studenty, kteří mají předmět zapsaný. Kdyžtak mi dejte vědět, abych ji překopíroval jinam.

Dokončil jsem případ kvadratického univerza ukázáním, že tresholdy při průchodu počínající s nejvýš $n/2$ řádkovými konflikty budou menší než 1, tedy výsledná funkce po druhé transformaci vyjde bezkonfliktní. Dostáváme z řádkového rozměru určenou konstantu $a$ kterou xorujeme sloupec, tím je určena sloupcová konstanta $a'$ kterou xorujeme řádek a tím dostaneme unikátní adresu.

Pokračoval jsem rozšířením univerza na velikost $2^{O(\log n)}$, tedy polynomiální. Takové prvky můžeme vnímat jako konstantně dlouhé řetězce nad $n$-písmenou abecedou. Pokud $n$ prvkovou množinu takových slov uložíme jako komprimované trie (kde v uzlech evidueme podle kolikátého písmenka se větvíme), tak nám stačí $n$ listů (v nichž je evidovaný klíč pro kontrolu) a nejvýš $n-1$ vnitřních vrcholů. Dohromady nejvýš $2n-2$ orientovaných hran. Hrany trie můžeme evidovat v heš tabulce pod klíčem vrchol a písmeno. To je $2\log n+O(1)$ bitů, můžeme tedy pro uložení $2n-2$ prvkové množiny hran (k určení cílového vrcholu) použít předchozí techniku hešování. Výslednou adresu pak získáme průchodem trie vyžadující vyhledání nejvýš konstantně mnoho hran. Pokud bylo univerzum velké $O(n^c)$, budeme tak číst nejvýš $3c$ krát.

Před dalším zvětšováním univerza (v zapomněnce) jsme odbočili k deterministické technice R1995 volby hešovací funkce $(ax \mod 2^b)>\!>(b-s)$ (liché $a$) v čase $O(bn^2)$ postupnou volbou $b$ bitů parametru $a$ tak abychom nepřekročili očekávaný odhad počtu konfliktů.

Dalším krokem bylo univerzum velikosti $2^{o(\sqrt n)}$, kde jsme navíc znali masku $M$ s nejvýš $O(\log n)$ nenulovými bity tak, že pokud prvky množiny $S$ transformujeme pomocí bitového and s maskou $M$, tak dostaneme množinu stejné velikosti (tedy $n$). Trik byl rozdělit masku na konstantní počet podmasek $M_0$, ... $M_{c-1}$ každou s nejvýš $\log n/4$ nenulovými bity a pro průniky $S \cap M_i$ vytvořit FKS hešování s použitím Ramanovy metody volby hešovacích funkcí. Jednotlivé množiny jsou velké $O({\root 4 \of n})$, takže na vytvoření hešovacích pro výsledné množiny potřebujeme $b{\root 4 \of n}^2\in o(n)$ času. Nejspíš nemáme čas počítat $S\cap M_i$, ale místo toho vytvoříme hešovací funkci pro množinu odpovídající všem podmaskám masky $M_i$. Výsledná adresa je pro každou takovou masku $O(1)+\log n/4$ bitová. Pokud výsledné bity adres spojíme dohromady, dostaneme $O(\log n)$ bitů, takže se pohybujeme v univerzu které již umíme perfektně hešovat. Vzhledem k tomu, že se libovolné dva prvky množiny $S$ liší po maskování maskou $M$, liší se i v maskování některou z podmasek $M_i$. Proto se spojení adres bude v části odpovídající masce $M_i$ lišit, takže je tato transformace univerza bezkonfliktní.

Následně jsme pokračovali k univerzu velikosti $2^w$, s tím, že jsme opět měli masku $M$ s nejvýš $k=O(\log n)$ nenulovými bity tak, že pokud prvky množiny $S$ transformujeme pomocí bitového and s maskou $M$, tak dostaneme množinu stejné velikosti (tedy $n$). Ukázali jsme, jak je možno nalézt $C$ a $M'$ tak, abychom pomocí $(((x \cap M) * C) >\!> w) \cap M'$ přetransformovali množinu $S$ na $n$-prvkovou množinu $k^3$ bitového univerza s maskou $M'$ s $k$ nenulovými bity. Vzhledem k tomu, že $k^3\in o(\sqrt n)$ můžeme použít předchozí techniku k dokončení konstrukce. K žádnému dalšímu čtení z paměti přitom nedochází.

V závěrečných okamžicích jsem naznačil, že s předpočítaným $\delta$-samoopravným kódem postupný (náhodný) výběr bitů do masky statisticky exponenciálně snižuje počet konfliktů. To jak se pomocí bitové aritmetiky s postupným zvětšováním přesnosti aritmetiky dá paralelně najít v $O(n\log n)$ čase nejefektivnější bit do masky jsem ani nenaznačoval. Ani jsem nenaznačil, jak existence univerzálního hešovacího systému z $w$ bitového do $4w$ univerza plyne existence $\delta$ samoopravitelného kódu. Dobrá zpráva je, že takový kód je nezávislý na reprezentované množině $S$, takže můžeme počítat s tím, že je předkompilovaný.

Přednáška 3

Video z přednášky vypadá OK.

Probírali jsme „vyhledávací stromy“ nad univerzem $2^k$ bitových čísel, tedy množinám s podporou dotazů succ a pred (i pro prvky nepatřící do množiny). Cílem bylo dosáhnout časů $\Theta(k)$ jak pro tyto dotazy, tak pro aktualizace insert/delete (i pro prvky nepatřící do množiny). Pomocí konstantního počtu takových dotazů succ/pred jsme schopni zjistit, zda daný prvek patří do reprezentované množiny (a dostat na něj odkaz). Všechny probírané reprezentace navíc podporovaly vyhledání minima a maxima reprezentované množiny v konstantním čase, což by šlo použít na snížení počtu potřebných dotazů succ/pred při vyhledávání daného prvku.

Začali jsme strukturou B1975, která worst case dosahovala $\Theta(k)$ časy, ale vyžadovala souvislý úsek paměti velikosti $\Theta(2^{2^k})$. (Při popisu succ(x) jsem nezvažoval případ prázdné množiny, kde je samozřejmě odpověď „prázdná množina“.) Pokračovali jsme strukturami W1993, první dosahovala $\Theta(k)$ pro succ/pred, ale aktualizace vyžadovaly $\Theta(2^k)$ času a struktura stále vyžadovala úsek paměti velikosti $\Theta(2^{2^k})$. První transformace (indirekce) vedla k amortizovanému času aktualizací $\Theta(k)$, ale neřešila problém s pamětí. (Když jsem říkal jak často budeme muset provádět aktualizaci indikátorového stromu, říkal jsem jednou za $O(2^k)$ aktualizací. Samozřejmě to mělo být jednou za $\Omega(2^k)$ aktualizací.) Druhá transformace (x-fast) (univerzální hešování potřebné části stromu) veda k tomu, že i pred/succ dotazy přestaly být worst case, ale staly se randomizovaně $\Theta(k)$, čas aktualizací se změnil na amortizovaně randomizovaný $\Theta(2^k)$. Velikost potřebné paměti ale klesla na $\Theta(n2^k)$, kde $n$ je velikost reprezentované množiny. Kombinace těchto dvou transformací (y-fast) pak vedla k randomizovaným $\Theta(k)$ succ/pred a amortizovaně randomizovaným aktualizacím v $\Theta(k)$. Velikost potřebné paměti klesla na $\Theta(n)$.

Zajímavou alternativou jsou FW1990 fusion trees, které využívají triky s širokou aritmetikou (proto vynecháváme). Ty jsou tím efektivnější čím je větší poměr velikosti (logaritmu) univerza vůči reprezentované množině (širší aritmetika) na rozdíl od prezentovaných technik, kde je to obráceně.

Na konci hodiny jsme se trochu věnovali ST1985 splay trees. Udělali rozbor operace Splay s ohledem na libovolně zvolené váhy vrcholů. (V rozboru jsem tvrdil, že $\mu'_x=\mu_x$ znamená, že jsou všechna zmíněná $\mu$ stejná, ono ale může být třeba $\mu'_y$ menší. Tvrzení jsme k ničemu nepotřebovali. Potřebovali jsme jen tvrzení, že pokud $\mu'_x=\mu_x$ a nejsou všechna $\mu$ stejná, pak jsme mohli jedničku v odhadu ušetřit. To že stejná být nemohou bylo zdůvodněno správně.)

Přednáška 4

Video z přednášky vypadá OK. Zdvojnásobení velikosti znamená zvětšení logaritmu o 1 a ne zdvojnásobení logaritmu, ... ach jo.

Začali jsme motivací pro používání cestových operací na stromech se z vnějšku daným tvarem. První z nich byla implementace hledání toku ve vrstevnatých sítích potřebná v Dinicově algoritmu pomocí cestových operací, čímž při vhodné implementaci dostáváme složitost $O(m\log n)$ pro vrstevnatou síť (případně při kombinaci s algoritmem 3 indů $O(\min\{m\log n,n^2\})$). Celková složitost Dinicova algoritmu pak vychází $O(n\min\{m\log n,n^2\})$. Druhou motivací byla $\Theta(\log n)$ implementace (v průběhu hodiny jsme ukázali amortizovanou variantu) struktury pro testování hranové dvousovislosti PW1998 při aktualizacích umožňujících přidávání vrcholů či hran s podporou odvolávání aktualizací (libovolně hluboké historie). K implementacím jsme potřebovali umět přidat mezistromovou hranu, navýšit/snížit cenu všech hran na určené (koncovými vrcholy) cestě o konstantu, umět odstranit danou hranu, zeptat se na nejlacinější hranu na určené cestě.

Pokračovali jsme popisem možné implementace podcestových dotazů operací v rámci jedné cesty, možností podcestových aktualizací vah v rámci jedné cesty. (Ukázalo se, že reprezentace cesty inorder pořadím v binárním stromy umožňují dotaz na podcestu rozložit na spojení logaritmického počtu předzpracovaných dotazů, takže typicky vede k $O(\log n)$ složitosti.)

Následně jsme řešili podcestové dotazy v rámci stromu. Cestu mezi dvěma vrcholy snadno najdeme pokud je strom zakořeněný. Stačí najít první průsečík „lca“ na cestách do kořene z daných dvou vrcholů a úseky cest k tomuto průsečíku. Potřebovali jsme zajistit, aby cesta protínala nejvýš $O(\log n)$ předzpracovaných částí a těmito částmi byly podcesty stromu. Každou takovou podcestu jsme reprezentovali binárním stromem, takže se dotaz na úsek mezi libovolnými dvěma vrcholy podcesty rozkládal na $O(\log n)$ předzpracovaných dotazů. Pouze dotaz v části obsahující lca potřeboval úsek mezi libovolnými dvěma vrcholy. Na ostatních částech byl vždy dotaz od nějakého vrcholu do posledního vrcholu cesty a ty mohly být předzpracované, takže každý vyžadoval $O(1)$ času. Celkový čas dotazu pak mohl být $O(\log n)$.

Pokud pomocí DFS z kořene spočteme velikosti všech podstromů a každý vrchol spojíme do části s nejtěžším dítětem (v případě shody vybereme náhodně, pokud je váha podstromu dítěte menší než polovina váhy podstromu rodiče, není spojení potřeba). Tato strategie znamená, že není-li dítě ve stejné části s rodičem, tak velikost podstromu rodiče je aspoň dvakrát větší než velikost podstromu dítěte. Na cestě z libovolného vrcholu ke kořeni se ale velikost podstromu může zdvojnásobit nejvýš $\log_2 n$ krát takže se taková cesta rozpadá na nejvýš $\log_2 n$ částí, jak jsme potřebovali. Takovému to rozkladu se říká heavy-light dekompozice.

Heavy light dekompozice bude mít nejspíš problém s aktualizací pro cestu určenou dvojicí vrcholů. Přepočítání všech sufixových informací bude nejspíš časově náročné.

Pak jsme se konečně dostali k dynamickému rozkladu na cesty T1983. Nevěnovali jsme se worst case variantám využívajícím BST1985 biased trees, ale jednodušší variantě se splay stromy, dosahujícím amortizovaně stejných časů. Základem práce s cestami je operace Expose($u$), která zajistí aby kořenová část byla tvořená cestou z vrcholu $u$ do kořene reprezentovaného stromu. V neorientovaném případě (kdy kořen není zvenku určen) potřebujeme ještě operaci Evert($u$), která kořenovou cestu začínající ve vrcholu $u$ převrátí, takže se $u$ stane kořenem reprezentovaného stromu.

Operace Expose($u$) je prováděna ve třech fázích, kde v lichých (pomocných) fázích provádíme splay v jednotlivých částech na cestě ke kořeni reprezentace počínaje Splay($u$), takže druhá fáze začíná v situaci kde vrcholy do nichž se napojují části počínaje vrcholem $u$ jsou kořeny jednotlivých Splay stromů (reprezentujících jednotlivé části). Ve druhé fázi pro každý kořen Splay stromu (na cestě od $u$ až ke kořenové části) odtrhneme levé dítě a nahradíme je (pokud tím kořenem není $u$) hranou z kořene splay stromu části obsahující vrchol $u$. Tím se postupně část počínající v $u$ spojí do kořenové části. Protože tuto výměnu provádíme vždy v kořeni splay stromu, reprezentuje vždy levý podstrom část cesty pod vrcholem reprezentovaným v kořeni podstromu. Záměnou levého dítěte kořene tak dochází ke korektnímu přepojení částí. Jako váhy vrcholů jsme pro amortizovanou analýzu Splay stromů zvolili velikost podstromu pod vrcholem s výjimkou podstromu dítěte ve stejné části, proto se při této záměně $\mu$ kořene vůbec nemění. Ceny (včetně času) operací splay v první fázi sa dají odhadnout rozdílem $3\mu_\rho-3\mu_u$ plus počet částí na původní cestě z $u$ do kořene, kde $\rho$ reprezentuje kořen splay stromu reprezentujícího kořenovou část, takže $\mu_\rho$ odpovídá logaritmu velikosti komponenty obsahující vrchol $u$. Cenu (včetně času) druhé fázi můžeme odhadnout počtem částí na původní cestě z $u$ do kořene. Ve třetí fázi se provede tolik rotací, kolik bylo částí na původní cestě z $u$ do kořene. Cenu (včetně času) třetí fáze můžeme odhadnout rozdílem $3\mu_\rho-3\mu_u$. Čas i potenciál je v takovém rozboru měřen v jednotkách času dvojrotace. Pokud tuto jednotku navýšíme tak, abychom započítali jednotku času potřebou v prvních dvou fázích za jednu část na cestě z $u$ do kořene, dokážeme z potenciálu zaplatit i „přeskoky“ mezi částmi v prvních dvou fázích. Tím dostáváme v nových jednotkách celkový odhad ceny (včetně času) operace Expose($u$) $6\mu_\rho-6\mu_u+O(1)$.

Operace Evert($u$) je prováděna zavedením (a flipnutím) bitu jehož význam je pravolevé převrácení podstromu pod kořenem splay stromu kořenové části. Pravolevé převrácení obrací inorder uspořádání, takže tím jsou implicitně otočeny všechny orientace hran v kořenové části. Operace Evert tedy trvá konstantní čas. Znamená ale konstantní zpomalení rotací prováděných v průběhu operací splay. Na určení relativní pravolevosti vůči prarodiči musíme xorovat flipovací bit vrcholu s flipovacím bitem rodiče.

Pomocí operací Expose() a Evert snadno zajistíme, aby kořenovou částí byla cesta mezi danými vrcholy $u$, $v$. Zbývá jen dorozmyslet, jak reprezentovat ceny hran tak abychom snadno určili minimum ceny hrany na kořenové části (reprezentované Splay stromem). Pokud nepoužíváme Evert (orientovaný graf jako v prvním příkladě), můžeme ceny hran reprezentovat ve vrcholech z nichž vycházejí (v kořeni je $\infty$). Implementace Evert flipovacím bitem je ale s takovouto reprezentací nekompatibilní, protože by se jím měnily vrcholy v nichž by měly být váhy udržovány. Řěšením je přidat do reprezentovaného stromu na každou hranu pomocný vrchol, v němž bude váha hrany reprezentována. V původních vrcholech je cena $\infty$. Dodržujeme pak pravidlo, že část vždy začíná původním vrcholem. S takovouto reprezentací je implemantace evert flipovacím bitem kompatibilní.) Nyní již máme určeno v kterých vrcholech reprezentujeme ceny hran, potřebujeme ale takovou reprezentaci, aby byly dotazy i aktualizace efektivní. Řěšením je ceny v rámci části (v rámci Splay stromu) reprezentovat součtem mezivýsledků. V kořeni splay stromu reprezentujeme minimum cen celého splay stomu, a cenu reprezentovnou tímto kořenem jako rozdíl mezi reprezentovanou cenou a minimem podstromu (součtem těchto dvou hodnot dostaneme reprezentovanou cenu). Pro ostatní vrcholy splay stromu reprezentujeme minimum cen jejich podstromu rozdílem od minima ceny podstromu rodiče. Minimum cen podstromu tedy můžeme získat jako součet diferencí minim cen podstromů na cestě ke kořeni včetně minima cen v celém stromu. Cenu daného vrcholu reprezentujeme i zde rozdílem od minima ceny podstromu. Takže reprezentovanou cenu získáme přičtením minima ceny podstromu. (Vzhledem k tomu, že u splay stromů vždy pracujeme v kořeni, tak nikdy nepotřebujeme určovat cenu takto složitým výpočtem.) Zjišťování minimální ceny kořenové části je v této reprezentaci triviální, je uložena přímo v kořeni. Změna všech cen hran kořenové části přičtením stejné konstanty je triviální (přičteme danou konstantu k minimu celého splay stromu reprezentujícího kořenovou část). Tato implicitní reprezentace cen ale opět konstantně zpomaluje rotace (je potřeba přepočítat relativní minima a relativní ceny vůči relativním minimům, nepotřebujeme k tomu znát absolutní hodnoty minim), stejně tak to konstantně zkomplikovalo převěšení levých podstromů kořene (do vrcholu z kterého se stane kořen utrhávaného podstromu musíme přičíst minimum celého stromu a opačně při připojování).

Amortizovaná složitost (současně i worst case) jednotlivých operací s našimi dynamickými stromy je pak konstantní s výjimkou operace Expose($u$) jejíž amortizovaná složitost je $6\mu_\rho-6\mu_u+O(1)$, kde $\mu_\rho$ je logaritmus velikosti komponenty obsahující $u$, a $\mu_u$ je logaritmus velikosti podstromu splay stromu pod vrcholem $u$ včetně velikosti všech částí připojených do tohoto podstromu.

Ve zbývajícíh 3 minutách jsem naznačil užitečnost (pokud nepotřebujeme cestové dotazy) reprezentace tvaru stromu pomocí Eulerovských procházek na zdvojených hranách stromu, kde libovolně přeseknutou procházku reprezentujeme inorder pořadím vyváženého stromu. Jednoduše pak můžeme v logaritmickém čase spojovat či rozpojovat takovéto stromy (jen přitom musíme měnit „přeseknutí“, k tomu ale stačí strom vertikálně přeseknout a vzniklé dvě části spojit v opačném pořadí).

Kromě Eulerovkých procházek jsem upozornil na existenci interface AHLT2003 Top stromů, kde strom je dekomponován na podstromy, které je možno vnímat jako zobecněné hrany. Existuje driver, který zaručuje logaritmickou hloubku dekompozice a jako hlavní operaci umožňuje Expose($u$,$v$) zajistit, aby bylo možno vnímat strom obsahující $u$ a $v$ jako zobecněnou hranu $(u,v)$ (pokud jsou $u$, $v$ v jednom stromě). Interface umožňuje uživateli definovat informace, které chce v zobecněných hranách udržovat a jak tyto informace přepočítávat při primitivních operacích se zobecněnými hranami (spojení dvou zobecněných hran do jedné, rozdělení zobecněné hrany, konverze hrany na zobecněnou hranu a naopak).

Tento interface umožňuje jak práci s cestovými, tak necestovými informacemi. Umožňuje například udržovat centrum stromu efektivněji než jiné datové struktury. Existuje více driverů, jejich imlementace je netriviální, výše popsané link cut trees mohou sloužit jako podklad jedné z nejjednodušších (amortizovaných) implementací.

Přednáška 5

Věnovali jsme se rozboru TL1984 Disjoint Find Union. Připomněli jsme si, že nezávisle na tom, zda spojujeme třídy ekvivalence dle ranku či dle velikosti vychází podstrom pod vrcholem ranku $r$ velký alespoň $2^r$ (neuvažujeme zkracování cest resp. v době, kdy je vrchol stále ještě kořenem). Proto je nejvýš $n/2^r$ vrcholů ranku $r$ (disjunktnost), kde $n$ je počet vrcholů (počátečních tříd ekvivalence). Připomněli jsme si, že $\sum_{k=0}^\infty k/2^k=2$.

Pak jsme definovali tři techniky zkracování cest v průběhu Find (na cestě vždy ostře roste rank), z nichž komprese a splitting byly formou kompakce, což znamená, že všechny hrany po provedení operace Find vedou buď do kořene či do vrcholu na původní cestě s větším rankem než měly před operací Find. U halvingu toto platí pro skok přes dvě hrany. Čas operace Find je proporcionální délce cesty, takže naší snahou je odhadnout celkovou délku všech cest použitých operacemi Find v době práce s datovou strukturou.

Následně jsme bez znalosti významu ${\rm level}(x)$, pouze s tím, že hodnoty jsou nezáporné a menší než nějaké $\ell$ odhadli délku cesty (z operace find na $x_0$) průchodem po jednotlivých vrcholech cesty se zohledněním potenciálu „${\rm level}(x)$“, kde $x$ ja aktuální vrchol na cestě. Dostali jsme odhad ${\rm level}(x_0)+\sum_{i\in P} (1+{\rm level}(x_{i+1})-{\rm level}(x_i))$, kde $P$ označuje vrcholy $x_i$ na cestě, jejichž level není větší než level následujícího vrcholu ($x_{i+1}=p(x)$) na cestě. Potenciál jsme zavedli, abychom dokázali odhadnout počet vrcholů nepatřících do $P$. ${\rm level}(x_0)\le \ell$ naúčtujeme dané operaci Find.

Důležitou vlastností ${\rm level}(x)$ je, že v průběhu času pro vrchol $x$ nemůže tato hodnota nikdy klesnout a pokud je $x$ v $P$, bude po operaci find jeho level roven alespoň ${\rm level}(x_{i+1})$. To nám umožňuje předplatit všechny příspěvky ${\rm level}(x_{i+1})-{\rm level}(x_i)$ v odhadu délek cest zdražením o $\ell$ operace Union, která připojila $x_i$ pod nějaký jiný vrchol.

K dokončení odhadu celkové délky cest potřebujeme posčítat jedničky v daných sumách, tedy kolikrát mohli být jednotlivé vrcholy v $P$. K tomu již potřebujeme definici ${\rm level}(x)$. V prvním nástřelu víme, že funkce ${\rm level}(x)$ bude definována na základě $\ell+1$ řádkové tabulky (počínaje od řádku 0), kde v prvním řádku jsou hodnoty $0\dots \log_2 n$ rozděleny na intervaly délky 1 a v dalších řádcích je méně a méně intervalů vzniklých spojováním intervalů předchozího řádku, s tím, že v řádku $\ell$ je jediný interval. Můžeme označit $b_{i,j}$ z kolika intervalů předchozího řádku se skládá $j$-tý interval na $i$-tém řádku.

${\rm level}(x)$ (pokud $x$ není kořen) je první řádek, na němž je jak ${\rm rank}(x)$ tak ${\rm rank}(p(x))$ ve stejném intervalu. Vzhledem k tomu, že je rank pro nekořeny konstantní, a rank rodiče se může měnit jen tím, že se změní rodič (zvýšení) či je-li rodič kořen, jemuž se rank zvětšil připojením podstromu stejného ranku, nemůže tedy později dojít k tomu, že by se interval mezi $x$ a $p(x)$ zkrátil a vešel se do intervalu na dřívějším řádku. Tedy náš předpoklad neklesání hodnoty ${\rm level}(x)$ v čase platí. Navíc po kompakci s výjimkou předposledního vrcholu na cestě bude ${\rm rank}(p'(x))$ velký alespoň ${\rm rank}(p(p(x)))$ (a předposlední vrchol nepatří do $P$). Proto ${\rm level}'(x)\ge \max({\rm level}(x),{\rm level}(p(x)))$ (přinejmenším sjednocení obou intevalů se musí vejít do intervalu příslušného řádku), takže platí předpoklad, že pro $i$ v $P$ bude po Find ${\rm level}'(x_i)\ge {\rm level}(x_{i+1})$.

Navíc, pokud je $a\in P$, pak ${\rm level}(x_a)\ge 1$ a musely být $x_a$, $p(x_a)$ i $p(p(x_a))$ v různých intervalech úrovně ${\rm level}(x_a)-1$. To může pro vrchol jehož rank padne do $j$-té přihrádky úrovně $i$ nastat na úrovni $i$ nejvýš $b_{i,j}-1\le b_{i,j}$ krát. Pokud to posčítáme pro všech $n_{i,j}$ vrcholů přihrádky, dostaneme odhad $n_{i,j}b_{i,j}$. Přes všechny přihrádky pak $\sum_{i\ge 1,j}n_{i,j}b_{i,j}$. Je-li $r_{i,j}$ nejnižší rank v $j$-té přihrádce řádku $i$, pak $n_{i,j}\le 2n/2^{r_{i,j}}$. Zvolíme-li pro $i<\ell$ $b_{i,j}\le r_{i,j}$ dostaneme součet $\sum_j n_{i,j}b_{i,j}\le \sum_r 2nr/2^r=4n$. Tím bychom dostali celkem $\sum_{i\ge 1,j}n_{i,j}b_{i,j}\le 4\ell n+nb_{\ell,1}$. Nám se ale v odhadu faktor $\ell$ nelíbí a radši navýšíme cenu operace Find o $\ell$. Tím že pro každý level $l$ první $x_i \in P$ s ${\rm level}(x_i)=l$ zaplatí operace Find. V takovém případě nikdy neúčtujeme na úrovni $i$ vrcholu, jehož rank padne do první přihrádky na úrovni $i-1$. Posčítáme zvlášť příspěvky za první přihrádky na každém řádku a za ostatní přihrádky (poslední řádek zcela samostatně). Součty na řádcích od druhé přihrádky jsou $$\sum_{j>1} n_{i,j}b_{i,j}\le \sum_{r\ge r_{i,2}} 2nr/2^r=2n/2^{r_{i,2}}\sum_{r\ge 0}((r+r_{i,2})/2^r)=2n/2^{r_{i,2}}((\sum_{r\ge 0} r/2^r)+r_{i,2}(\sum_{r\ge 0}1/2^r))=4n(1+r_{i,2})/2^{r_{i,2}}.$$ Zvolíme $b_{i,1}=2$, tedy $r_{i,2}$ rostoucí (a $r_{1,2}\ge 2$) a celkově $$\sum_{i\ge 1,j>1}n_{i,j}b_{i,j}\le \sum_{i\ge 1} 4n/2^{r_{i,2}}(1+r_{i,2})\le 4n(\sum_{r\ge r_{1,2}} 1/2^r+\sum_{r\ge r_{1,2}}r/2^r)\le 4n(2/2^{r_{1,2}}+2(1+r_{1,2})/2^{r_{1,2}})\le 8n.$$

V první přihrádce $i$-tého řádku účtujeme jen za vrcholy jejichž rank je aspoň $r_{i-1,2}$, tedy nejvýš $2n/2^{r_{i-1,2}}\cdot b_{i,1}=4n/2^{r_{i-1,2}}$ součet přes všechny řádky pak dává $\sum_i 4n/2^{r_{i-1,2}}\le 4n$.

Zbývá finalizovat přihrádkové schéma a určit $\ell$. Nechť $m$ je počet operací prováděných datovou strukturou. Zjednodušíme to a $j$ tou přihrádku na řádku $i$ ukončíme těsně před rankem $A(i,j)$, kde $A(0,j)=j$, $A(i,1)=A(i-1,2)$ pro $i>0$ a $A(i,j)=A(i-1,A(i,j-1)+1)$ pro $i,j>0$. (V článku je používána rychleji nastartovaná varianta Ackermanova funkce a je dodržováno $b_{1,j}=r_{1,j}$, nicméně ve výsledku je naše $\alpha(m,n)$ nejvýš o $2$ větší.) První podmínka zajišťuje, aby každý interval na nultém řádku byl jednoprvkový, druhá aby $b_{i,0}=2$ a třetí $b_{i,j}\le r_{i,j}$ pro $j>1$ dokonce $\sum_{k\le j} b_{i,k}\le r_{i,j}$. Zvolíme $\ell-1=\alpha(m+n,n)=\min\{i\mid A(i,\lfloor (m+n)/n\rfloor)>\log n\}$ tedy jakmile na řádku $\ell-1$ je nejvýš $\lfloor (m+n)/n\rfloor$ intervalů, pak tedy $b_{\ell,1}\le \lfloor (m+m)/n\rfloor$ a $n_{\ell,1}b_{\ell,1}\le n(m+m)/n=m+n$. (Pokud bychom chtěli využít fakt, že účtujeme jen vrcholům s ${\rm rank}(x)\ge r_{\ell-1,2}=A(\ell-1,1)$, mohli bychom použít $\ell-1=\alpha'(m+n,n)=\min\{i\mid A(i,\lfloor (m+n)/n\rfloor \cdot 2^{A(i-1,1)-1})>\log n\}$.)

Dostali jsme tak, že kromě času $O(1+\alpha(m+n,n))$ účtovanému jednotlivým operacím potřebujeme $13n+m$ času. Celkem tedy $O(n+m(1+\alpha(m+n,n)))$ (pokud vytváření vrcholů zavedeme jako třetí metodu datové struktury, můžeme sčítanec $n$ v odhadu nahradit pomocí $m$).

Pro halving je potřeba důkaz mírně modifikovat a definovat level na základě $x$ a $p(p(x))$. Rozbor přirozeně zaplatí půlku délky cesty (vrcholy, jimž se mění $p(x)$), takže dostáváme dvojnásobek pro odhad celkové složitosti.

Užitečné je si všimnout, že $\alpha(m,n)$ je nerostoucí v první a neklesající ve druhé souřadnici a například pro $m>n\log\log^*n$ platí $\alpha(m,n)\le 4$. Takže například Kruskalův algoritmus volaný se setříděným seznamem hran podle cen je v případě aspoň $n\log\log^*n$ hran lineární (v počtu hran). V článku definují „separovatelné algoritmy“ a s odkazem na jiné články dokazují, že dosažený výsledek je pro takové algoritmy asymptoticky optimální.

Přednáška 6

Věnovali jsme se haldám. Jako motivaci jsme měli algoritmus Fredman Tarjan na hledání minimální kostry FT1987 v řádově $\log^*n$ fázích, kde každá trvá $\Theta(m)$.

Následně jsme rychle proletěli $d$-reguární haldy a začali se věnovat odvození varianty Fibonacciho hald na základě principu „drahého porovnávání“. K dosažení optimální amortizované složitosti nám v rozboru stačil součet 4 potenciálů.

Ke konci hodiny jsem naznačil, jak efektivně implementovat worst case verzi hald bez operace meld M2020. Od Fibonacciho hald byl rozdíl v tom, že místo lokální podmínky omezující ztrátu každého rankového potomka na nejvýš 1 používáme součet ztrát všech potomků je menší než maximální řád plus 1. Ukazuje se že maximální řád se tím příliš nezmění (asymptoticky je menší než u Fibonacciho hald). Struktura vyžaduje různé priority prvků, což je případně potřeba zajistit lexikografickým porovnáváním a přidaným identifikátorem v druhé souřadnici. Na rozdíl od Fibonacciho hald struktura při konsolidaci nevkládá všechny kandidáty na minimum do pole dle řádů, aby je na konci z pole odstranila, ale rankové kořeny stromů dle jednotlivých řádů udržuje v poli celou dobu. Obdobně v poli dle jednotlivých řádů udržuje potomky se ztrátou 1 (poté co byl připojen rankovou hranou mu byl ztráta krát snížen rank). Aby bylo dosaženo worst case složitostí, končí ExtractMin plnou konsolidací, zatímco metody které mají pracovat v konstantním čase končí konsolidací částečnou. Při ní je zajištěno, aby existoval jediný kandidát na minium a jak počet rankových stromů, tak součet ztrát byly nejvýš maximální rank plus 1. Toho je dosaženo pomocí konsolidačních operací spojujících stromy stejného řádu, případně pro vrchol se ztrátou aspoň 2 konverzí rankové hrany na nerankovou, čímž se danému vrcholu vynuluje ztráta, ale jeho rodiči, nebyl-li rankovým kořenem se zvětší ztráta o 1. Mohou nastat situace, kdy je příležitost pokračovat s konsolidací nekonstantně dlouho. My místo toho konsolidaci (za jasně definovaných okolností) přerušíme a vrchol, jenž by měl být dále řešen odložíme na zásobník čekajících konsolidací. Takový zásobník máme jak pro konsolidace počtu nerankových hran, tak pro konsolidace ztrát. Z hlediska rozboru používáme potenciál ve formě součtu dvou potenciálů. První je jednou zaplnění pole řádů rankových kořenů plus dvakrát počet prvků na zásobníku nerankovýh hran. Druhý je třikrát zaplnění pole řádů potomků se ztrátou 1 plus čtyřikrát součet velikostí ztrát (resp. 1 pro vrchol bez ztráty) na zásobníku konsolidace ztrát. Každý konsolidační krok snižuje součet těchto potenciálů. Dodržujeme strategii, že pro oba potenciály buď musí být po skončení operace potenciál menší než byl na začátku operace, nebo musí být příslušný zásobník konsolidace prázdný. Dá se spočítat, kolik jakých konsolidačních kroků je potřeba pro každý druh operace vykonat, aby byla podmínka splněná. A je to konstanta.

Přednáška 7

Jednalo se o „paběrkovací“ hodinu. Po seznámení s plánem na zbytek semestru jsme se věnovali doplnění dřívějších přednášek.

Nejprve jsme rozebrali amortizovanou složitost DFU s naivním union (v případě $m\ge n$ operací). Pak jsme oslabením přístupového lemma pro Splay stromy (váhy podstromu jsme odhadovali vahou kořene podstromu) ukázali 3 věty o chování Splay stromů.

Na konci hodiny jsme se vrátili k Top stromům a ukázali jsme uživatelské rozhraní, jak pomocí nich udržovat centrum stromu. Zmínil jsem Global search s uživatelskou funkcí Decide. Nevím proč jsme rozebrali jak spočítat potřebné hodnoty (nejvzdálenější vrchol od hraničního vrcholu a délka páteře) jen pro jednu ze dvou variant dekompozice. Pro druhou variantu je to obdobně jednoduché.

Přednáška 8

Věnovali jsme se dynamizaci datových struktur.

Nejprve pro případ dynamické datové struktury kde po $\Omega(m)$ operacích musíme strukturu v čase $O(m)$ přebudovat.

Následně jsme se věnovali struktuře s částečným přebudováváním ... BB-$\alpha$ stromům. Ukázali jsme, že stačí spořit do potenciálu při každé modifikaci konstantu na každé úrovni stromu, kterých je logaritmus. Všechny rebuildy pak dokážeme z úbytku potenciálu zaplatit.

Ukázali jsme, jak pomocí BB-$\alpha$ stromů implementovat strukturu na kvádrové dotazy v $d$-dimenzionálním prostoru. Při velikosti $n\log^{d-1} n$ bude struktura umět vracet body ze specifikovaného kvádru v čase $O(\log^d n + |A|)$ kde $|A|$ je velikost vrácené množiny. Přitom přebudovánání struktur je možno zaplatit z úspor, pokud každá aktualizace předplácí dohromady $O(\log^d n)$.

Následně jsme se věnovali dynamizací struktury pro odpovídání rozložitelného dotazu. Nejprve jsme řešili Insert only struktury. V první variantě amortizovaně pomocí rozkladu na nejvýš $\log_2 n$ podmnožin $B_i$ velikostí $2^i$ (pro každé $i$ nejvýš jedna množina). Až na nepodstatnou pomocnou paměť nám stačil původní prostor statické struktury (za předpokladu $Space_S(n)/n$ je neklesající). Dotazy se $O(\log n)$ krát zpomalily (za předpokladu, že skládání výsledků je nejvýš tak pomalé jako indviduální dotaz $Query_S(n)$ a $Query_S(n)$ je neklesající). Pokud každý insert předplácel $Build_S(n)/n\cdot \log n$, stačilo to na všechny aktualizace (za předpokladu $Build_S(n)/n$ je neklesající).

Pak jsme se zabývali možností dynamizovat rozložitelný dotaz worst case. Za předpokladu, že Build můžeme rozdělit na konstantně trvající části (což může být například pro alokaci paměti problém), můžeme plánovat na každý insert tolik práce, kolik odpovídá amortizovanému času. Rozložení budování nové verze struktury v čase má ale svá úskalí. Musíme udržovat prvky jak v hotové, tak v rozpracované verzi, s tím, že dotazy používají jen hotové verze. Ukázali jsme, jak je možno plánovat strukturu tak, aby pro každé $i$ jsme vždy měli nejvýš 3 hotové struktury velikosti $i$ a nejvýš jednu rozpracovanou. Asymptoticky se amortizovaný čas nezměnil, ale podařilo se budování rozložit v čase tak abychom zajistili odpovídající worst case časy.

Poslední modifikací je pomocí první techniky (přebudovávání) jednou za $\Omega(m)$ v čase $O(m)$, za předpokladu, že můžeme Delete řešit kaňkováním, upravit strukturu tak, aby obsahovala menšinu zakaňkovaných prvků.

Ke konci hodiny jsem udělal přípravu na persistenci. Definovali jsme efemerní struktury, semipersistentní, plně persistentní a funkcionální datové struktury. Ukázal jsem, jak využít semipersistentní vyhledávací stromy k lokalizaci trojúhelníku triangulace obsahujícího daný bod.

Přednáška 9

Věnovali jsme se DDST1986 persistenci pro struktury odpovídající pointer machine výpočetnímu modelu. Jednodušší byla semipersistence, kde modifikace mohou nastávat pouze v aktuální verzi a nemusíme verzovat data potřebná pouze kvůli modifikacím. Nejprve jsme jak pro semipersistenci, tak pro plnou persistenci popsali variantu s tlustými vrcholy, kde pro každý efemerní uzel udržujeme binární strom verzí jednotlivých evidovaných hodnot. (Logaritmické zpomalení oprerací, ale vše je worst case. V semipersistentní verzi bychom mohli použít y-fast stromy, díky tomu, že čísla verzí nemusíme přečíslovávat, dostali bychom tak $\log\log$ zpomalení randomizovaně amortizovaně.) Pak jsme se věnovali semipersistentí variantě pro případ konstantou omezených in degree jednotlivých efemerních uzlů (pointer machine ani víc neumožňuje). Trik byl v tom, v jednom persistentním uzlu reprezentovat současně interval verzí efemerních uzlů tak, že evidujeme stav v počátku intervalu a následně seznam změn, ke kterým v intervalu verzí došlo. (udržujeme navíc spojový seznam všech persistentních uzlů v pořadí odpovídajícím vývoji jednoho efemerního uzlu). Seznam změn „žurnál“ nám umožňuje evidovat nejvýš konstantní počet změn. Platnost každé evidované hodnoty pak je nějaký interval verzí. O pointeru s platností počínající verzí $v$ říkámě, že je „řádný“ pokud odkazuje na uzel jehož rozsah verzí zahrnuje verzi $v$. O řádném pointeru s platností končící verzí $v$ říkáme, že „nepřetéká“ pokud odkazuje na uzel jehož rozsah verzí zahrnuje verzi $v$. Invariantem, který budeme dodržovat mezi jednotlivými aktualizacemi je, že ve struktuře jsou všechny pointery řádné, nepřetékající. V případě přetečení kapacity žurnálu založíme nový uzel počínaje aktuální verzí. Tím ale u pointerů odkazujících na předchozí verzi uzlu dojde k tomu, že přestanou být nepřetékající. To musíme na konci operace konsolidovat například tím, že zavedeme aktuální verzi pointeru odkazující na novou verzi uzlu. To může vyvolat kaskádovité štěpení uzlů. Vhodný potenciál může tato štěpení zaplatit, aby takový potenciál existoval, potřebujeme kapacitu žurnálu $E$ větší než indegree efemerního uzlu. Abychom dokázali lokalizovat vzniklé přetékající pointery, potřebujeme v aktuální verzi datové struktury evidovat odkazy na uzly odkazující na daný uzel (v článku pro jednoduchost tyto zpětné odkazy udržují ve všech uzlech persistentní struktury, ale využívají je jen v aktuální verzi).

Mnohem komplikovanější situace je u plně persistentníh datových struktur. Zapomněl jsem zmínit, že transformace vyžaduje worst case verzi efemerní datové struktury. Pokud bychom amortizací chtěli hradit pomalou operaci, určitě nemůžeme mít naspořeno dost na to, abychom tutéž pomalou aktualizaci libovolně krát zopakovali (ze stejné historie). Další problém je s evidencí verzí. Například v tlustých vrcholech potřebujeme umět odnavigovat k požadované verzi informace. Situace se mnohem zjednoduší, pokud budeme mít uspořádání na verzích na základě něhož budeme moci navigovat. Toho se dá docílit například řešením list ordering problému. Budeme mít linearizovaný seznam verzí a jakoukoli verzi můžeme aktualizovat tak, že vytvoříme verzi bezprostředně následující a za ní ještě jednu verzi obnovující stav před aktualizací. Pak můžeme jakýkoli stav vnímat jako postupnou aplikaci všech změn od počátku seznamu. Třetí problém týkající se implementace s tenkými vrcholy je v tom, že můžeme být nuceni vrcholy štěpit i jinde než v aktuální verzi. Což může během jedné aktualizace vést až k logaritmickému (vůči počátečnímu počtu uzlů) počtu vložení verzí pointerů původně jedné verzi uzlu. Je potřeba dělat aktualizace opatrně, abychom je zvládli v kostatním čase na jednu vloženou verzi pointeru. Tirkem je řešit přetékání pointerů vždy jen v jednom uzlu a při jeho štěpení udržovat řádnost pointerů v odkazujících vrcholech. Evidujeme proto verzované i opačné pointery. Opět můžeme vhodným potenciálem všechna taková štěpení zaplatit, vzhledem k tomu, že aktualizace se může týkat uzlů reprezentující všechny intervaly verzí, nemůžeme zajistit snížení potenciálu tím, že by uzel přestal být aktivní. Aby to potenciál dokázal zaplatit potřebujeme kapacitu žurnálu $E$ větší než dvakrát celkový stupeň efemerního uzlu.

Věnovali jsme se také aplikovatelnosti metody na červenočerné vyhledávací stromy. V případě semipersistence, kde nemusíme verzovat informace o barvě byla situace jednoduchá. Každá aktualizace vedla pouze ke konstantnímu množství strukturálních změn, takže částečně persistentní struktura byla řádově tak velká, kolik aktualizací jsme provedli. Dotazy zůstaly logaritmické. V případě plné persistence jsme ve snaze zajistit řádově tak velkou strukturu, kolik jsme provedli aktualizací, museli modifikovat pravidla barvení, tak aby velikost aktualizace zůstávala konstatní. Kromě explicitně evidovaných barev jsou definovany dva druhy implicitních přebarvovacích pravidel pro skupiny vrcholů určených kořenem ovlivněného podstromu a klíčem určujícím dolní konec cesty v jejímž okolí je implicitní přebarvování platné. Jedno pravidlo odpovídá operaci insert, druhé operaci delete. Je dodržován invariant, že žádný vrchol stromu není současně ve více přebarvovacích skupinách. Pokud je potřeba přebarvovací skupinu o konstantní úsek zkrátit, můžeme to na konstantní počet změn udělat (explicitně přebarvíme a změníme kořen podstromu či/a klíč určující dolní konec). Obdobně můžeme skupinu rozdělit na dvě, či konstantně velkou skupinu úplně nahradit explicitním přebarvením.

Na konci hodiny jsme popsali dva základní a jeden kombinovaný přístup na řešení list ordering problému, tak abychom na základě porovnávání dokázali určit „dřívější/pozdější“ verzi plně persistentní datové struktury.

Přednáška 10

Nejprve jsme se vrátili k list order problému. Speciálně jsme se věnovali list labeling formě, kde generujeme jen čísla v rozsahu $\Theta(n)$, kde $n$ je počet položek, tedy file order maintainance problému. Ukázali jsme jak v amortizovaném čase $O(\log^2 n)$ udržovat $n$ položek v určeném pořadí v souboru délky $\Theta(n)$. Technika byla založená na představě $h$ patrového binárního stromu kde pro delší a delší intervaly je stále striktnější podmínka na hustotu zaplnění. V kořeni je cílová hustota mezi $2/4$ a $3/4$, zatímco v listech (v blocích velikosti $\Theta(\log n)$) mezi $1/4$ a $4/4$. Kdykoli přeteče list, hledáme patro nejblíž listům v jehož intervalu obsahujícím přetečený list už bude cílová hustota. Kvůli určování hustot přepočítáváme přitom zaplnění což nás celkem stojí čas odpovídající kapacitě představovaného intervalu patra s cílovou hustotou. Ve stejném čase pak (dvojprůchodově) přerozdělíme vrcholy představovaného intervalu s cílovou hustotou. Tím se tato hustota až na zaokrouhlování stane aktuální hustotou v každém patře blíž k listům. Vzhledem k tomu, že požadavky na hustotu jsou s každým patrem směrem k listům o $1/(4h)$ benevolentnější, muselo od situace, kdy v intervalu byla cílová hustota patra blíž ke kořeni do situace, kdy v intervalu není cílová hustota odpovídající jeho patru nastat alespoň $K/4h$ aktuzalizací, kde $K$ je kapacita intervalu na příslušném patře. Pokud těchto $K/4h$ aktualizací předplatí $\Theta(K)$ času na toto patro, dokážeme z toho zaplatit přebudování celého nadintervalu kapacity $2K$. Stačí tedy, když každá aktualizace zaplatí $\Theta(h)$ na každé patro, tedy celkem $\Theta(h^2)$. Pokud ani kořenová hustota (hustota celého souboru) není v požadovaných mezích, zvolíme novou velikost souboru odpovídající až na zaokrouhlení cílové hustotě $5/8$ a přerozdělíme všechny prvky tak, že ve všech listech bude až na zaokrouhlení tato hustota. Bude tedy čas naspořit na přerozdělování intervalů. Od posledního změny velikosti souboru se celková hustota musela změnit (až na zaokrouhlení) o $1/8$, muselo tedy dojít k $\Theta(n)$ aktualizacím. Stačí tedy, aby každá aktualizace předplácela navíc $\Theta(1)$ abychom spořili na změny velikostí souboru.

Následně jsme se věnovali cache aware a cache oblivious problematice, především co se týče vyhledávacích stromů. Ukázali jsme, že vEB layout pro úplný statický vyhledávací strom pevné hloubky má optimální složitost vyhledání $\Theta(\log n/\log B)$ výpadků bloků keší velikosti $B$ (cache oblivious, tedy beze znalosti $B$). (V principu nepotřebujeme pro strom ve vEB layoutu udržovat explicitní pointery, mohli bychom je dopočítávat. Stálo by nás to nejspíš $\Theta(\log\log n)$ času na pointer, ale zkompaktnění položek by mohlo snížit multiplikativní konstantu u počtu výpadku keší.)

Při pokusu o dynamickou verzi struktury, založenou na udržování setříděné množiny pomocí file order maintainance techniky, kde vyhledávací strom co se týče aktualizací potřebujeme pouze k lokalizaci místa aktualizace jsem byl zmaten tím jak si poradit se situací, kdy velikost souboru neodpovídá velikosti úplného biárního stromu. Stačí vybrat úplný strom s aspoň tolika listy, jak je velký soubor. V nelistových vrcholech stačí uchovávat největší klíč podstromu. Otestováním hodnoty v levém potomkovi je jasné do kterého potomka pokračovat. Po $\Theta(\log n)$ čteních a $\Theta(\log n/\log B)$ výpadcích keší tak najdeme příslušný list.

Při aktualizacích souboru, kdy je modifikován interval hodnot je potřeba přepočítat informace v podstromu pokrývajícím daný interval. To ale v čase konstanta krát velikosti intervalu zvládneme, přičemž počet výpadků keší bude řádově velikost intervalu děleno $B$. Dostáváme tak amortizovanou složitost $\Theta(1+\log^2 n)$ s amortizovaným počtem výpadků keší $\Theta(1+\log^2 n/B)$ na aktualizaci (navíc k lokalizaci místa aktualizace $\Theta(\log n)$ času a $\Theta(\log n/\log B)$ výpadků).

Indirekcí, kdy používáme bloky velikosti $\Theta(\log n)$ a v file ordered maintainance udržujeme pouze zástupce bloků dokážeme aktualizaci (včetně dohledávání) v bloku provádět v čase $\Theta(\log n)$ s počtem výpadků keší $\Theta(\log n/B)$. A na (pře/pod)tečení kvůli kterému musíme aktualizovat file ordered maintainance dokážeme našetřit v průběhu $\Theta(\log n)$ aktualizací. Stačí tedy amortizovaně $\Theta(1+\log n)$ času a $\Theta(1+\log n/B)$ výpadků keší co se týče aktualizace file ordered maintinance a binárního stromu nad ním, nicméně lokalizace místa aktualizace v čase $\Theta(\log n)$ s $\Theta(\log n/\log B)$ výpadky zůstává, což se (co se týče výpadků keší) stává podstatnější složkou (optimální) složitosti. (Při vyhledávání prvku najdeme pomocí vyhledávacího stromu zástupce ve file order maintainance, může se stát, že se jedná o zástuce sousedního bloku, ale dohledání nemá vliv na asymptotickou složitost.)