{{TOC float}}
{{Sources|
''Založeno na [[Státnice_-_Stromové_vyhledávací_struktury]]''
09/10: Stromové vyhledávací struktury: binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty.
14/15: Stromové vyhledávací struktury: binární stromy a jejich vyvažování, haldy, trie, B-stromy a jejich varianty. <u>Relaxované vyhledávací stromy</u>
}}
{{zkazky|
* '''Stromové vyhledávací struktury (2014, Fiala)''' - Přehledově trie, binární vyhledávací stromy, (a,b)-stromy. Podrobně haldy d-regulární, leftist, binomiální, líné binomiální, Fibonacciho.
* '''Stromové vyhledávací struktury (2008, Spěchající teoretik)''' - Popsat jsem A4 binárními stromy, jejich procedurami insert a delete, popisem jak se vyvažují AVL stromy, a stručnými pravidly jak vypadají červenočerné stromy. Chtěl jsem si udělat i něco o B-stromech, haldách a triích, ale zkoušející si prohlédl můj papír s binárními stromy a prohlásil, že mu to stačí.
I1/I4:
* '''Vyhledávací stromy (2013, Fiala,MJ)''' - Řekl jsem dospělácké věci: RB stromy jsou (2,4)-stromy, AVL jsou RB, RB jsou polovyvážené. Náhodné stromy jsou randomizovaný Quicksort. Splay tree, dynamická optimalita, statická optimalita. Počítání nebylo potřeba, ale chtělo by to trochu lépe znát operace.
* '''Dynamizace, relaxované vyhledávací stromy, samoupravující datové struktury (Majerech+Čepek+Petr Kučera)''' - Dynamizaci jsem věděl, stačilo popsat ty dva způsoby semidynamizace a dynamizaci. Bez důkazů. To se jim celkem líbilo, a protože jsme tím zabili dost času, popsal jsem princip relaxovaných struktur jen stručně. Pak jsme se ještě zasekli u Splay stromů, ptali se, jak se u nich měří složitost, což jsem nějak nebyl schopný zodpovědět, aby s tím byli spokojeni. Zpětně mě napadá jen možnost, že jsem neřekl, že měříme amortizovanou hloubku stromu.
}}
==Binární vyhledávací stromy (14×🎓)==
{{zkazky|
* '''Vyvazovani binarnich vyhledavacich stromu(2015, Kopecky)''' - AVL + CC stromy. Dokazal jsem logaritmickou vysku CC stromu (ani dukaz AVL neni moc tezky). Popsal jsem vyvazovani a trochu zavahal u tezsiho prikladu vyvazeni CC stromu.
* '''Vyvazovani binarnich vyhledavacich stromu (2014)''' - stihli jsme jenom AVL
* '''Vyvážené binární vyhledávací stromy (2013, Koubek)''' - Napsal jsem: co je BVS (měl jsem tam chybu v podmínce), co je vyvážený strom a ústně jsem na jeho dotaz doplnil, že jeho hloubka je O(logn), definici AVL a Č-Č (u Č-Č jsem měl i nějaký odhad hloubky, ale Koubek vypadal, že si ho ani nevšiml), základní algoritmy – jen slovně a občas jsem tam měl drobnou chybku (např. jsem předpokládal, že vrchol má při odstraňování jednoho syna, ale on to mohl být i list), na příkladu AVL jsem se snažil popsat vyvažování. Neměl jsem to připravené, ale Koubek ty operace stejně přesně nechtěl. Spíš chtěl, abych mu řekl, že při vyvažování se nejen upravuje strom, ale také mění ta hodnota o vyvážení uložená ve vrcholech. Celkově mě překvapilo, že byl Koubek docela hodný (čekal jsem to horší podle předchozích zápisů). Když odcházel vypadal spokojeně. Koubek občas chytne za slovo, když člověk řekne něco co není pravda. Je třeba se nenechat zaskočit (což je samozřejmě těžké) a popřemýšlet nad tím, co se mu nelíbí.
* '''Binarne vyvazene stromy (2012, Koubkova)''' - Rekl jsem definici AVL, RB, BB(alpha), dukaz hloubky AVL a nakonec par operaci nad AVL stromy. AVL jsem si vybral dobrovolne, mohl jsem rikat vic i o RB. Na nic moc se neptala a byla spokejena
* '''Binarni stromy (2010, Kratochvil)''' - napsal sem co jsou binarni stromy, jak muzou zdegenerovat, jak vypada idealne vyvazeny binarni strom, popsat CC-stromy a AVL stromy, otazky byli ohledne slozitosti, jestli muzou rotace eskalovat a slozitost insert/delete znamka1
* '''Bin. vyvažovacie stromy (2010, Kopecký)''' - stromy som zadefinoval (BS, AVL, CC), popísal member, insert, delete - obrázky, jednotlivé prípady, rotácie ČČ som nerozpisoval - napriek tomu, že som sa to učil, nervy hrali a nebol som to schopný dať na papier. Takže som popísal slovne, koľko akých prípadov nastane. Porovnal som medzi sebou ČČ a AVL stromy, povedal dôvod, prečo sa zavádzajú. Napísal som podstatné z dôkazu o výške oboch. Kopecký vyzeral spokojne a do technických detailov nevŕtal. Ďalšie otázky smerovali k optimálnym vyhľ. stromom - popísal som slovne konštrukciu - dynam. programovanie, spomenul možné zlepšenie zložitosti z kubickej na kvadratickú. Rozložiteľnosť úlohy. Pýtal sa na stromy s príslušnou amort. zložitosťou, či nejaké poznám. Odpovedal som, že poznám Splay stromy - popísal som, k čomu sú dobré, ako fungujú zhruba - Splay a prvok hore. Prečo to má v praxi dobré vlastnosti. To mu stačilo, povedal, že otázka o Splay tr. bola nad rámec, že len skúšal, kam siahajú znalosti.
* '''Binární vyhledávací stromy (2009)''' - popsal jsem co je to binární strom, co je to BVS, jak se tam dělají jednotlivé operace, proč se zavádějí vyvažované stromy, definice k AVL a R-B, jaký je tam rozdíl v hloubce, jak se dělají vyvažovací operace. Jen lechce si zkoušející šťournul do vyvažovacích operací R-B (že je při delete potřeba 2xčerný vrchol a ještě nějaké detaily, nic do hloubky). Pak se ptal ještě na Splay stromy, ale o tom jsem nic nevěděl, nechal to tedy být s tím, že se to dnes asi už neučí.
* '''Bin. vyvažovacie stromy (2010, Kopecký)''' - stromy som zadefinoval (BS, AVL, CC), popísal member, insert, delete - obrázky, jednotlivé prípady, rotácie ČČ som nerozpisoval - napriek tomu, že som sa to učil, nervy hrali a nebol som to schopný dať na papier. Takže som popísal slovne, koľko akých prípadov nastane. Porovnal som medzi sebou ČČ a AVL stromy, povedal dôvod, prečo sa zavádzajú. Napísal som podstatné z dôkazu o výške oboch. Kopecký vyzeral spokojne a do technických detailov nevŕtal. Ďalšie otázky smerovali k optimálnym vyhľ. stromom - popísal som slovne konštrukciu - dynam. programovanie, spomenul možné zlepšenie zložitosti z kubickej na kvadratickú. Rozložiteľnosť úlohy. Pýtal sa na stromy s príslušnou amort. zložitosťou, či nejaké poznám. Odpovedal som, že poznám Splay stromy - popísal som, k čomu sú dobré, ako fungujú zhruba - Splay a prvok hore. Prečo to má v praxi dobré vlastnosti. To mu stačilo, povedal, že otázka o Splay tr. bola nad rámec, že len skúšal, kam siahajú znalosti.
* '''Binarni stromy, vyvazovani (2011, Majerech)''' - AVL, RB, hlavne definice a invarianty a hloubky, operace a rotace vlastne ani nechtel. Spocital se mnou minimalni pocet vrcholu pro danou hloubku u obou stromu a prestoze mi to moc neslo, tak byl nakonec spokojenej.
* '''BVS a jejich vyvažování (2010, Kopecký)''' - BVS, AVL stromy, RB stromy, rotace. Vytvoření statického stromu pomocí dynamického programování. Mluvili jsme také o splay stromech.
* '''AVL, CC stromy (2010, Löebl)''' - Bez problému, definice, rotace, nic moc do hloubky.
* '''AVL stromy (2009, Koubkova)''' - Toto bolo velmi v poho. Napisal som zopar definicii, ukazal rotacie a zlozitosti operacii. Potom mi dala priklad ktory sme spolu spravili a koniec.
* '''Binární stromy a vyvažování (2009, Surynek)''' - Definice BS, BVS, operace, jejich složitosti, nejhorší případ. AVL - definice, důkaz logaritmické výšky, rotace, příklad vkládání několika prvků. RBT - definice, důkaz logaritmické výšky, výhody/nevýhody oproti AVL, hustota AVL vs. RBT, stejný příklad s vkládáním. Stručně BB-α, splay stromy (kdy se hodí), optimální BVS.
* '''Stromové vyhledávací struktury (2008, Spěchající teoretik)''' - Popsat jsem A4 binárními stromy, jejich procedurami insert a delete, popisem jak se vyvažují AVL stromy, a stručnými pravidly jak vypadají červenočerné stromy. Chtěl jsem si udělat i něco o B-stromech, haldách a triích, ale zkoušející si prohlédl můj papír s binárními stromy a prohlásil, že mu to stačí.
I1/I4:
* '''Vyvazovani binarnich vyhledavacich stromu (2013, Koubkova)''' - co, proc jak, priklad, algoritmy ne, radsi obrazky. U vyvazovani stacilo popsat rotace, nejaky prilad insertu, pak jsme pokecali o tom jak se to da delat obecne v AVL stromech (jen zhruba) a nakonec me nechala zadefinovat RB-stromy.
* '''AVL stromy (2012, Koubkova, ale zkousel de facto Koubek)''' - Napsal jsem definici, ukazal logaritmickou vysku, nakreslil rotace. Popisoval jsem insert a delete, Koubek mi do toho zacal docela dost rypat, nejakou dobu jsme se nemohli poradne dohodnout, jak presne detekuji, ze se strom rozvazil. :) Nakonec jsme to nejak dali dohromady, ale asi se vyplati mit to opravdu vsechno promyslene, nez to jdete predvadet, abyste to nemuseli dovymyslet za behu.
}}
==== Definice ====
''Binární vyhledávací strom'' <math> T\,\!</math> reprezentující množinu prvků <math>S\,\;</math> z (uspořádaného) univerza <math>U\,\;</math> je úplný strom (tj. všechny vnitřní vrcholy mají 2 syny), ve kterém existuje bijekce mezi množinou <math> S\,\!</math> a ''vnitřními'' vrcholy taková, že pro <math> v\,\!</math> vnitřní vrchol stromu platí:
* všechny vrcholy podstromů levého syna jsou <math> \leq v\,\!</math>
* všechny vrcholy podstromů pravého syna jsou <math> >v\,\!</math>.
Listy reprezentují jednotlivé intervaly mezi vnitřními vrcholy. Můžeme je vynechat, ale s nimi je to (jak pro koho) logičtější.
====Základní operace na stromech====
* '''MEMBER''' -- test, zda prvek <math>x\,\;</math> je obsažen ve stromě (vyhledání, zpravidla s využitím invariantu )
* '''INSERT''' -- vložení prvku <math>x\,\;</math> do stromu
* '''DELETE''' -- odebrání prvku <math>x\,\;</math> ze stromu
* '''MIN''', '''MAX''', '''ORD''' -- nalezení prvního, posledního, <math> k\,\!</math>-tého největšího prvku
* '''SPLIT''' -- rozdělení stromu podle <math> x\,\!</math>, které vyhodí, je-li ve stromě
* '''JOIN''' -- spojení dvou stromů (jsou dvě verze, s přidáním prvku navíc, nebo bez něho)
===Obecná (nevyvážená) implementace===
* '''INSERT''': najít list reprezentující interval, kam vkládám, udělat z něj normální uzel se vkládanou hodnotou a dát mu dva listy s podintervaly.
* '''DELETE''': najdu vrchol, má-li jednoho syna-lista, pak druhý syn ho nahradí na jeho místě, jinak najdeme a dáme na jeho místo nejmenší větší vnitřní vrchol, jehož levý syn je list, a pravého syna tohoto vrcholu dáme na jeho místo.
* '''SPLIT''': procházím stromem a hledám <math> x\,\!</math>, ost. prvky házím cestou do dvou stromů <math> T_1,T_2\,\!</math>, ve kterých si vždy uchovávám ukazatel na list, místo kterého vkládám (odkrojím syna, ve kterém hledám dál, místo něj vložím list, na který si pamatuju ukazatel).
* '''JOIN''': s prvkem navíc, triviální -- spojím stromy jako 2 syny nového prvku.
Tato struktura sama nepodporuje efektivní '''ORD''', je nutné přidat navíc položky, které určují počet listů v podstromu každého vrcholu. ORD je pak jen jde do pravých synů a přičítá levé podstromy když může, jinak jde do levého syna (a nepřičte nic).
====Analýza algoritmů====
Definujme si pomocné hodnoty <math> \lambda,\pi\,\!</math> jako hodnoty nejbližšího menšího (levějšího), resp. většího (pravějšího) prvku na vyšší úrovni, nebo <math> -\infty\,\!</math>, resp. <math> +\infty\,\!</math>, pokud tyto prvky neexistují.
'''Korektnost vyhledávání''': Je-li <math> T'\,\!</math> podstrom <math> t\in T\,\!</math>, pak <math> T'\,\!</math> reprezentuje <math> S\cap(\lambda(t),\pi(t))\,\!</math> (a je to největší interval nezastoupený mimo <math> T'\,\!</math>). Pak pro vyhledání vrcholu <math> x\,\!</math> platí <math> \lambda(t)<x<\pi(t)\,\!</math>, vyšetřuji-li vrchol <math> t\,\!</math>.
Díky tomu je korektní '''MEMBER''' a '''INSERT'''. U '''DELETE''' musím dokázat korektnost případu s přehazováním vrcholů (dostávám bin. strom reprezentující <math> S\setminus\{x\}\,\!</math>).
Korektnost '''MIN''', '''MAX''', '''JOIN''' je zřejmá, u '''SPLIT''' plyne z korektnosti hledání a toho, že moje označené listy jsou nejlevější, resp. nejpravější.
Korektnost '''ORD''' plyne z toho, že v každém kroku je <math> k\,\!</math>-tý prvek představován tolikátým v pořadí vrcholů akt. vyšetřovaného podstromu, kolik mi zbývá přičíst.
'''Složitost''': Zpracování 1 vrcholu je vždy <math> O(1)\,\!</math> a alg. se pohybuje po nějaké cestě od kořene k listu, která má <math> O(h)\,\!</math>, kde <math> h\,\!</math> je výška stromu.
===Vyvažování===
Chceme-li pro zachování efektivity operací zajistit, že výška bude <math> O(\log|S|)\,\!</math>, přidáme pro strom další podmínky, které bude muset splňovat a operace je zachovávat.
[[Image:Stromy-rotace.png|frame|Rotace]]
Pro vyvažovací operace, které se snaží zachovat logaritmickou výšku, se používá pomocný algoritmus '''ROTACE'''<math> (u,v)\,\!</math>:
# Vezmu <math> v\,\!</math>, jeho pravého syna <math> u\,\!</math> a podstromy (zleva) <math> A,B,C\,\!</math>.
# Přehodím <math> v\,\!</math> pod <math> u\,\!</math>, upravím ukazatel v otci a přeházím podstromy.
Existuje i symetrický případ, kdy se postupuje přesně opačným směrem. Někdy se této dvojici operací říká '''LL-ROTACE''' a '''RR-ROTACE'''.
[[Image:Stromy-dvojrotace.png|frame|Dvojrotace]]
Další potřebný algoritmus je '''DVOJROTACE'''<math> (u,v,w)\,\!</math>:
# Vezmu <math> u\,\!</math>, jeho levého syna <math> v\,\!</math> a pravého syna <math>v\,\;</math> -- <math> w\,\!</math>
# Seřadím je tak, že <math> w\,\!</math> je otec obou, <math> u\,\!</math> vpravo a <math> v\,\!</math> vlevo.
# Přitom opět upravím ukazatele v nadřízeném uzlu a přepojím podstromy.
Taky existuje symetrický případ. Jiné označení je '''LR-ROTACE''' a '''RL-ROTACE'''.
U obou operací lze aktualizovat i počty listů v podstromě a obě pracují v <math> O(1)\,\!</math>.
====Alternativy k vyvažování====
Je velká pravděpodobnost, že i bez vyvažování strom zůstane <math> O(\log|S|)\,\!</math> vysoký a operace na něm můžou tak (bez vyvažování) běhat i rychleji. Proto existují i ''pravděpodobnostní postupy'', nahrazující vyvažování znáhodněním posloupností operací. Další možnost jsou ''samoopravující struktury'' -- operace samy bez dalších uchovávaných dat obstarávají vyvažování, existuje strategie, která zajistí dobré chování bez ohledu na data. Nebo se ''sleduje chování'' struktury, a když začne být příliš pomalá, vytvoří se nová -- vyvážená. Poslední možnost je ''upravit dat. strukturu podle známého pravděpodobnostního rozdělení'' dat.
===AVL-stromy===
''AVL-stromy (Adel'son-Velskii, Landis)'' jsou nejstarší vyvážené stromy, dodnes oblíbené, jednoduše definované, ale detailně technicky složité.
'''Podmínka AVL''' pro vyvažování: ''Výška pravého a levého podstromu lib. vrcholu se liší max. o 1''.
'''Definice''': <math> \eta(v)\,\!</math> -- výška vrcholu (délka nejdelší cesty z vrcholu do listů), <math> \omega(v)\,\!</math> -- rozdíl výšek levého a pravého podstromu (<math> \in\{-1,0,1\}\,\!</math>). Uchovávat potřebuji jenom <math> \omega\,\!</math>.
====Logaritmická výška====
{{Theorem|AVL strom o ''n'' vrcholech má výšku nejvýše 2·log(''n'')|logaritmická výška AVL}}'''Dk (indukcí):''' N(h) min počet vrcholů AVL stromu výšky h.
N(0)=1
N(1)=2
N(h)=1 + N(h-1) + N(h-2)
zřejmě platí N(h) > 2·N(h-2):
N(h) > 2·N(h-2)
> 2·(2·N(h-4)) = 2²·N(h-4)
> 2²·2·N(h-6) = 2³·N(h-6)
...
> 2ʰ<sup>/</sup>²
Dostanem N(h)>2ʰ<sup>/</sup>² a z toho vyjádříme h: h < 2·log N(h).
====Operace na AVL stromech====
Operace '''MEMBER''' je stejná jako pro nevyvážené.
'''INSERT''' se musí po běžném vložení zabývat vyvažováním. Jde zpět ke kořeni a hledá, který nejnižší vrchol <math> x\,\!</math> nemá po vložení vyvážené <math> \omega\,\!</math>, přičemž cestou upravuje <math> \omega\,\!</math>. Na vrcholu <math>x\,\!</math> se provede vhodná ROTACE nebo DVOJROTACE, což zajistí vyváženost (existuje několik podpřípadů).
Operace '''DELETE''' odstraní vrchol a pak vyvažuje podobně jako INSERT, ale potřebuje víc operací (až <math> O(\log|S|)\,\!</math> rotací). Asymptotická složitost je ale stejná -- logaritmická.
===Červeno-černé stromy===
''3'' povinné vlastnosti:
# Listy je '''černé'''.
# <font color=red>'''Červený'''</font> vrchol musí mít '''oba syny černé'''.
# Každá cesta od libovolného vrcholu k listům v jeho podstromě musí obsahovat stejný počet černých uzlů. Pro červeno-černé stromy se definuje ''černá výška uzlu'' (<math> \mathbf{bh}(x)\,\!</math>) jako počet černých uzlů na nejdelší cestě od uzlu k listu.
====Logaritmická výška====
{{Theorem|ČČ strom o ''n'' vrcholech má výšku O(log ''n'')|logaritmická výška ČČ}}'''Dk (přímo): '''k-poč.černých vrcholů v cestě k listu, n-počet vrcholů
<nowiki> </nowiki>minimální strom má všechny vrcholy černé (v cestě počtu k) ⇒ hloubka k-1 a počet vrcholu je 1+2+...+2<sup>k-1</sup> = 2<sup>k</sup>-1;
<nowiki> </nowiki>maximální: střídavě černé a červ. ⇒ hloubky 2k-1 a pocet vrcholu je 1+2+...+2<sup>2k-1</sup> = 2<sup>2k</sup>-1;
<nowiki> </nowiki>2<sup>k</sup>-1 ≤ n ≤ 2<sup>2k</sup>-1 ⇒ k ≤ log<sub>2</sub>(n + 1) ≤ 2k
<nowiki> </nowiki>a dále tedy k ≤ hloubka ≤ 2k ⇒ hloubka O(log n)
====Algoritmy====
U algoritmů '''INSERT''' a '''DELETE''' jde také o vložení a následné vyvažování. Bez porušení vlastností červeno-černých stromů lze kořen vždy přebarvit načerno, můžeme pro ně předpokládat, že ''kořen stromu'' je ''vždy černý''.
{{TODO|zkontrolovat operace, přepsat do formálních volání rotací}}
'''INSERT''' vypadá následovně:
* Vložený prvek se přebarví načerveno.
* Pokud je jeho otec černý, můžeme skončit -- vlastnosti stromů jsou splněné. Pokud je červený, musíme strom upravovat (předpokládejme, že otec přidávaného uzlu je levým synem, opačný připad je symetrický):
** Je-li i strýc červený, přebarvit otce a strýce načerno a přenést chybu o patro výš (je-li děd černý, končím, jinak můžu pokračovat až do kořene, který už lze přebarvovat beztrestně).
** Je-li strýc černý a přidaný uzel je levým synem, udělat pravou rotaci na dědovi a přebarvit uzly tak, aby odpovídaly vlastnostem stromů.
** Je-li strýc černý a přidaný uzel je pravým synem, udělat levou rotaci na otci a převést tak na předchozí případ.
'''DELETE''' se provádí takto:
* Skutečně odstraněný uzel (z přepojování -- viz [[#Obecn.C3.A1_.28nevyv.C3.A1.C5.BEen.C3.A1.29_implementace|obecné vyhledávácí stromy]]) má max. jednoho syna. Pokud odstraňovaný uzel byl červený, neporuším vlastnosti stromů, stejně tak pokud jeho syn byl červený -- to řeším přebarvením toho syna načerno.
* V opačném případě (tj. syn odebíraného -- <math> x\,\!</math> -- je černý) musím udělat násl. úpravy (předp., že <math> x\,\!</math> je levým synem svého nového otce, v opačném případě postupuji symetricky):
** <math> x\,\!</math> prohlásím za "dvojitě černý" ("porucha") a této vlastnosti se pokouším zbavit.
** Pokud je (nový) bratr <math> x\,\!</math> (buď <math> w\,\!</math>) červený, pak má 2 černé syny -- provedu levou rotaci na rodiči <math> x\,\!</math>, prohodím barvy rodiče <math> x\,\!</math> a uzlu <math> w\,\!</math> a převedu tak situaci na jeden z násl. případů:
*** Je-li <math> w\,\!</math> černý a má-li 2 černé syny, prohlásím <math> x\,\!</math> za černý a přebarvím <math> w\,\!</math> načerveno, rodiče přebarvím buď na černo (a končím) nebo na "dvojitě černou" a propaguji chybu (mohu dojít až do kořene, který lze přebarovat beztrestně).
*** Je-li <math> w\,\!</math> černý, jeho levý syn červený a pravý černý, vyměním barvy <math> w\,\!</math> s jeho levým synem a na <math> w\,\!</math> použiji pravou rotaci, čímž dostanu poslední případ:
*** Je-li <math> w\,\!</math> černý a jeho pravý syn červený, přebarvím pravého syna načerno, odstraním dvojitě černou z <math> x\,\!</math>, provedu levou rotaci na <math> w\,\!</math> a pokud měl původně <math> w\,\!</math> (a <math> x\,\!</math>) červeného otce, přebarvím <math> w\,\!</math> načerveno a tohoto (teď už levého syna <math> w\,\!</math>) přebarvím načerno.
'''MIN''' a '''MAX''' jsou stejné jako pro nevyvážené.
'''JOIN''' (s prvkem navíc): mám-li černou výšku u obou stejnou, není co řešit, pokud ne, projdu po tom s větší <math> \mathbf{bh}(x)\,\!</math> do patra, kde se výšky rovnají, půjčím si přísl. podstrom a slepím s ním, vrátím celek zpátky a aplikuji vyvažování, jako kdybych vložil 1 prvek (poruším výšku max. o 1).
'''SPLIT''': rozhazuji podstromy do zásobníků, odkud je pak slepuji operací '''JOIN'''.
Každý algoritmus pracuje jen s vrcholy na jedné cestě od kořene k listům a s každým dělá konstantně činností, takže všechny algoritmy mají logaritmickou složitost. DELETE volá max. 2 rotace nebo 1 rotaci a 1 dvojrotaci, INSERT zase max. 1 rotaci nebo dvojrotaci (i když přebarvovat můžou rekurzivně až do kořene).
{{collapse|Váhově vyvážené stromy (BB-α) - už se asi nezkouší|
Dnes jsou už na ústupu, ale občas se ještě používají. Mějme <math> 1/4<\alpha<1-\sqrt{2}/2\,\!</math>, označme <math> p(T)\,\!</math> počet listů ve stromě <math> T\,\!</math>. Pak strom je BB-<math> \alpha\,\!</math>, když
:<math>\alpha\leq\frac{p(T_{\mbox{levý}(v)})}{p(T_v)}\leq 1-\alpha\,\!</math>
pro <math> T_v\,\!</math> jako podstrom určený (každým) vrcholem <math> v\,\!</math>. O BB-<math> \alpha\,\!</math> stromech platí, že:
:výška<math>(T)\leq 1+\frac{\log(n+1)-1}{\log{\frac{1}{1-\alpha}}}\,\!</math>
Takže jsou také vyvážené a operace mají zaručenou logaritmickou hloubku, vyvažuje se na nich také rotacemi a dvojrotacemi. Vždy totiž existuje <math> \alpha\leq d\leq1-\alpha\,\!</math> takové, že když mám strom, jehož oba podstromy splňují vlastnosti a navíc <math> p(T_l)/p(T)\leq \alpha\,\!</math> a <math> p(T_l)/p(T)-1\,\!</math> nebo <math> p(T_l)+1/p(T)+1\,\!</math> vyhovuje, vezmu <math> \rho=\frac{p(T')}{p(T_r)}\,\!</math>, kde <math> T'\,\!</math> je určen levým synem <math> T_r\,\!</math>, a pro <math> \rho\leq d\,\!</math> provedu ROTACE(<math> T\,\!</math>, <math> T_r\,\!</math>), jinak DVOJROTACE(<math> T\,\!</math>, <math> T_r\,\!</math>, <math> T'\,\!</math>) a dostanu BB-<math> \alpha\,\!</math> strom (bez důkazu). Opačný případ je popsaný symetricky.
Mají pěknou vlastnost, kvůli které se používaly: pro <math> \forall \alpha\,\!</math> existuje <math> c>0\,\!</math> takové, že každá posloupnost <math> k\,\!</math> operací INSERT a DELETE volá max. <math> c\cdot k\,\!</math> rotací a dvojrotací.
}}
== B-Stromy a jejich varianty (6×🎓) ==
{{:Státnice_-_Stromové_vyhledávací_struktury_I2/B-Stromy}}
==Trie (🎓🎓🎓)==
{{Sources|
''Sekce o Trie je popsaná podle [http://ktiml.mff.cuni.cz/teaching/files/materials/dsii2.pdf Koubkových skript], [[TIN066 Skripta Vidner-Kotal|skript Vidner-Kotal]] a [http://www.mpi-inf.mpg.de/~mehlhorn/DatAlgbooks.html knihy K. Mehlhorna]'' -- [[User:Tuetschek|Tuetschek]] 10:43, 22 Aug 2010 (CEST)
}}
{{zkazky|
* '''Trie (2012, Koubek, Dvořák)''' - Taktéž lehce neočekáváné, naštěstí ne příliš těžké. Koubek ke me přiběhl lehce před oficiálním termínem, takže jsem ještě neměl hotový papír o komprimaci trie. Odříkal jsem mu základní definice, vlastnosti, ukázal vše na nakreslesném příkladu. Koubek, dobře si vědom mé schopnosti přesně definovat cokoliv, nelpěl příliš na detailech. Chtěl doplnit delete a pak jsme se vrhli na komprimaci, která trochu vázla, neb jsem ji neměl připravenou, ale nakonec jsme se dobrali výsledku. Dvořák přišel se záludným dotazem, co by se změnilo, kdyby to nebyl prefixový, ale sufixový strom. Otevřeně jsem přiznal, že nemám tušení a oba pak se slovy, že to nebylo v otázce, odkáčeli směr tabule.
* '''Hashovanie a trie (2011, I3 - Zeman)''' - Nastastie taka prehladova otazka, kedze som ju odpovedal ako poslednu, tvoril som to pocas odpovedania, rozpisal som druhy hashovania, potom zmienil univerzalne (principy ~ ku kazdej S vyberieme nejaku fciu z H, H c-univerzalna, napisal som funkciu h_ab(x), a ze je c-univerzalna), perfektne hashovanie, opat som zacal ako to principialne funguje a v polovici som bol zastaveny a ze mam este o triach porozpravat, tak som opat vysvetlil princip, dalej ako sa to potom komprimuje (v style, potom vznechame tie uzly, kde nedochadza k plodnemu vetveniu, potom to mozeme zapisat do tabulky, tu do dvoch poli, etc), spokojnost
* '''Trie (2011, P. Kucera)''' - Vedel jsem jen uplny zaklad jak to vypada a k cemu se to pouziva, celkove jsem popsal tak 1/2 stranky s kratkym prikladem. Cekal jsem, ze tohle mozna neprojde, ale Kucera jen rekl, ze to jsou jen ty trivialni veci, ze ty hezke, netrivialni se tykaji komprimace struktury, ale ze vim co to je, ze priklad, co jsem napsal se mu libi (bo nahodou jsem ho nacmaral tak, ze se na nem nedalo dobre ukazat, jak super je ta komprimace, co jsem neumel:) a pustil mne. 3
I1/I4:
* '''Trie(2014, Majerech)''' - Zakladni jsem dal, prvni komprimaci jsem se s nima trochu hadal, protoze me to prijde uplne blby (videl jsem to jinde definovane jinak, ale asi jenom pro asymptoticke vypocty, protoze tak jak je to v Koubkovy to opravdu dava smysl pro implementaci na realnym pocitaci). Komprimaci do listu mi Majerech vysvetlil, ja jsem o tom neco rekl (no OK to fakt nebylo).
* '''Trie(2012)'''
}}
Trie (z angl. retrieval) jsou stromova datova struktura urcena k reprezentaci "slovnikove" mnoziny. Jejich hlavni vyhodou je rychla operace member O(l). Dale zabiraji malo mista - pro ulozeni jednoho klice je treba jen amortizovane konstatni prostor. Taky se hodi pro hledani klice, ktery ma s hledanym (ale neobsazenym) klicem nejdelsi spolecny prefix (hledam ve slovniku "autol" a najde mi to "automat").
Universum U, jehoz nejakou podmnozinu S chceme reprezentovat tvori vsechna slova delky l nad nejakou mnozinou znaku (abeceda - \Sigma). Kratsi slova, ktera bychom chteli vlozit doplnime nejakym vhodnym znakem (mezerou).
Def: Trie nad \Sigma je konecny strom, jehoz kazdy vnitrni vrchlo ma prave k synu, ktere jsou jednoznacne ohodnoceny prvky \Sigma. Kazdemu vnitrnimu vrcholu trie odpovida slovo nad \Sigma delky nejvyse l: korenu odpovida prazdne slovo; kdyz vrcholu v odpovida slovo \alpha, pak v[a], synu v ohodnocenemu pismenem a, odpovida slovo \alphaa.
Trie nad \Sigma reprezentuje mnozinu S \subset U, jestlize:
1. Kazdemu listu je prirazena boolean fce Nal(t), vracejici true, jestlize slovo reprezentovane t \in S a false, jestlize slovo reprezentovane t \notin S.
2. (prefixova podminka) Pokud vnirtrni vrchol p odpovida slovu \alpha, tak \Exists slovo \beta \in S takove, ze \alpha je prefixem \beta
3. Pro kazde slovo \alpha \in S existuje v trie list odpovidajici \alpha.
Algoritmus 5.1 MEMBER pro základní verzi trie
{vyhledání x = x1 . . . xl}
t := kořen
i := 1
while t není list do
t := t[xi] // sestup podle znaku xi
i := i + 1
end while
return Nal(t)
Pouzivame jednotlive znaky k hledani dalsi cesty ve stromu. To umoznuje dosahnout slozitosti O(l).
Algoritmus 5.2 INSERT pro základní verzi trie
{vyhledej x pomocí operace MEMBER(x)}
if not Nal(t) then {trie nemusí být tak hluboké, jak potřebujeme}
while i <= l do
vrcholu t přidej k listů ohodnocených písmeny z \Sigma, jejich Nal := false
t := t[xi]
i := i + 1
end while
Nal(t) := true
end if
Najdi x, pokud neni, tak zkontroluj hladinu, pokud nejsi dost hluboko (jeste v trie neni reprezentovan zadny prvek se stejnym prefixem delky l-1), tak pridavej vnitrni vrcholy az do hloubky l.
Algoritmus 5.3 DELETE pro základní verzi trie
{vyhledej x pomocí operace MEMBER(x)} if Nal(t) then
Nal(t) := false
t := otec t
{opravíme prefixovou podmínku} while všichni synové t jsou listy s Nal = false do
zruš listy t
Nal(t) := false
t := otec t
end while
end if
Inverzne k insertu rusi vrcholy, ktere by nesplnovaly prefixovou podminku.
Slozitosti:
member O(l), insert/delete O(lk).
Pametova slozitost klesa od O(|S|lk) pro malo prvku (zadny spolecny prefix) po O(|S|), je -li reprezentovano cele U.
Komprimovane trie
Idea - v pripade, ze ma vnitrni vrchol nekomprimovaneho trie jen jednoho syna, neprinasi zadnou "pridanou hodnotu", protoze mnoziny prvku S reprezentovanych vrcholy v podstromu otce i syna jsou stejne.
Rozsirime puvodni trie o fce uroven(v) - vraci cislo urovne v odpovidajicim nekomprimovanem trie a slovo(v) - slovo odpovidajici v. Nyni lze vynechavat vrcholy, ktere maji jen jeden vrchol, ktery neni list s nal(x) = false a tohoto jednoho syna presunout na misto vynechaneho otce. To opakujeme, dokud takovy existuje.
Upraveny member pak vypada nasledovne.
Algoritmus 5.4 MEMBER pro komprimované trie
{vyhledání x = x1 . . . xl} t := kořen
while t není list do
i := uroven(t) + 1
t := t[xi] // xi-tý list
end while
return Nal(t) &&slovo(t) = x
Upravene operace insert/delete musi pripadne rozsirovat/kratit strom.
Slozitosti komprimovanych trii:
nejhure Member O(l), insert/delete O(l+k).
ocekavane: member O(logk(n)) insert/delete O(logk(n) + k)
pametova O(nk) - maximalne n vnitnich vrcholu, kazdy s k syny.
<hr>
''Trie'' je vlastně stromová reprezentace slovníku. Její označení zřejmě pochází od slova "retrieval". Jejím úkolem je reprezentovat množinu <math>S\subseteq U\,\!</math>, kde <math>U\,\!</math> je tvořeno všemy slovy nad abecedou <math>\Sigma, |\Sigma|=k\,\!</math> o délce <math>l\,\!</math>. Na této množině budeme provádět operace '''MEMBER''', '''INSERT''' a '''DELETE'''.
Požadavek na délku se použije pouze u odhadů na složitost algoritmů. Ve skutečnosti ale není omezující -- slova můžeme vždycky doplnit nějakými znaky mezery nebo lehce algoritmy upravit, aby s kratšími slovy počítaly.
=== Základní varianta ===
==== Definice ====
''Trie'' je strom takový, že každý vnitřní vrchol má <math>k\,\!</math> synů, odpovídajících všem znakům abecedy. Každému vrcholu lze rekurzivně přiřadit slovo nad abecedou <math>\Sigma\,\!</math> následujícím způsobem:
* Kořeni patří prázdné slovo <math>\lambda\,\!</math>.
* <math>a\,\!</math>-tému synu patří slovo otce doplněné o <math>a\,\!</math> (kde <math>a\,\!</math> je libovolné písmeno).
Pro každý vnitřní vrchol trie musí platit, že tento vrchol je prefixem nějakého slova z reprezentované množiny <math>S\,\!</math>. Každý list obsahuje jeden bit, který udává přítomnost nebo nepřítomnost slova, které představuje, v množině <math>S\,\!</math>.
Je vidět, že taková struktura je dost paměťově náročná -- každý vrchol potřebuje paměť <math>O(k)\,\!</math> a celkem máme aspoň tolik vrcholů, co bodů množiny, násobeno délkou cesty k nim, tedy <math>O(kl|S|)\,\!</math>.
====Operace====
'''MEMBER''' je velice jednoduchý -- postupně sestupuje stromem podél syna, který odpovídá <math>i\,\!</math>-tému písmenu hledaného slova v <math>i\,\!</math>-tém kroku. Pokud se dostane do listu dřív než dojde na konec slova, skončí neúspěchem. Jinak vrátí informaci o přítomnosti slova z listu, do kterého se dostal.
'''INSERT''' dojde do listu podobně jako '''MEMBER'''. Potom (je-li to potřeba) mění listy na vnitřní vrcholy a vkládá pokračování cesty až do dosažení délky slova. V posledním kroku upraví indikaci v listu.
'''DELETE''' vyhledá prvek a nastaví indikaci v jeho listu na FALSE. Pak se postupně vrací a dokud nalézá jen samé listy s FALSE, zruší celý vrchol a změní ho na list s FALSE.
Algoritmus '''MEMBER''' projde až <math>l\,\!</math> vrcholů a každý v konstantním čase (vrcholy se indexují přímo písmeny abecedy), tedy je <math>O(l)\,\!</math>. Algoritmy '''INSERT''' a '''DELETE''' vyžadují čas <math>O(kl)\,\!</math>, protože úprava jednoho vrcholu vyžaduje až <math>k\,\!</math> operací.
=== Komprimované Trie ===
Trie upravíme tak, že vyházíme vrcholy, jejichž slovo je prefixem stejné množiny slov jako slovo jejich otců (tj. vrcholy, kde nedochází k žádnému větvení a je jen jedna možnost pokračování). Ve vrcholech si teď ale místo toho musíme udržovat informaci o aktuální hloubce <math>\kappa(v)\,\!</math> a navíc v listech musíme držet celé slovo, které reprezentují (abychom neztratili písmena z vrcholů, které jsme vyházeli).
Operace pak bude třeba upravit, ale protože takto upravené trie má jen <math>S-1\,\!</math> vnitřních vrcholů, paměťová náročnost klesla na <math>O(k|S|)\,\!</math>
====Operace====
'''MEMBER''' pracuje podobně, ale ve vrcholu <math>v\,\!</math> vždy testuje <math>\kappa(v) + 1\,\!</math>-ní písmeno hledaného slova. Nakonec (protože neotestoval všechna písmena a mohlo by tedy dojít ke kolizi) navíc porovná slovo uložené ve vrcholu se slovem, které jsme hledali.
'''INSERT''' pro nějaké slovo <math>x\,\!</math> opět vyhledá místo pro vložení a dojde do listu, kde najde jiné slovo <math>y\,\!</math>. Pak vezme největší společný prefix slov <math>x,y\,\!</math> a v jeho místě strom rozdělí -- pokud ve správné hloubce už je vnitřní vrchol, pokračuje z něj, jinak nový dělící vrchol přidá. Potom upraví hodnoty v listech.
'''DELETE''' zruší informaci o mazaném slově stejně jako předtím. Navíc ale pokud zjistí, že otec "vyčištěného" listu v hierarchii stromu má jen jednoho dalšího potomka -- vnitřní uzel, nacpe tohoto potomka na jeho místo.
Je vidět, že '''INSERT''' a '''DELETE''' změní maximálně jeden vnitřní vrchol a pracují tak v <math>O(k+l)\,\!</math>.
====Očekávaná hloubka====
Odhady časů pro operace '''MEMBER''', '''INSERT''' a '''DELETE''' závisí na (maximální) délce slov <math>l\,\!</math>, ale takové hloubky komprimované trie dosáhne jen v nejhorším případě. Chceme proto odhad očekávané hloubky, za předpokladu, že reprezentovaná množina <math>S\,\!</math> je vzorkem dat z rovnoměrného rozdělení (což bývá často přibližně splněno).
Označíme <math>q_d\,\!</math> pravděpodobnost, že komprimovaný trie nad množinou <math>S, |S| = n\,\!</math> má hloubku aspoň <math>d_n = d\,\!</math>. Pak je naše očekávaná (střední) hodnota hloubky:
:<math>E(d_n) = \sum_{i=1}^{\infty} i(q_i - q_{i+1}) = \sum_{i=1}^{\infty} q_i\,\!</math>
Odhadneme proto velikost <math>q_d\,\!</math>. Víme, že hloubka trie je menší než <math>d\,\!</math>, když prefixy o délce <math>d\,\!</math> slov z naší množiny rozlišují tato slova jednoznačně. Pravděpodobnost, že toto nastane, je (počet jednoznačných prefixů a k nim počet libovolných doplnění do délky <math>l\,\!</math>, děleno počtem jednoznačných slov délky <math>l\,\!</math>, vše nad abecedou o velikosti <math>k\,\!</math>):
: <math>P(</math>jednoznačné rozlišení o délce <math>d\,\!</math>) <math> = \frac{\mathbf{}\binom{k^d}{n}k^{n(l-d)}}{\binom{k^l}{n}}\,\!</math>
Z toho:
: <math>q_d \leq 1 - P(</math>jednoznačné rozlišení o délce <math>d-1) = </math> <math>1 - \frac{\mathbf{}\binom{k^{(d-1)}}{n}k^{n(l-d+1)}}{\binom{k^l}{n}} \leq 1 - \frac{\left(\prod_{i=0}^{n-1}(k^{d-1}-i)\right)k^{n(l-d+1)}}{k^{nl}} = 1 - \prod_{i=0}^{n-1}\left(1 - \frac{i}{k^{d-1}}\right) \leq 1 - \exp\left(\frac{-n^2}{k^{d-1}}\right) \leq \frac{n^2}{k^{d-1}}</math>
Poslední kroky jsme mohli udělat, protože platí (integrál s nerovností můžeme použít, protože daný logaritmus je klesající, při výpočtu integrálu použijeme substituci za <math>1-\frac{x}{k^{d-1}}\,\!</math>):
:<math>\prod_{i=0}^{n-1}\left(1 - \frac{i}{k^{d-1}}\right) = \exp\left(\sum_{i=0}^{n-1}\ln\left(1-\frac{i}{k^{d-1}}\right)\right) \geq</math> <math>\geq \exp\left(\int_{0}^{n}\ln\left(1-\frac{x}{k^{d-1}}\right) \mathrm{d} x\right) = \exp\left((n-k^{d-1})\ln\left(1-\frac{n}{k^{d-i}}\right) - n\right) \leq \exp\left(\frac{-n^2}{k^{d-1}}\right)\,\!</math>
Očekávaná výška stromu pak vyjde, položíme-li <math>c = 2\lceil \log_k n\rceil\,\!</math>:
:<math>\sum_{i=1}^{\infty} q_i = \sum_{i=1}^c q_i + \sum_{i=c+1}^{\infty} q_i \leq \sum_{i=1}^{c} 1 + \sum_{i=c+1}^{\infty} \frac{n^2}{k^{i-1}} = c + \frac{n^2}{k^c}\left(\sum_{i=0}^{\infty}\frac{1}{k^i}\right) \leq 2\lceil \log_k n \rceil + \frac{1}{1-\frac{1}{k}}\,\!</math>
=== Trie v tabulce ===
Pokud se vzdáme operací '''INSERT''' a '''DELETE''', můžeme trie reprezentovat na extrémně zcvrklém prostoru. Nejdříve si ho představme jako matici <math>M\,\!</math> dimenze <math>r\times s\,\!</math>, kde každý vnitřní vrchol odpovídá jednomu řádku a sloupce jsou písmena abecedy. Potom na pozici <math>M(v,a)\,\!</math> je <math>a\,\!</math>-tý syn vrcholu <math>v\,\!</math>. Pole matice může obsahovat buď odkazy na další vrcholy (identifikátor řádku), nebo přímo slova, která jsou obsažena v reprezentované množině, nebo prázdnou hodnotu '''null'''. Ve vedlejším poli si musíme uchovat i hloubky vrcholů odpovídající nekomprimovanému trie -- <math>\kappa(v)\,\!</math>.
====Komprese matic -- uložení do pole====
Hodnoty '''null''' ale nepřinášejí novou informaci -- stačí při průchodu maticí na další vrcholy testovat, zda nám stoupá hodnota <math>\kappa(v)\,\!</math> a nakonec provést test shody s nalezeným prvkem. Díky tomu můžeme na místa, kde je '''null''', v klidu ukládat něco jiného.
Matici <math>M\,\!</math> tak můžeme reprezentovat dvěma poli
* <math>VAL\,\!</math> -- v něm budou hodnoty z různých řádků matice
* <math>RD\,\!</math> ("row displacement", "posunutí řádku") -- bude udávat, kde začíná který řádek původní matice <math>M\,\!</math> ve <math>VAL\,\!</math>
Jednotlivé datové řádky původní matice se v poli <math>VAL\,\!</math> v klidu můžou překrývat, pokud překryté hodnoty jsou jen '''null'''. Formálně musíme zachovat, že když <math>M(i,j)\,\!</math> je definováno, pak <math>M(i,j) = VAL(RD(i) + j)\,\!</math> a že když <math>M(i,j)\,\!</math> a <math>M(i',j')\,\!</math> jsou definovány pro <math>(i,j)\neq (i',j')\,\!</math> , pak <math>RD(i) + j \neq RD(i') + j'\,\!</math>.
Pro nalezení "dobrého" rozložení řádků původní matice do pole <math>VAL\,\!</math> se používá algoritmus '''First-Fit Decreasing''':
* Pro každý řádek původní matice <math>M\,\!</math> spočteme, kolik míst je non-'''null''' a setřídíme řádky matice podle této hodnoty v klesajícím pořadí
* Bereme řádky podle setřídění a vkládáme je na první místo od začátku pole <math>VAL\,\!</math> tak, že neporušují výše uvedené podmínky.
Označíme počet všech non-'''null''' hodnot jako <math>m\,\!</math> a počet non-'''null''' hodnot v řádcích s alespoň <math>l\,\!</math> non-'''null''' hodnotami jako <math>m_l\,\!</math>. Pokud řádky matice <math>M\,\!</math> splňují pravidlo ''harmonického rozpadu'', tj. <math>\forall l: m_l\leq \frac{m}{l+1}\,\!</math> (tj. např. více než polovina řádků obsahuje jen jednu skutečnou hodnotu), pak pro každý řádek <math>i\,\!</math> platí <math>RD(i)<m\,\!</math> a algoritmus stavby polí potřebuje <math>O(rs+m^2)\,\!</math> času (důkaz je hnusný).
====Posouvání sloupců====
Protože podmínku ''harmonického rozpadu'' splňuje jen málo matic, upravíme si obecné matice tak, aby ji splňovaly taky. Využijeme toho, že matici trochu "natáhneme" do počtu řádků (tím se, pravda, zvětší pole <math>RD\,\!</math>) a jednotlivé sloupce v ní rozstrkáme tak, aby v jednom řádku nevyšlo moc zaplněných míst najednou. Kde začíná který sloupec si zapamatujeme v dalším pomocném poli <math>CD\,\!</math> ("column displacement", "posunutí sloupce").
"Dobré" posunutí sloupců nalezneme obyčejným přístupem '''First-Fit''', když pro každý sloupec <math>j\,\!</math> nalezneme nejmenší číslo <math>CD(j)\,\!</math> splňující:
:<math>m(j+1)_l\leq \frac{m}{f(l,m(j+1))}\ \forall l = 0,1,\dots\,\!</math>
Hodnota <math>m(j)\,\!</math> je počet všech zaplněných míst v prvních <math>j\,\!</math> sloupcích právě konstruované matice a <math>m(j)_l\,\!</math> je počet zaplněných míst v řádcích s alespoň <math>l\,\!</math> zaplněnými místy.
Pozorování:
* Je vidět, že každá funkce <math>f\,\!</math> musí splňovat <math>f(0,m(j))\leq \frac{m}{m(j)}\ \forall j\,\!</math>, protože jinak by v algoritmu nemohla být splněna testovaná podmínka pro <math>l=0\,\!</math> (protože <math>m_j = m(j)_0\,\!</math>).
* Dále musí funkce <math>f\,\!</math> splňovat nerovnost <math>f(l,m)\leq l+1\ \forall l\,\!</math>, aby výsledná matice splňovala podmínku ''harmonického rozpadu''.
Dá se ukázat (a je to hnusný důkaz), že vhodná funkce je třeba <math>f(x,y) = 2^{x(2-\frac{y}{m})}\,\!</math>, protože splňuje obě podmínky a navíc výsledný vektor <math>CD\,\!</math> má délku <math>s\,\!</math>, vektor <math>RD\,\!</math> má délku menší než <math>4m\log\log m + 15.3m + r\,\!</math> a vektor <math>VAL\,\!</math> má délku menší než <math>m+s\,\!</math>. Protože hodnoty <math>CD\,\!</math> indexují <math>RD\,\!</math> a hodnoty <math>RD\,\!</math> indexují <math>VAL\,\!</math>, plynou z toho omezení i na hodnoty v nich uložené.
Čas celého algoritmu vytváření matic je <math>O(s(r+m\log\log m)^2)\,\!</math>.
====Další komprese vektoru RD====
Protože <math>M\,\!</math> má jen <math>m\,\!</math> definovaných mít, z algoritmu pro výpočet <math>RD\,\!</math> plyne, že jen max. <math>m\,\!</math> míst v tomto vektoru bude různých od nuly. Proto můžeme použít následující kompresi (řekněme, že nenulových míst je <math>t\,\!</math>):
# Vektor <math>RD\,\!</math> rozdělíme na <math>n\,\!</math> bloků o délce <math>d\,\!</math>.
# Vytvoříme nový vektor <math>CRD\,\!</math> o délce <math>t\,\!</math>, který obsahuje jen nenulové prvky původního vektoru. Označme jejich původní pozice <math>i_j, j = 0\dots t-1\,\!</math> a jejich pozice ve vektoru <math>CRD\,\!</math> jako <math>v(i_j)\,\!</math>.
# Vytvoříme vektor <math>BASE\,\!</math> o délce <math>n\,\!</math>, kde <math>BASE(x) = \begin{cases}-1 & i_j \div d \neq x\ \forall j = 0,\dots t-1 \\ \min\{l; i_l\div d = x\} & \mbox{jinak}\end{cases}\,\!</math>{{ref|1}}
# Vytvoříme matici <math>OFFSET\,\!</math> typu <math>n\times d\,\!</math>, kde <math>OFFSET(x,y) = \begin{cases} -1 & x\cdot d + y \neq i_j\ \forall j \\ j - BASE(x) & x\cdot d + y = i_j \end{cases}\,\!</math>
# Uložíme matici <math>OFFSET\,\!</math> do vektoru <math>OFF\,\!</math> dimenze <math>n\,\!</math> tak, že z každého řádku vytvoříme číslo v soustavě o základu <math>d+1\,\!</math>: <math>OFF(x) = \sum_{k=0}^{d-1}(OFFSET(x,k)+1)(d+1)^{k}\,\!</math>.
Potom platí, že:
* <math>v(h) = 0 \Leftrightarrow OFFSET(h\div d, h\mod d) = -1\,\!</math>
* <math>v(h) = 1 \Rightarrow h = BASE(h\div d) + OFFSET(h\div d, h\mod d)\,\!</math>
* <math>OFFSET(i,j) = ((OFF(i)\div (d+1)^j)\mod (d+1)) -1\,\!</math>
Celá tahle legrace má smysl, jen pokud <math>d\ll n,\;</math> a <math>t<n\,\!</math>. Když <math>d\leq \lceil \log\log n\rceil\,\!</math>, pak lze celé trie uložit pomocí pěti vektorů dimenze <math>n\,\!</math> s hodnotami menšími než <math>4n\log\log n\,\!</math>.
----
{{note|1|Funkce <math>\div\,\!</math> tu označuje celočíselné dělení (podobné operaci <tt>div</tt> z Pascalu).}}
==Haldy (9×🎓)==
{{zkazky|
* '''Fibonacciho haldy (2014, Hladík)''' - Lehce nečekané (jedna z těch věcí, kde si člověk říká o haldách člověk něco řekne ale pak ...). Začal jsem úvodem co jsou haldy, napsal něco o Leftist, D-Reg., Polynom a nakonec Fibonachi. Popis struktury (les) a omezení (oproti poly. je rozvoleněné), jak pracuje "konsolidace" (spojování stromů stejných stupňů), označení vrcholů, vztah k Fibonacciho číslům. Popsání operací insert, merge, delete, delete-min + v diskusi pak složitosti. Padla otázka na definici .?. nakonec to prošlo +- přes "operace". Zmínění ostatních hald pan Hladík nejprve při diskusi přeskočili (neb to nebylo otázkou), ale dalo se na ně hezky referovat pro "porovnání".
* '''Fibonacciho haldy (2013, Hladík)''' - Základně jsem popsal d-regulární a binomiální haldy a složitost operací (to ho moc nezajímalo). Pak, že FH jsou definované pomocí posloupnosti operací + popis operací (stačilo slovně). Trochu jsem plaval v dokazování složitosti (stačila amortizovaná), ale důležité bylo ukázat, že vím, proč jsou ty operace definované tak, jak jsou (jak ovlivňují složitost). Nakonec dotaz, kde se využívají a jaké mají výhody proti ostatním strukturám/haldám. Celkově byl zkoušející v pohodě.
* '''Haldy (2012, Koubkova)''' - Regularni haldy -- co jsou, k cemu jsou, Min/Max heap, Insert, ExtractMin, Delete, pouziti, implementace v poli, Binomiální haldy, Fibbonaciho haldy, nasledne diskuse
* '''Haldy (2012, Žemlička)''' - Popsal jsem binární (s tím, že je tom jenom jednoduchý případ d-regulární), binomiální, a Fibonacciho, u Fibonacciho jsem si nebyl jistý, jak se počítá amortizovaná složitost, protože mi vycházelo, že by mohla být konstantní, ale Žemličkovi se to nechtělo moc řešit, tak se mě zeptal, kdy bych kterou haldu použil a jaké mají prostorové náročnosti a byl spokojený.
* '''Haldy a trie (2011, Kopecky)''' - priznam se, ze me celkem zaskocilo, ze jsem nedostal jen jeden/dva typy hald, respektive ze k tomu byly i trie. Pan Kopecky se zeptal, za jak dlouho to asi bude trvat, nacez jsem odpovedel, ze pokud mam napsat vse, co vim tak asi hodinu a pul Navrhl jsem zkouseni "on-the-fly", protoze toto jsem celkem umel, ale pan Kopecky chtel byt korektni a nechal mi tedy asi 20min na pripravu, to jsem stale psal a tak tedy vzhledem k pokrocile dobe prikyvnul, ze mu to mam povykladat to co mam na papire + treba neco kolem. Probrali jsme tedy d-regularni haldy, binomialni, tam jsme to cele ani nedodelali, zacal jsem fibinacciho a tam bylo prohlaseno, ze to umim a ze to staci. Coz jsem byl rad, protoze trie jsem umel uz mene Znamka: 1
* '''Haldy (2011, Majerech)''' - Co a jak zkouší: Dobrý je přehled o haldách obecně (co od nich nejlepšího můžu očekávat, jakou asymptotickou/amortizovanou složitost). Logaritmus tam vždy u nějaké operace vždy bude. d-reg. haldy prý nesnáší, ale v klidu je zkoušel. Odráží se totiž od toho, co máte napsané. Řekl, že nemám zmiňovat leftist haldy, když nevím, jak vypadají, že by se na to neptal.
* '''Haldy a fibonacciho haldy (2010, Fiala)''' - asi na 3/4 stranu som si rozpísal d-reg., bionom. a lazy. binom haldy (čo to je, aké sú tam operácie, ako približne fungujú, aká je cca. (amortizovaná) O() :)), na fibonacciho mi ostalo pár riadkov na konci... väčšinu odpovede som strávil zbežnými komentármi k haldám, takže po pár minútach som asi vyčerpal trpezlivosť a pri fibonacciho sme len prediskutovali, aké majú výhody (decrease/increase key, delete, O(1) atď...) a bolo hotovo..
* '''Haldy (2010, Koubkova)''' - d-regularni, binomialni, leftist, fibbonaci. Ukazat pridavani / odebirani prvku v d-regularni a binomialni.
* '''Haldy (2009, Čepek)''' - Definice + operace binární haldy, binomiální haldy, Fibonacciho haldy + dotaz, jak se (implementačně) řeší přístup na prvek haldy (třeba fuprostřed nějakého stromu Fib. haldy (Odpověď: pole ukazatelů do haldy indexované čísly vrcholů)
I1/I4:
* '''Fibonacciho haldy (2014, Koubek) -'''
Další nemilá otázka, navíc jsem podcenil přípravu na papír, kterou
Koubek podrobně zkoumal. Čekal jsem, že to doplním během diskuze, ale
nedostal jsem moc šanci. Pokud vás bude zkoušet, raději si vezměte víc
času na přípravu na papír a pořádně to tam napište. Koubek je puntičkář a
<nowiki> </nowiki>nelíbí se mu, když člověk zapomíná předpoklady k tvrzením, apod.
Koubek byl velmi zklamaný, nakonec mi dal 3-, že se mám ještě snažit.
* '''Haldy (2013, MJ)''' - Popsal jsem definice a (hodne) strucne i operace. D-reg se vsim vsudy, i dotaz na vysku stromu. Leftist haldy byly jen s definici a popiskem, ze se vyvazuji utrzenim podstromu a prohazovanim synu. Binomialni v pohode bez dukazu (stacilo rict <math>|B_i| = 2^i</math>). Line haldy - motal jsem se v amort. slozitosti, takze me nechali ji spocitat, jinak by to ale asi slo i bez ni. Fibonacciho opet bez dukazu, jen jsem opet motal amort. slozitost, tak jsem jim ji radsi spocital. Pak chteli nejake aplikace - heapsort, dijkstra. Pro me novy poznatek: "Proc bychom mohli chtit u d-reg hald zvysovat d? Kdyz nas nezajimaji nejake male konstanty, tj. ty hodnoty mezi 4-6, o kterych se pise, ze jsou idealni pro vnitrni trideni?" Odpoved znela, ze v Dijkstrovi pouziju DELETEMIN jen |V|-krat, kdezto DECREASE az |E|-krat. Zvetseni d mi sice zhorsi DELETEMIN (bublani dolu je kvuli vice synum pomalejsi), ale zase zlepsi DECREASEKEY (haldy jsou mensi).
* '''Haldy (2012, Koubek)''' - popsal jsem d-regulární haldy, zmínil jsem se o tom, že existují leftist haldy a popsal jsem binomiální haldy. Pana profesora ale zajímaly hlavně Fibonacciho haldy, jejichž složitost jsem nedokázal uspokojivě vysvětlit. Doporučení: ty algoritmy si OPRAVDU projděte.
* '''Fibonacciho haldy (Koubek)'''
}}
Haldy se používají pro měnící se uspořádané množiny. Nevyžaduje se efektivní operace '''MEMBER''' (často se předpokládá s argumentem operace informace o uložení prvku). Požadují se malé nároky na paměť a rychlost ostatních operací.
==== Definice, operace ====
Halda je stromová struktura nad množinou (dat) <math>S\,\!</math>, jejíž uspořádání je dáno funkcí <math> f:S\to \mathbb{R}\,\!</math>, splňující ''lokální podmínku haldy'':
:<math> \forall v\in S: f(\,\!</math>otec<math> (v))\leq f(v)\,\!</math>, případně v duální podobě.
Množina ''je reprezentovaná'' haldou, když přiřazení prvků vrcholům haldy je bijekce, splňující podmínku haldy. Různé druhy hald se liší podle dalších podmínek, které musí splňovat stromové struktury.
* Krom běžných operací můžu měnit uspořádání: operace '''INCREASE''' a '''DECREASE''' změní velikost <math> f\,\!</math> na nějakém daném prvku <math> s\,\!</math> se známým uložením o <math> +a\,\!</math>, <math> -a\,\!</math>.
* Další operace: '''DELETEMIN''' -- smazání prvku s nejmenší hodnotou <math> f\,\!</math>.
* Pro operaci '''DELETE''' budeme požadovat přímé zadání uložení prvku.
* Navíc definujeme operaci '''MAKEHEAP''' -- vytvoření haldy při známé množině a <math> f\,\!</math>,
* a ''' MERGE''' -- slití dvou hald do jedné, reprezentující <math> S_1 \cup S_2\,\!</math> a <math> f_1\cup f_2\,\!</math>, aniž by se ověřovala disjunktnost.
===Regulární haldy===
Pro <math> d\,\!</math>-regulární strom (<math> d\in\mathbb{N}\,\!</math>) s kořenem <math> r\,\!</math> platí, že existuje pořadí synů vnitřních vrcholů takové, že očíslování prohledáváním z <math> r\,\!</math> do šířky splňuje:
# každý vrchol má nejvýše <math> d\,\!</math> synů
# když vrchol není list, tak všechny vrcholy s menším číslem mají právě <math> d\,\!</math> synů
# má-li vrchol méně než <math> d\,\!</math> synů, pak všechny vrcholy s většími čísly jsou listy
Potom takový strom s <math> n\,\!</math> vrcholy má max. jeden ne-list, který nemá právě <math> d\,\!</math> synů, jeho výška je <math> \lceil\log_d(n(d-1)+1)\rceil\,\!</math>. Čísla synů vrcholu s číslem <math> k\,\!</math> jsou <math> (k-1)d+2,\dots,kd+1\,\!</math>, číslo otce je <math> 1+\lfloor\frac{k-2}{d}\rfloor\,\!</math>. Takto vytvořená halda umožňuje i efektivní reprezentaci v poli.
==== Operace na regulárních haldách ====
* Není známa efektivní operace '''MERGE'''.
* Máme pomocné operace '''UP''', '''DOWN''', posunující prvek níž/výš ve struktuře, dokud není splněna podmínka haldy ("probublávání").
* '''INSERT''' jen vloží nový prvek za poslední a spustí '''UP'''
* '''DELETE''' nahradí odstraněný prvek posledním listem a volá '''UP''' nebo '''DOWN''' podle potřeby
* '''DELETEMIN''' odstraní kořen, nahradí ho posl. listem a volá '''DOWN'''
* '''MIN''' jen vrátí kořen
* '''INCREASE''' a '''DECREASE''' změní hodnotu <math> f\,\!</math> nějakého prvku a zavolají '''DOWN''', resp. '''UP''' (pozor, je to naopak, než názvy napovídají).
* Operace '''MAKEHEAP''' vytvoří libovolný strom a pak postupně od posledního ne-listu ke kořeni volá na všechno '''DOWN'''.
U všech operací je korektnost zajištěna podmínkou haldy (a tím, že '''UP''' a '''DOWN''' zaručí její splnění).
====Složitost operací====
Běh '''DOWN''' vyžaduje <math> O(d)\,\!</math> a '''UP''' <math> O(1)\,\!</math> v každém cyklu, takže celkem jde o <math> O(d\log|S|)\,\!</math> a <math> O(\log|S|)\,\!</math>.
Haldu lze vytvořit opakovaným '''INSERT'''em v čase <math> |S|\log|S|\,\!</math>, ale pro větší množiny je rychlejší '''MAKEHEAP''' -- uvažujeme-li, že operace '''DOWN''' vyžaduje čas odpovídající výšce vrcholu. Ve výšce <math>k-i\,\;</math> je <math>d^i\,\;</math> vrcholů. Tím dostávám celkový čas <math> O(\sum_{i=0}^{k-1}d^i(k-i)d)\,\!</math>, což se dá odhadnout jako <math> O(d^2|S|)\,\!</math>.
====Aplikace====
''Heapsort'' -- vytvoření haldy a postupné volání '''MIN''' a '''DELETEMIN'''. Lze ukázat, že pro <math> d=3,d=4\,\!</math> je výhodnější než <math> d=2\,\!</math>, empiricky je do cca <math> 1 000 000\,\!</math> prvků <math> d=6\,\!</math> nebo <math> d=7\,\!</math> nejlepší. Pro delší posloupnosti je možné <math> d\,\!</math> zmenšit.
''Dijkstra'' -- normální Dijkstrův algoritmus, jen vrcholy grafu uchovávám v haldě, tříděné podle aktuálního <math> d\,\!</math> (horního odhadu vzdálenosti). Složitost <math> O((m+n)\log n)\,\!</math>, pro <math> d=\max\{2,\frac{m}{n}\}\,\!</math> je to <math> O(m\log_d n)\,\!</math> a pro husté grafy (<math> m>n^{1+\varepsilon}\,\!</math>) je lineární v <math> m\,\!</math>.
===Leftist haldy===
Leftist halda je binární strom (<math> T,r\,\!</math>). Označme npl(<math> v\,\!</math>) délku nejkratší cesty z <math> v\,\!</math> do vrcholu s max. 1 synem. Leftist halda musí splňovat následující podmínky:
# má-li vrchol 1 syna, pak je vždy levý
# má-li 2 syny <math> l,p\,\!</math> , pak npl(<math> p\,\!</math>)<math> \leq\,\!</math>npl(<math> l\,\!</math>)
# podmínka haldy na klíče prvků (ex. přiřazení prvků vrcholům stromu)
Pro leftist haldu se definuje pravá cesta (posl. pravých synů) a pokud máme takovou cestu délky <math> k\,\!</math> z vrcholu <math> v\,\!</math>, víme, že podstrom <math> v\,\!</math> do hloubky <math> k\,\!</math> je úplný binární strom. Délka pravé cesty z každého vrcholu je tedy logaritmická ve velikosti podstromu.
Operace jsou založeny na algoritmech '''MERGE''' a '''DECREASE'''.
* '''MERGE''' testuje prázdnost jednoho ze stromů (a pokud je jeden prázdný, vrátí ten druhý jako výsledek). Pokud ne, volá se rekurzivně na podstrom pravého syna kořene s menším klíčem dohromady s celým druhým a výsledek připojí místo onoho pravého syna. Pokud neplatí podmínka na npl, syny vymění.
* '''INSERT''' je to samé co vytvoření jednoprvkové haldy a zavolání '''MERGE'''.
* '''DELETEMIN''' je z'''MERGE'''ování synů kořene (a jeho zahození).
* '''MAKEHEAP''' je vytvoření hald z jednotl. prvků. Nacpu je do fronty a potom v cyklu vyberu dva první, zmerguju a hodím výsledek na konec, dokud mám ve frontě víc než 1 haldu.
'''INCREASE''' a '''DECREASE''' se dělají jinak.
* Mám pomocnou operaci '''OPRAV''', která odtrhne podstrom a dopočítá všem vrcholům správné npl. Po odtržení vrcholu a příp. přehození pravého syna doleva jde nahoru, dokud provádí změny npl (možno až do kořene), vztahuje npl odspoda a příp. prohazuje syny.
* '''DECREASE''' se pak udělá snížením hodnoty ve vrcholu, zavoláním '''OPRAV''', tj. jeho odříznutím od zbytku haldy, a '''MERGE''' podstromu a zbytku.
'''INCREASE''': zapamatuju si levý a pravý podstrom vrcholu s mým prvkem a provedu na něj '''OPRAV''' (vyhodím ho), potom vyrobím nový vrchol s mým prvkem se zvednutou hodnotou a jako samostatnou haldu ho z'''MERGE'''uju s levým podstromem. Pravý podstrom z'''MERGE'''uju se zbytkem haldy a nakonec s tím z'''MERGE'''uju výsledek '''MERGE''' levého podstromu a zvednutého prvku.
====Složitost====
1 běh '''MERGE''' bez rekurze je <math> O(1)\,\!</math>, hloubka rekurze je omezena pravými cestami, takže je to <math> O(\log(|S_1|+|S_2|))\,\!</math>. Z toho plyne logaritmovost '''INSERT''' a '''DELETEMIN'''.
Pro '''MAKEHEAP''' se uvažuje, kolikrát projdou haldy frontou: po <math> k\,\!</math> projití frontou mají velikost <math> 2^{k-1}\,\!</math> a tedy fronta obsahuje <math> \lceil\frac{|S|}{2^{k-1}}\rceil\,\!</math> hald. Jeden '''MERGE''' je <math>O(k)</math> a jedno projití frontou pro všechny haldy tedy trvá <math> O(k\lceil\frac{|S|}{2^{k-1}}\rceil)\,\!</math>. Celkem dostávám <math> O(|S|\sum_{k=1}^{\infty}\frac{k}{2^{k-1}})=O(|S|)\,\!</math> (součet řady je <math> 4\,\!</math>).
'''OPRAV''' chodí jen po pravé cestě, takže má logaritmickou složitost. '''INSERT''', '''INCREASE''' a '''DECREASE''' se díky ní dostanou taky na <math> O(\log|S|)\,\!</math>, protože jejich části kromě '''MERGE''' a '''OPRAV''' mají konstantní složitost.
===Binomiální haldy===
''Binomiální stromy'' se definují rekurentně jako <math> H_i\,\!</math>, kde <math> H_0\,\!</math> je jednoprvkový a <math> H_{i+1}\,\!</math> vznikne z dvou <math> H_i\,\!</math>, kdy se kořen jednoho stane dalším (krajním) synem kořenu druhého. Pak strom <math> H_i\,\!</math> má <math> 2^i\,\!</math> prvků, jeho kořen má <math> i\,\!</math> synů, jeho výška je <math> i\,\!</math> a podstromy určené syny kořene jsou právě <math> H_{i-1},\dots,H_0\,\!</math>.
''Binomiální halda'' reprezentující <math> S\,\!</math> je seznam stromů <math> T_i\,\!</math> takový, že celkový počet vrcholů v těchto stromech je <math> |S|\,\!</math> a je dáno jednoznačné přiřazení prvků vrcholům, respektující podmínku haldy. Každý strom je přitom izomorfní s nějakým <math> H_i\,\!</math> a dva <math> T_i,T_j, i\neq j\,\!</math> nejsou izomorfní.
Existence binomiální haldy pro každé přirozené <math> |S|\,\!</math> plyne z existence dvojkového zápisu čísla.
====Operace====
Operace na binomiálních haldách jsou založené na MERGE.
* '''MERGE''' pracuje stejně jako binární sčítání -- za pomoci operace '''SPOJ''' (slepení dvou stromů, přilepím jako syna toho, který má v kořeni vyšší klíč) slepí stromy stejného řádu, přenáší výsledky do dalšího spojování (přenos + obě haldy mající strom daného řádu = vyplivnutí 1 stromu na výsledek a spojení zbývajících dvou).
* '''INSERT''' je MERGE s jednoprvkovou haldou.
* '''MIN''' je projití kořenů a vypsání nejmenšího.
* '''DELETEMIN''' je '''MIN''', odebrání stromu s nejmenším prvkem v kořeni a přidání ('''MERGE''') podstromů jeho kořene do haldy.
* '''INCREASE''' a '''DECREASE''' se dělají úplně stejně jako u regulárních hald.
* Přímo není podporováno '''DELETE''', jen jako '''DECREASE''' + '''DELETEMIN'''.
* '''MAKEHEAP''' se provádí opakováním '''INSERT'''.
Složitost '''MERGE''' je <math> O(\log|S_1|+\log|S_2|)\,\!</math>, protože 1 krok '''SPOJ''' je konstantní. Halda má nejvýše <math> \log|S|\,\!</math> stromů, takže '''MIN''' a '''DELETEMIN''' mají tuto složitost. Výška všech stromů je <math> \leq\log|S|\,\!</math>, což dává složitost '''INCREASE''' <math> O(\log^2|S|)\,\!</math> a '''DECREASE''' <math> O(\log|S|)\,\!</math>. Pro odhad složitosti '''MAKEHEAP''' se použije amortizovaná složitost přičítání jedničky k binárnímu číslu, což je <math> O(1)\,\!</math>, tedy celkem <math> O(|S|)\,\!</math>.
====Líná implementace====
Vynecháme předpoklad neexistence dvou izomorfních stromů v haldě a budeme "vyvažování" provádět jen u operací '''MIN''' a '''DELETEMIN''', kdy se stejně musí projít všechny stromy. '''MERGE''' je pak prosté slepení seznamů hald. Vyvažování se provádí operací '''VYVAZ''', která sloučí izomorfní stromy (podobně jako '''MERGE''' z pilné implementace).
Složitost '''INSERT''' a '''MERGE''' je <math> O(1)\,\!</math>, ale '''DELETEMIN''' a '''MIN''' v nejhorším případě <math> O(|S|)\,\!</math>.
Amortizovaná složitost vychází ale líp: použijeme [[St%C3%A1tnice_-_Odhady_slo%C5%BEitosti#Algoritmus_.28Potenci.C3.A1lov.C3.A1_metoda.29|potenciálovou metodu]], když za hodnocení konfigurace <math>w(H)\,\;</math> zvolíme počet stromů v haldě <math>|\mathcal{H}|\,\!</math>. '''INSERT''' a '''MERGE''' ho nemění, resp. mění o <math> 1\,\!</math>, takže jsou stále <math> O(1)\,\!</math>.
Operace '''VYVAZ''' potřebuje <math> O(|H|)\,\!</math>, protože slití dvou stromů trvá konstantně dlouho a nelze slévat víc stromů, než kolik jich je v haldě. Kromě operace '''VYVAZ''' potřebuje '''MIN''' <math> O(|\mathcal{H}|)\,\!</math> a '''DELETEMIN''' <math> O(|\mathcal{H}|+\log|S|)\,\!</math> (max. stupeň stromu je logaritmický).
Dohromady vychází amortizovaná složitost pro '''MIN''': <math>am(o) = t(o) - w(H) + w(H') = O(|\mathcal{H}|-|\mathcal{H}|+\log|S|)\,\!</math>, protože výsledný počet stromů <math>|H'|\,\;</math> odpovídá pilné implementaci. Pro '''DELETEMIN''' podobně dostanu <math> O(|\mathcal{H}|+\log|S|-|\mathcal{H}|+\log|S|)=O(\log|S|)\,\!</math>.
===Fibonacciho haldy===
Definují se jako množiny stromů, které splňují podmínku haldy a ''musely vzniknout posloupností operací z prázdné haldy''. Všechny operace zachovávají podmínku, že jednomu vrcholu lze odříznout max. dva syny. Strom má ''rank'' <math> i\,\!</math>, má-li jeho kořen <math> i\,\!</math> synů (podobné jako izomorfismus s <math> H_i\,\!</math> u binomiálních hald).
Podmínka odříznutí max. dvou synů se zachovává pomocnou operací '''VYVAZ2'''. Když vrchol není kořen a byl mu předtím někdy odříznut syn, je speciálně označený. '''VYVAZ2''' prochází od daného vrcholu ke kořeni a dokud nalézá označené vrcholy, odtrhává je i s jejich podstromy, ruší jejich označení a vkládá do haldy jako zvláštní stromy. Když se vrchol stane kořenem, označení se zapomene.
====Operace====
'''MERGE, INSERT, MIN''' a '''DELETEMIN''' jsou stejné jako v líné implementaci binomiálních hald, jen požadavek na isomorfismus s <math> H_i\,\!</math> je nahrazen požadavkem na daný rank. Pomocné operace z binomiálních hald '''VYVAZ''' a '''SPOJ''' jsou také stejné.
'''DECREASE, INCREASE''' a '''DELETE''' vycházejí z leftist hald. Používají pomocnou operaci '''VYVAZ2'''
* '''DECREASE''' odtrhne podstrom určený snižovaným vrcholem (není-li to už kořen), zruší u něj případné označení a vloží ho zvlášť do haldy, na odtržené místo zavolá '''VYVAZ2'''.
* '''INCREASE''' provede to samé, jen ještě roztrhá podstrom zvedaného vrcholu (odtrhne všechny syny, zruší jejich příp. označení a vloží jako samostatné stromy do haldy) a vloží zvednutý vrchol do haldy zvlášť.
* '''DELETE''' je to samé co '''INCREASE''', bez přidání vrcholu zpět do haldy.
====Korektnost a složitost====
Operace '''SPOJ''' podobně jako u binomiálních hald vyrobí ze dvou stromů ranku <math> i\,\!</math> jeden strom ranku <math> i+1\,\!</math>. Operace '''VYVAZ2''' zajistí, že od každého vrcholu kromě kořenů byl odtržen max. 1 syn -- když odtrhnu dalšího, odtrhu i tento vrchol a propaguju operaci nahoru.
Složitost operací:
* '''MERGE''' a '''INSERT''' je <math> O(1)\,\!</math> (stejně jako u binomiálních hald)
* '''MIN''' má <math> O(|\mathcal{H}|)\,\!</math> (nemění označení vrcholů)
* '''DELETEMIN''' <math> O(|\mathcal{H}|+\mathrm{maxrank}(\mathcal{H}))\,\!</math>, kde <math> maxrank\,\!</math> udává maximální rank stromu v haldě (může navíc odznačit některé vrcholy)
* '''DECREASE''' je <math> O(1+c)\,\!</math>, kde <math> c\,\!</math> je počet odznačených vrcholů (navíc označí max. 1 vrchol)
* '''INCREASE''' a '''DELETE''' jsou <math> O(1+c+d)\,\!</math>, kde navíc <math> d\,\!</math> je počet synů zvedaného nebo odstraňovaného vrcholu (také označí navíc max. 1 vrchol).
Pro výpočet amortizované složitosti použijeme potenciálovou metodu a zvolíme hodnotící funkci <math> w\,\!</math> jako počet stromů v haldě + <math> 2\times\,\!</math> počet označených vrcholů. Můžeme říct, že amortizovaná složitost '''MERGE''', '''INSERT''' a '''DECREASE''' je <math> O(1)\,\!</math>.
Označme max. rank stromů v lib. haldě reprezentující <math> n\,\!</math>-prvkovou množinu jako <math> \rho(n)\,\!</math>. Amortizovaná složitost '''MIN''', '''DELETEMIN''', '''INCREASE''' a '''DELETE''' pak je <math> O(\rho(n))\,\!</math> (pro '''MIN''' a '''DELETEMIN''' je vzorec amortizované složitosti podobný jako u binomiálních hald, pro '''INCREASE''' a '''DELETE''' je to vidět přímo ze vzorců).
Pro odhad <math>\rho(n)\,\;</math> je potřeba znát fakt, že <math> i\,\!</math>-tý nejstarší syn libovolného vrcholu má aspoň <math> i-2\,\!</math> synů (plyne z toho, že se slévají jen stromy stejného řádu a odtrhnout lze max. jednoho syna).
Vezmeme tedy nejmenší strom <math>T_j\,\;</math> ranku <math>j\,\;</math>, který toto splňuje. Ten musí být složením <math>T_{j-1}\,\;</math> a <math>T_{j-2}\,\;</math> (vzniká tak, že se slijí dva <math>T_{j-1}\,\;</math> a potom se na tom, který je pověšený jako syn nového kořenu, provede '''DECREASE''' a tím se z něj stane <math>T_{j-2}\,\;</math>). Z minimálního počtu synů se dá odvodit i rekurence <math>|T_k| \geq 1 + 1 + |T_0| + \dots + |T_{k-2}|</math>, která dá indukcí to samé.
Potom <math>|T_{k+1}| = F_k</math>, kde <math>F_k</math> je <math>k</math>-té Fibonacciho číslo. Pro Fibonacciho čísla platí, že <math>\lim_{k\to\infty} F_k = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^k</math>. Proto je <math>\rho(n) = O(\log(n))\,\;</math>, což dává logaritmickou amortizovanou složitost pro '''MIN''', '''DELETEMIN''', '''INCREASE''' a '''DELETE'''. Z toho pochází i název ''Fibonacciho'' haldy.
====Aplikace====
''Fibonacciho haldy'' se díky své rychlosti '''INSERT''', '''DECREASE''' a '''DELETEMIN''' často používají v grafových algoritmech. Praktické porovnání rychlosti s jinými haldami však není dosud přesně prostudováno.
Motivací pro vývoj ''Fibonacciho hald'' byla možnost '''aplikace v Dijkstrově algoritmu'''. Dává totiž složitost celého algoritmu <math> O(m+ n\log n)\,\!</math>, což by mělo být lepší pro velké, ale řídké grafy proti <math> d\,\!</math>-regulárním haldám. O prakticky zjištěném "zlomu" ale nevíme.
== Relaxované vyhledávací stromy ==
{{zkazky|
* '''Dynamizace, relaxované vyhledávací stromy, samoupravující datové struktury (I4 - Majerech+Čepek+neznámý teoretik)''': Dynamizaci jsem věděl, stačilo popsat ty dva způsoby semidynamizace a dynamizaci. Bez důkazů. To se jim celkem líbilo, a protože jsme tím zabili dost času, popsal jsem princip relaxovaných struktur jen stručně. Pak jsme se ještě zasekli u Splay stromů, ptali se, jak se u nich měří složitost, což jsem nějak nebyl schopný zodpovědět, aby s tím byli spokojeni. Zpětně mě napadá jen možnost, že jsem neřekl, že měříme amortizovanou hloubku stromu.
}}
[http://ktiml.mff.cuni.cz/teaching/files/materials/binvyhst.pdf Skripta Koubek str 16. podkapitola 3], [http://www.dmi.unict.it/~faro/algocom/prova01/paper16.pdf Článek "Relaxed Balanced Red-Black Trees"]
Co se stane se stromy, kde po přidání/odebrání nevyvažujeme. Rychlejší operace, více uživatelů zároveň, vyvažování necháme na později. Tyto stromy nazýváme relaxované.
* Možná degenerace stromu - delší vyhledávání
* Lze jednoduše nevyvážený strom vyvážit bez přebudování celé struktury?
Požadavek
* v - vrchol černý a v podstromu vrcholu chybí jeden černý uzel
* b - vrchol i jeho otec červené, exkluzivní, s vrcholem nesmí být svázán žádný jiný požadavek
Příklad na RB stromech, lze analogicky pro ostatní. Máme frontu vyvažovacích požadavků, pokud prázdná, strom je vyvážený.
Nad daty pracuje několik procesů najednou:
* uživatelský - provádí vyhledávání, přidávání a odebírání. Pokud po aktualizaci vznikne požadavek na vyvážení, přidá ho do fronty
* správcovký - bere vhodné požadavky z fronty a provádí je. Požadavky mohou být buď zcela ošetřeny nebo transformovány v jiný požadavek blíže kořeni.
{{Statnice I2}}
