Státnice - Stromové vyhledávací struktury I2

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

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. Relaxované vyhledávací stromy

Zážitky ze zkoušek  
  • 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×🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Vyvazovani binarnich vyhledavacich stromu(2015, Kučera) - I3 - definice stromu a vyváženého stromu, AVL a CC, (hrubé) odhady logaritmické výšky. Popis rotace. Implementaci vyvažování jsem nepitvala vůbec, Kučera pak dloubal do operací, kde chtěl krom FIND, INSERT a DELETE nevynechat intervalové dotazy.
  • 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.


(pravá/levá) rotace - pomocné operace pro vyvažování, proveditelné v konst.čase

BVS - uzel má dva syny

  •     levy podstrom obsahuje mensi nez klic
  •     pravy podstrom vetsi

AVL-stromy[editovat | editovat zdroj]

Pravidla: - ∀uzel platí: výška  jeho levého a pravého podstromu se liší nejvýše o 1, uchováváme si v uzlu o tom info {-1,0,1}

Logaritmická výška[editovat | editovat zdroj]

Věta (logaritmická výška AVL)AVL strom o n vrcholech má výšku nejvýše 2·log(n)

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ʰ/²

Dostanem N(h)>2ʰ/² a z toho vyjádříme h: h < 2·log N(h).

Insert (max 2 rot.)[editovat | editovat zdroj]

  • postupujeme od nově přidaného uzlu směrem nahoru a cestou opravujeme balance uzlů podle hloubky podstromů
    • pokud se balance uzlu změnila na 2 nebo –2 (silně nevyvážený vrchol) - > je nutná reorganizace stromu … operace rotace (LR a RL rotace jde brat jako jednu)
    • zrotovaný podstrom má stejnou výšku jako původní, takže není potřeba postupovat dále nahoru ke kořeni stromu (tzn. rotace 1x a dost)

Delete (může mít rotace až do kořene)[editovat | editovat zdroj]

  • vyhledat uzel s rušenou hodnotou a odebrat ho jako v BVS:
    • má- li 0 nebo 1 syna - > vypustit přímo tento uzel U
    • má- li 2 syny, nahradit jeho hodnotu maximem z levého podstromu (nebo minimem z pravého podstromu) a vypustit ze stromu tento náhradní uzel U
    • případného syna uzlu U přepojit na otce uzlu U místo U samotného
  • postupujeme od otce zrušeného uzlu směrem nahoru ke kořeni stromu, v každém uzlu přepočítáváme balanci
    • pokud vznikne silně nevyvážený vrchol (hodnota 2 nebo –2), provedeme v tomto uzlu rotaci – z balance uzlu a jeho synů vyplývá potřebný druh rotace (LL, LR, RR, RL), při rotaci se opraví údaje o výšce a balanci dotčených uzlů
    • cestou se může provádět rotace až log n krát

časová složitost Find,Insert,Delete je nejvýše rovna výšce stromu, tzn. O(log N)

Červeno-černé stromy[editovat | editovat zdroj]

3 pravidla:'

  1. Listy je černé.
  2. Červený vrchol musí mít oba syny černé.
  3. 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 ($ \mathbf{bh}(x)\,\! $) jako počet černých uzlů na nejdelší cestě od uzlu k listu.

Logaritmická výška[editovat | editovat zdroj]

Věta (logaritmická výška ČČ)ČČ strom o n vrcholech má výšku O(log n)

Dk (přímo): k-poč.černých vrcholů v cestě k listu, n-počet vrcholů

minimální strom má všechny vrcholy černé (v cestě počtu k) ⇒ hloubka k-1 a počet vrcholu je 1+2+...+2k-1 = 2k-1;

maximální: střídavě černé a červ. ⇒ hloubky 2k-1 a pocet vrcholu je 1+2+...+22k-1 = 22k-1;

2k-1 ≤ n ≤ 22k-1 ⇒ k ≤ log2(n + 1) ≤ 2k

a dále tedy k ≤ hloubka ≤ 2k ⇒ hloubka O(log n)

Insert (max 1 rot.)[editovat | editovat zdroj]

  • nový vrchol N se přebarví načerveno
  • otec černý ⇒ skončit -- vlastnosti stromů jsou splněné.
  • otec č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ý):
    • 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ě)
      Rb insert1.png
    • strýc černý a přidaný uzel N je levým synem pravá rotace na dědovi a přebarvit uzly tak, aby odpovídaly vlastnostem stromů
      RB case 2.png
    • strýc černý a přidaný uzel N je pravým synem ⇒ levá rotaci na otci a převést tak na předchozí případ

Delete (max 2 rot.)[editovat | editovat zdroj]

detailně  
 
  • Skutečně odstraněný uzel (z přepojování -- viz 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 -- $ x\,\! $ -- je černý) musím udělat násl. úpravy (předp., že $ x\,\! $ je levým synem svého nového otce, v opačném případě postupuji symetricky):
    • $ x\,\! $ prohlásím za "dvojitě černý" ("porucha") a této vlastnosti se pokouším zbavit.
    • Pokud je (nový) bratr $ x\,\! $ (buď $ w\,\! $) červený, pak má 2 černé syny -- provedu levou rotaci na rodiči $ x\,\! $, prohodím barvy rodiče $ x\,\! $ a uzlu $ w\,\! $ a převedu tak situaci na jeden z násl. případů:
      • Je-li $ w\,\! $ černý a má-li 2 černé syny, prohlásím $ x\,\! $ za černý a přebarvím $ w\,\! $ 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 $ w\,\! $ černý, jeho levý syn červený a pravý černý, vyměním barvy $ w\,\! $ s jeho levým synem a na $ w\,\! $ použiji pravou rotaci, čímž dostanu poslední případ:
      • Je-li $ w\,\! $ černý a jeho pravý syn červený, přebarvím pravého syna načerno, odstraním dvojitě černou z $ x\,\! $, provedu levou rotaci na $ w\,\! $ a pokud měl původně $ w\,\! $ (a $ x\,\! $) červeného otce, přebarvím $ w\,\! $ načerveno a tohoto (teď už levého syna $ w\,\! $) přebarvím načerno.

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).

  • Find,Insert,Delete vždy v O(log n)
  • máme více případů ale zase jen max 2 rotace (Delete)

B-Stromy a jejich varianty (6×🎓)[editovat | editovat zdroj]

praktické použití B-stromů:
  • NTFS adresáře (B+)
  • Oracle 11g (B+)
  • MS SQL Server 2012 (B+)
  • PostgreSQL 9.2 (B+)
  • MySQL 5.5 (B+)

Více I2 praktický pohled z OZD - důležitá otázka pro databázisty
okruhy 14/15: B-stromy a jejich varianty

Zážitky ze zkoušek  
  • Indexace relacnich dat (2014, Hoksza) - B-stromy a hasovani - -B B+ B* (proc se pouzivaji - velikost vnitrniho uzlu), hashování 7 druhu, viz Hoksza slajdy
  • DS - B-stromy a jejich varianty (2014, Kopecký) - Popsal jsem definice, co splňují, operace, vyváženosti a jaké jsou varianty ((ne)redundantní, B+, B*). Pak chtěl pan Kopecký vědět, k čemu jsou dobré (zmínil jsem indexování) a dlouho se ptal na různé detaily (např. jak zabránit zamykání celého B-stromu při insertu pokud se ke stromu přistupuje paralelně - lze provádět dopředný split již naplněného uzlu, jaká varianta stromu je nejlepší pro indexování, které atributy v DB jsou vhodné pro indexování - záleží např. na doméně, atd.)
  • DS - B-stromy a jejich varianty (2012) - tady jsem neznal úplně všechny varianty (stacily B/B+/B* jine TEORIE.PDF je neobsahuje), ale nebylo to nijak zásadní, vše hlavní a podstatné jsem věděl, takže OK.
  • B-stromy (2012, Dvořák) Napsal sem definici, dukaz logaritmicke vysky ( hrde sem to nazval Veta o logaritmicke vysce Bstromy coz dvorak s usmevem okomentoval ze je to spis takove trivialni pozorovanicko :D ) Pak sem popsal insert a delete. Pak se ptal nato jestli se da insert udelat v jednom pruchodu ( tzn ne ze prvek zatridim a pak vstoupam vzhuru a provadim stepeni preplnenych uzlu...spravna odpoved je delat dopredne stepeni ( kdyz jdu dolu tak plne uzly preventivne rozstepim abych tam mel misto cimz amortizovane zlepsuju slozitost ) Potom A-sort, Redundantni B-stromy, B*-stromy ( tohle vsechno jen v rychlosti...proste chtel vedet ze vim jaka je tam myslenka )
  • DS - B-stromy + jejich varianty (2010, nějaký teoretik) - Def., operace, složitosti bez žádných větších důkazů.
  • DS - B-stromy a ich varianty (2009, Kopecky) - Napisal som si zakladne definicie B, B+, B* a VB stromov. Pobavili sme sa o redundantych/neredundantych stromoch. Potom o dotazoch na viacero atributov z coho sme sa dostali k hasovaniu a dotazom na ciastocnu zhodu a koncilo to iba otazkou na priestorove data. Tam stacilo povedat, ze je na to dobry R-strom. (Tiez niekde v debate padla otazka na paralelny pristup do B-stromu.) Prijemne aj ked pomerne podrobne sa snazil preverit znalosti.
  • I1/I4 DS - B-stromy (2011, Koubek/Majerech) - Zhruba 2 A4, popis (a,b)-stromu, B-strom jako spec. pripad. Odvozeni log. vysky, neformalne zakl. algoritmy, jejich slozitost, varianty B+, B*, preventivni stepeni a slevani, vyuziti: v databazich, index-sekvencni soubory, A-sort. Ptali se me na to definici (dulezity, ze u korene neplati ta podminka na pocet synu) a pak to zacalo: nejdriv rozdil mezi redudantni a neredudantni verzi a jak se tam lisi delete. :( Nejak jsem nedokazal odvodit, kde je to horsi, pak zacal diskutovat Koubek s Majerechem, ze se to takhle neda poradne rict, ze ta slozitost muze byt v nejhorsim pripade stejna (log n, coz jsem rikal), chvilku se "hadali", pak po me chteli amortizovanou slozitost posloupnosti insertu a deletu - odpoved je, ze to vyjde amortizovane O(1) na operaci, ale dokazat jsem to neumel (pry nejak pres potencial, obdobne jako u Fibonaciho haldy). No a jeste se mne docela pacili, proc jsou ty B-stromy pro databaze lepsi, nez streba BVS - no protoze ja to b muzu zvolit tak, ze pak list ~ stranka na disku. Ale pak me nechali uz zit. Asi jsem uplne neoslnil, ale aby me vyhodili, na to to zas nebylo.


Tato část je neúplná a potřebuje rozšířit. najít další zkazky a doplnit podle nich
  • umožňují při daném klíči najít záznam pomocí několika málo operací, na rozdíl od hashování ale i klíče z nějakého intervalu
  • nejčastější pro indexy na externí paměti, pomocí "klastrování" odfiltrujeme nerelevantní záznamy

B-strom (redundantni, neredundantni)[editovat | editovat zdroj]

setříděný vyvážený m-nární strom s definovanými omezeními větvení (díky nim je rozumně široký)

💡 inserty a delety způsobují pouze lokální změny

pravidla pro neredundatní verzi:

  1. kořen≥2 syny (pokud není list)
  2. vnitřní uzel (mimo kořene) má od ⌈m/2⌉ do m synů
  3. ∀uzel má od ⌈m/2⌉-1 do m-1 (poiterů na) datových záznamů
  4. větevstejnou délku
  5. uzly vypadají takhle: p₀,(k₁,p₁,d₁),(k₂,p₂,d₂), ... ,(kₙ,pₙ,dₙ),u (p - pointery, k - klíče - řadí se podle nich, d - data/pointery na data)
  6. podstromy mají hodnoty klíče mezi klíči z otce
INSERT

💡 v neredundatních se teoreticky dostaneme rychleji k záznamům (ve vnitřních uzlech)

redundatní - mají datové záznamy pouze v listech, takže klíče jsou redundantní ve vnitřních uzlech

Implementace

💡 většinou 1 stránka/blok(8kb) = 1 uzel , tedy arita B-Stromu je okolo 500 a výška se drží okolo 3

INSERT
  • najdeme list kam vložit a pokud je plný uděláme split takže každý nový list je z půlky plný
  • split můžeme zvýšit počet podstromů otce ⇒ split kaskáda (💡 možná optimalizace: přetékáme do sousedů = vyvažování stránek ⇒ nenastane kaskáda)
DELETE
DELETE
  • pokud je po delete uzel méně než z pulky plný mergujeme se sousedem
  • merge můžeme snížit počet podstromů otce ⇒ merge kaskáda

Oba algoritmy pracují v O(log N) v nejhorším případě.

B+-stromy (redundantni)[editovat | editovat zdroj]

tedy data (pointry na ně) jsou pouze v listech, a listy jsou propojeny pointery (💡 nelistové vyšší úrovně mouhou být také propojeny - např. MSSQL pro intervalové zámky)

  • menší vnitřní uzly ⇒ nižší výška (pže uzly mohou být větší) a tj.rychlejší hledání
  • INSERT/DELETE jednodušší ⇒ jednodušší implementace (hlavně range queries)

B*-strom (redundantni, neredundantni)[editovat | editovat zdroj]

generalizace vyvažování:

  • kořen≥2 syny (pokud není list)
  • větevstejnou délku
  • ∀uzel má alespoň ⌈(2m-1)/3⌉ synů
INSERT/DELETE
  • Štěpení se odkládá, dokud nejsou sourozenci plní, potom se štěpí buď 2 do 3. Při odebírání se slévají 3 uzly do 2.

💡 detailněji zde: B-Stromy

Trie (3×🎓)[editovat | editovat zdroj]

Trie pro klíče „A“, „to“, „tea“, „ted“, „ten“, „i“, „in“ a „inn“
Zážitky ze zkoušek  
  • 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).


Redundantní n-ární prefixový strom (z angl. retrieval) určený k reprezentaci operace Member v O(l).

  • Jsou datově úsporné - pro uložení jednoho klíče je třeba jen amortizovaně konstantní prostor.

Trie nad Σ je konečný strom, jehož vnitřní vrcholy mají k synů ohodnocených znaky abecedy Σ.

  • Každému vrcholu lze rekurzivně přiřadit slovo nad abecedou Σ takto:
    • Kořenu odpovídá prázdné slovo λ
    • Syn ohodnocený písmenem a odpovídá slovu otce konkatovanému s a
  • ∀vnitřní vrchol je prefixem nějakého slova z reprezentované množiny S
  • ∀list (nebo i vnitřní uzel?) obsahuje bit zda slovo co představuje je v S

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.

Složitosti časové: Member - O(I) , Insert/Delete - O (lk)

Paměťová složitosti: je od O(|S|lk) (žádné společné prefixy) po O(|S|) (v případě že reprezentujeme U)

Komrimované Trie[editovat | editovat zdroj]

vytvoření klasické trie s min.hloubkou je NPC (?)

Vynecháme vrcholy bez větvení, musíme si pak ale udržovat ve vrcholech hodnotu aktuální hloubky a v listech celá výsledná slova:

  • uroven(v) - číslo úrovně vrcholu v odpovídajícím někomprimovane trie
  • slovo(v) - slovo odpovídající vrcholu v

Trie.png

Insert a Delete můžou pak rozšiřovat, krátit strom.

Časová složitost: Member - O(I) , Insert/Delete - O(l+k) ,

Paměťová složitost: O(|S|k)

Ještě komprimovanější trie: Reprezentace řídkou maticí. Paměťová náročnost O(n) a nepodporují Insert/Delete

Aplikace:

  • autocomplete slovníky
  • náhrada za hashování

Haldy (9×🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • 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 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 $ |B_i| = 2^i $). 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)


d-regulární Leftist Binomial Fibonacci
Definice:otec≤syn

(nebo otec≥syn)

d-nární strom

  • ∀uzelnejvýše d synů
  • je "shora a zleva" naplněný (☀ jakobyste ten strom měli v poli a do něj zleva nasypali souvislý blok prvků)

Operace založeny na probubláváníDary heap.png

binarni strom (línější podmínky než d-reg)

  • vrchol má 1 syna je to levý syn
  • jinak npl(levého syna) ≥ npl(pravého)
  • npl(v) - (null path lenght)je delka nejkratsi cesty z vrcholu v do vrcholu s max. 1 synem (∼délka pravé cesty v podstromě - kvůli 1.bodu)

Operace jsou "rekurzivněji" založeny na MERGE a DECREASEKEY.

Binom.png
les binomiálních stromů
  • řád max. 1
  • binomiální strom řádu i se skládá z kořene a synů ze stromů izomorf. řádu 0,...,i-1  - chová se jako malá halda (☀H0 je 1 uzel)

"Horlivé" operace založené na MERGE

les (2směrný spoják) i-nárních hald vzniklých posloupnosti operací pro fib.haldy

  • označení vrcholu že ztratil syna - z nekořenového prvku lze oddelit max 1 syna, jinak se oddeli cely uzel do noveho stromu
  • řád stromu - počet synů kořene (řády se mohou opakovat a podstrom má alespoň Fi+1 vrcholů)
  • pointer na min.kořen

"Líné" operace.

MIN O(1) O(1) O(1) O(1)
DELETEMIN zahodím kořen, nahradím posledním prvkem a když nesedí probublávám dolů

O(d log n)

zahození kořene a zMERGEování jeho synů

O(log n)

zahození kořene, syny vložíme do haldy a zMERGEujeme (☀ jako leftist)

O(log n)

zahodím kořen, syny vložíme do sezn.kořenů, zMERGEujeme stejné řády (☀ jako leftist)

O(log n)[1]

INSERT přidám na konec haldy a když nesedí probublávám nahoru

O(log n)

MERGE 1-prvkové haldy

O(log n)

je vytvoření 1-prvkové haldy a zavolání MERGE (☀ jako leftist)

O(1)[1]

vložení 1-prvkové haldy do seznamu kořenů (☀ jako leftist)

O(1)

DECREASEKEY snížím číslo a když nesedí probublávám nahoru

O(log n)

snížím číslo odříznu od zbytku haldy, a MERGE podstromu a zbytku

O(log n)

snížím číslo a když nesedí probublávám nahoru (☀ jako d-reg)

O(log n)

urveme podstrom se zmenšeným prvkem,dáme do lesa, rekurzivně: pokud někde urveme 2.syna nekořenu urveme i ten prvek

O(1)[1]

MERGE (MAKEHEAP) vytvoříme z prvků náhodný d-reg.strom a postupně probubláváme dolů každý ne-list

O(d² n)

zavolá MERGE(pravý podstrom T1 s menším klíčem v kořeni, T2) výsledek připojí místo onoho pravého syna. Pokud neplatí npl, vymění syny T1

O(log n)

(pro ∀stromy) rekurzivně slep 2 stromy stejného řádu, menší kořen přilepím jako syna toho co má vyšší kořen

O(log n)

(2 stromy st.řádu) menší kořen přilepím jako syna toho co má vyšší kořen (☀ jako binom)

O(1)

haldy - stromová struktura kde platí uspořádání na haldě:

  •    otec≥syn (tzv. max-heap) nebo
  •    otec≤syn (tzv. min-heap)
    •    💡 tj. max/minimálni prvek je vždy kořen stromu

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ěť ( O(n) ) a rychlost ostatních operací. (MIN v O(1))

jsou různě rychlé ale vždy aspoň 1 operace má složitost O(log n)

Krom běžných operací můžu měnit uspořádání: operace INCREASE a DECREASE změní velikost klíče o 1.

d-regulární halda

d-regulární haldy[editovat | editovat zdroj]

Pravidla (minheap):

  • ∀ vrchol má nejvýše d synů
  • vrchol není list ⇒ ∀vrchol s menším číslem má právě d synů (očíslování vrcholů - odzhora dolu, zleva doprava)
  • vrchol má synů < d ⇒ ∀vrcholy s většímy čísly jsou listy
  • d-reg.strom má max 1 vrchol, který není list a má synů < d

Hloubka: zřejmě ⌈logd (n(d-1)+1)⌉

💡 umožňuje i efektivní reprezentaci v poli

MAKEHEAP (také se používá pro MERGE) - vytvoříme z prvků lib. d-reg.strom a postupně posouváme dolů každý ne-list, nejh.čas O(d² n)

INSERT - přidám na konec haldy a když nesedí prohazujeme s rodičem (tedy posouvám nahoru UP) , O(logd n)

DELETE / DELETEMIN - odeberu, nahradím posledním prvkem a pokud nesedí prohazuji s potomky kteří porušují vlastnost víc (tedy posouvám nahoru nebo dolů UP/DOWN) , O(d logdn)

DECREASE - zvětším číslo o a a když nesedí prohazujeme s rodičem (tedy posouvám nahoru UP) , O(logd n)

Aplikace

Heapsort -- vytvoření haldy a postupné volání MIN a DELETEMIN. Lze ukázat, že pro $ d=3,d=4\,\! $ je výhodnější než $ d=2\,\! $, empiricky je do cca $ 1 000 000\,\! $ prvků $ d=6\,\! $ nebo $ d=7\,\! $ nejlepší. Pro delší posloupnosti je možné $ d\,\! $ zmenšit.

Dijkstra -- normální Dijkstrův algoritmus, jen vrcholy grafu uchovávám v haldě, tříděné podle aktuálního $ d\,\! $ (horního odhadu vzdálenosti). Složitost $ O((m+n)\log n)\,\! $, pro $ d=\max\{2,\frac{m}{n}\}\,\! $ je to $ O(m\log_d n)\,\! $ a pro husté grafy ($ m>n^{1+\varepsilon}\,\! $) je lineární v $ m\,\! $.

zdroje

leftist

Leftist haldy[editovat | editovat zdroj]

binarni strom

  • vrchol má 1 syna ⇒ je to levý syn
  • vrchol má 2 syny ⇒ npl(levého syna) ≥ npl(pravého)
    • npl(v) - (null path lenght) je delka pravé (nejkratsi) cesty z vrcholu v do vrcholu s max. 1 synem (délka pravé cesty v podstromě - defakto kvůli 1.bodu)
  • plati usporadni na halde

Pro leftist haldu se definuje pravá cesta (posl. pravých synů) a pokud máme takovou cestu délky $ k\,\! $ z vrcholu $ v\,\! $, víme, že podstrom $ v\,\! $ do hloubky $ k\,\! $ 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(T1,T2) (💡 rekurzivní)

  • Testuje prázdnost obou stromù (a pokud je jeden prázdný, vrátí ten druhý jako výsledek)
  • volá MERGE(podstrom pravého syna stromu T1 s menším klíčem v kořeni, T2)
  • výsledek připojí místo onoho pravého syna
  • Pokud neplatí podmínka na npl, vymění syny T1

INSERT(x) - je vytvoření jednoprvkové haldy a zavolání MERGE

DECREASE(s,a) - se udělá snížením hodnoty ve vrcholu s o a, zavoláním OPRAV, tj. jeho odříznutím od zbytku haldy, a MERGE podstromu a zbytku.

  • OPRAV(T,v) 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.

vše v nejh.případě O(log n)

Ostatni

  • MIN je vypsání kořene, DELETEMIN je zMERGEování synů kořene (a jeho zahození). MAKEHEAP je vytvoření hald z jednotl. prvkù, jejich nacpání do fronty a potom v cyklu: vyberu dva z fronty, zmerguju a hodím výsledek zpátky; dokud mám ve frontě víc než 1 haldu - to je potom výsledek.
  • MAKEHEAP potřebuje jen O(n)
MERGE
MERGE
Binomiální halda - les binomiálních stromů
Binomiální halda - les binomiálních stromů

Binomiální haldy[editovat | editovat zdroj]

les binomiálních stromů

  • každý řád max.jednou,
  • binom.strom řádu i se skládá z kořene a synů ze stromů izomorf. řádu 0,...,i-1  - chová se jako malá halda
    • 💡 používá se ukazatel na strom s min.prvkem O(1) a kořeny jsou spojene ve spojaku

Operace jsou založené na MERGE

MERGE (přes všechny stromy)

  • 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í jen stromy stejného řádu (jinak také CONSOLIDATE), přenáší výsledky do dalšího spojování
  • vytvoří strom: Hi / Hi
  • Složitost - O(log |S1| + log |S2|), protože 1 krok (SPOJ) je konstantní.

INSERT - je vytvoření jednoprvkové haldy a zavolání MERGE (jako leftist)

DECREASE - INCREASE a DECREASE změní hodnotu f u prvku a zavolají probublávaní nahoru nebo dolů

vše vyžaduje čas O(log n) jen INCREASE O(log2n) 

není podporováno DELETE, jen jako DECREASE + DELETEMIN.

umožňuje rychlou implemetaci Insert O(log n) (amotizovaně O(1)) a Merge (dvou hald) O(log n)

Líné binomiální - může obsahovat více stejných binomiálních stromů, vyvažování (konsolidace) se děje jen po/před Min a DeleteMin, konsolidace (poskládání dohromady do podoby definované normálníma bin. haldama) - složitost se rozpočítá

Počty vrcholů stromů F0, F1, … mají souvislost s Fibonacciho čísly (odpovídají jim)

Fibonacciho haldy (3×🎓)[editovat | editovat zdroj]

  • les haldových stromů vzniklých posloupnosti operací pro fib.haldy z prázné haldy, vychází z (líných) binomiálních
    • 💡 výhodou je nízká složitost algoritmů, struktura je více flexibilní, operace co nejsou nutné odkládáme
    • 💡 používá se ukazatel na strom s min.prvkem O(1) a kořeny jsou spojene ve spojaku
  • při odebírání prvků lze oddelit z nekořenového prvku max 1 syna, jinak se oddeli cely uzel do noveho stromu
    • z čehož vyplývá: v je vrchol a má i synů ⇒ pak podstrom v má alespoň Fi+1 vrcholů
  • při DELETEMIN se počet stromů naopak snižuje - spojují se
    • strom má rank(i) pokud má kořen i synů (jako izomorfismus u binom.hald)
  • MERGE - (přes 2 stromy stejných stupňu) přilepím jako syna toho co má vyšší klíč
  • INSERT - je vytvoření jednoprvkové haldy a zavolání MERGE (jako leftist)
  • MIN - projiti korenu a vypsani nejmensiho, můžeme si udržovat odkaz na min (pak je to v O(1))
    • MIN,MERGE, INSERT, DECREASE mají amort.složitost O(1)
  • DELETEMIN - odebrání stromu s nejmenším prvkem, a pridani jeho podstromu do lesa, pak projdeme a hledame stromy se stejným rank a voláme na ně MERGE (jinak také CONSOLIDATE, jako líne binom.haldy)
  • DECREASE, INCREASE a DELETE vycházejí z leftist hald.
    • Když vrchol není kořen a byl mu předtím někdy odříznut syn, je speciálně označený.
    • Používají pomocnou operaci VYVAZ2, která 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. DECREASE pak 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, potom volá na odtržené místo 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.
      • DELETEMIN,INCREASE,DELETE mají amort.sl. O(log n)

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 $ O(m+ n\log n)\,\! $, což by mělo být lepší pro velké, ale řídké grafy proti $ d\,\! $-regulárním haldám. O prakticky zjištěném "zlomu" ale nevíme.


další zdroje  

{{{1}}}

Relaxované vyhledávací stromy[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • 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.


Skripta Koubek str 16. podkapitola 3, Č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.


Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic

  1. 1,0 1,1 1,2 Amortized time.