Datov0 struktury Typy rozlišujeme datov0a funkcion/Elní Datov0 typy lze zav0st pomocí funkcion/Elních,řqoadně funkcion/Elní typy lze simulovat pomocí nekonečných datových typů, ale kvůli efektivnosti implementace se rozlišují a uvažují se zvl/Ešť. Hodnoty funkcion/Elních typů \soufunkce a procedury. Jednotliv0 funtôní hodnoty (či vedlejší efekty procedur) nejsou zn/Emy pedem, ale dospěje se k nim po výpočtu. Ten je spuštěn tzv. vol/Enírrc\\\ aplikací na argumenty. Hodnoty datových typů jsou obvykle zn/Emy a uloženy v pareti, ale jejich složky je třeba najít a zpřístupnit (například najít prvek pole podle indexu apod). 78 Datov0 typy mohou býts/ca/^Er/7/nebo složen0 Skal/Erní datov0 typy v dan0m programovacím jazyce obvykleaiirnují číseln0 typy (cel/E nebo desetinn/Ešísla z určit0 kone5n0 množiny), znakov0 typy, typ pravdivostních hodnot apod. Data skal/Erního typu zabírají vždy konstantní a mal0 množství paměti (typicky do 10 B). Zpřístupnění hodnoty skal/Erního typu trv/E konstantní dobu. Složen0 datov0 typy jsou napíklad z/Eznamy#,-tice s pojmenovanými složkami), uniony, posloupnosti, množiny apod. Data složených typů se nazývají datov0 struktury • Datov0 struktury pevn0 velikosti ^-tice, statick/E pole,...) — \zvstatick0 datov0 struktury • Datov0 struktury prorrěnn0 velikosti — \zv.dynamick0 datov0 struktury _) Statick0 datov0 struktury mají konstantní velikost ačasov/E složitost zpístupnění Iibovoln0ho prvku je konstantní. Dynamick0 datov0 struktury mají velikost danou ějakou proměnnou n, jejíž hodnota se může měnit. Casov/E složitost zfĎístupnění Iibovoln0ho prvku dynamick0 datov0 struktury je neklesající funkcí z/Evislou nan; často line/Erní, u efektivních datových struktur lepší, typcky logaritmick/E. Dynamick0 datov0 struktury Seznam Seznam nad b/Ezovým typemB je line/Erní datov/E struktura typS s n/Esledujícími operacemi: nil : S cons : B x S -> S head : S —> B tail : S —> S null : S -> Bool Pro tyto operace a každou hodnotu x typu B a každý seznam s typu S musí platit Axiomy seznamu null(nil) = True null(cons(x,s)) = False head(cons(x,s)) = x tail(cons(x,s)) = s 81 Z/Esobnik Z/Esobnik nad b/Ezovym typerfi je line/Erni datov/E struktura typS s n/Esledujicimi operacemi: empty : S push : B x S -> S top : S —> B pop : S —■> S isempty : S —> Bool Pro tyto operace a každou hodnotu x typu B a každý z/Esobníks typu S musí platit tzv. Axiomy z/Esobníku isempty(empty) = True isempty(push(x,s)) = Falše top(push(x,s)) = x pop(push(x,s)) = s 83 Jak je vidět, z/Esobník a seznam je tat/Ež datov/E struktura. Liší se pouze v použití: O z/EsobníkuDbvyk\e mluvíme, když na něm použív/Eme jen z/Ekladní operace a pracujeme jen s jedním z/Esobníkem nebo pevě daným malým počtem z/Esobníků. Z/Esobníky bývají d/Enyřpdem: během výpočtu se mění jejich obsah, ale nemění se počet z/Esobníků, tj. neruší se a nevznikají nov0 z/Esobníkyrdfto se v imperativních jazycích z/Ekladní operacečasto implementují jako procedury; navíc jejich parametr z/Esobník se vynech/Ev/E, pracuje-li se jen s jedním z/Esobníike U seznamů často definujeme složitější operace (zpřístupnění či změnu n-t0ho prvku rozdělení seznamu na dva, spojení dvou seznamů,...) a během výpočtu seznamy vytv/Eíme a rušíme. Například změnu třetího prvku (alespoň tříprvkov0ho) seznamu s na číslo 5 lze realizovat složenou operací cons (a, cons(b, cons (5,t)))), kde a = head(s) b = head(taiKs)), t = tail(tail(tail(s))). Fronta Fronta nad b/Ezovým typerriB je line/Erní datov/E struktura typQ s n/Esledujícími operacemi: empty : Q head : Q —■> B enqueue : B x Q —> Q dequeue : Q —■> Q isempty : Q —> Bool Pro tyto operace a každ0 hodnoty^, y typu B a každou frontu g typu Q musí platit Axiomy fronty isempty(empty) = True isempty(enqueue(x,g)) = False head(enqueue(x,empty)) = x head(enqueue(x,enqueue(y,g))) = head(enqueue(y,g)) dequeue(enqueue(x,empty)) = empty dequeue(enqueue(x,enqueue(y,g))) enqueue(x,dequeue(enqueue(y,g))) 87 Implementace datových struktur Jestliže typ datov0 struktury není souč/Estí jazyka, je nutn0 vyj/Etidatovou strukturu a operace nad ní pomocí jiných struktur a operací. Takov0 koláčci definic řík/Eme implementace datov0 struktury Například z/Esobník (omezen0 d0lky) lze implementovat pomoc6l(atick0ho) pole, frontu lze implementovat pomocí dvou z/Esobníků, frontu omezen0 d0lky pomocí cyklick0ho pole apod. Pozn/Emka: Jazyky s malou podporou dynamických datových struktur (Pascal, C,...) často poskytují alespoň dynamickou datovou strukturu „nízk0 oerově": paměť M spolu s typem ukazatel (adresa) P, nul/Erní operachil: P pr/Ezdn0ho ukazatele a un/Erní operací zpístupnění (dereferencov/Ení)č/Esti panšti deref :P-—>M. Pak například seznam se běžně implementuje pomocí z/Eznamů vM, jejichž složky jsou ukazatele na další z/Eznamy apod. Příklad: Implementace ohraničen0 fronty pomocí cyklick0ho pole { procedury pracují pouze s jedinou globální frontou const M = 256; { délka pole } MAX = M-l; { kapacita fronty } type R = 0..MAX; Elem = Integer; var Q : record a : array [R] of Elem; h, t : Integer end; \ procedure mkemptyq; begin Q.h := 0; Q.t := 0 end; function isempty : Boolean; begin isempty := Q.h = Q.t end; function isfull : Boolean; begin isfull := Q.h = (Q.t + 1) mod M end; _J 91 function headq : Elem; begin if isemptyq then err("headq prázdné fronty") else headq := Q.a[Q.h] end; procedure enqueue (x:Elem); begin if isfull then err("enqueue do plné fronty") else begin Q.a[Q.t] := x; Q.t := (Q.t + 1) mod M end end; procedure dequeue; begin if isemptyq then err("dequeue prázdné fronty") else Q.h := (Q.h + 1) mod M end; Příklad: Implementace fronty pomocí dvou seznamů data Queue = Q [Int] [Int] emptyq :: Queue emptyq = Q [] [] isemptyq : : Queue —>- Bool isemptyq (Q [] []) = True isemptyq _ = False enqueue : : Int —>- Queue —>- Queue enqueue x (Q h t) = Q h (x:t) headq : : Queue —>- Int headq (Q (x:_) _) = x headq q = head h where Q h _ = revq q dequeue : : Queue —>- Queue dequeue (Q (_:h) t) = Q h t dequeue q Q u [] where Q (_:u) [] = revq q revq (Q [] t) Q (reverse t) [] 95 Cvičení: Funkce headq a dequeue z predešl0 strany zůst/Evají nedefinov/Enyipaplikaci na pr/Ezdnou frontu. Doplite jejich definice tak, aby jejich aplikace na pr/Ezdnou froibu způsobila chybov0 hl/Ešení. Využijte haskellovsk0 funkcerror : : String—>>a. D/E se lehce spóítat, že časov0 složitosti operacíisemptyq a enqueue z předchozího příkladu jsou konstantní, zatímco obě operace headq a dequeue jsou line/Erní vzhledem k velikosti fronty. V nepřízniv0m pípadě je totiž nutn0 volat pomocnou operacirevq, kter/E je sama line/Erní. Přesto i na tyto „dražší" operace lze v kontextu programu, v němž jsou použity, pohlížet v jist0m smyslu jako na operace v průměrn0m (oček/Evan0m) ppadě konstantní. Amortizovan/Easov/E složitost Def: Nechť / je operace na dan0 datov0 struktře D velikosti (nejvýše) n. Uvažujme všechny výpočty Ci,..., Cm podle algoritmů pracujících s datovou strukturou D. Z každ0ho takov0ho výpétu vybereme všechna vol/Ení operace/ (tj. všechny aplikace / na D), čímž dostaneme m posloupností vol/Ení operace/. Průměrnou d0lku výpočtu operace / v i-t0m výpočtu označíme rf. Potom amortizovan/E s/oz/řostoperace / na datov0 struktiře D je funkce Tamort : N —> N definovan/E pro každou velikost datn takto Tamort(n) = max{rfv|l T rootval : T —■> B left : T —► T right : T —■> T isempty : T —> Bool Pozn/Emka: Z/Ekladní operace mají konstantní složitost, slouží k popis datov0 struktury a k její implementaci a k implementaci dalších operací, jako například vyhled/Ení/pid/Ení/odebr/Ení uzlu, vyv/Ežení stromu a podoŠDn Pro z/Ekladní operace, každou hodnotíce typu B a každ0 bin/Erní stromy, r typu T musí platit Axiomy bin/Erního stromu isempty(empty) = True isempty(node(x,Z,r)) = False rootval(node(x ,1,r)) = x left(node(x,l,r)) = I right(node(x ,1,r)) = r J 103 Implementace bin/Ernich stromu v Haskellu data Tree b = Empty I Node b (Tree b) (Tree b) isempty : : Tree b —>• Bool isempty Empty = True isempty (Node _ _ _) = False rootval : : Tree b —>• b rootval (Node x _ _) = x left :: Tree b -> Tree b left (Node _ 1 _) =1 right : : Tree b —>• Tree b right (Node r) = r _J 104 Stromy s neomezeným větvením Def: Je d/Ena b/Ezov/E množina (tyfl. Nechť b E B. Pak pro každ0 riirozen0číslo k > 0 a každou /c-prvkovou posloupnost nepr/Ezdných stromů nad£? je dvojice (6, [Ti,..., Tk\) nepr/Ezónýmstromem s neomezeným větvením nad B. Pozn/Emka: Druhou složkou uspoř/Edan0 dvojice(&, [Ti,..., T^]) je /c-prvkov/E posloupnost stromů, tj. seznam d0lky/c. Je-li k = 0, je seznam pr/Ezdný a dvojice reprezentuje jednouzlový strom (list) s ohodnocením b. Stromy s neomezeným větvením se od stromů pevn0 arity liší tím, žečíslo k není předem pevně dan0, ale může být v jednom stromu pro různ0 uzly různ0. Pozn/Emka: Stromy s neomezeným větvením lze reprezentovat bin/Erními stromy. 105 Stromy s neomezeným větvením a bin/Erní stromy data NTree a = NNode a data BTree a = BEmpty f b : : fb [] fb (NNode v fr : frb) = nb :: NTree a —> BTree a nb t = fb [t] bf bf BEmpty bf (BNode v bn :: BTree a —> NTree a bn t = head (bf t) [ NTree a ] I BNode a (BTree a) (BTree a) [ NTree a ] -> BTree a BEmpty BNode v (fb fr) (fb frb) :: BTree a -> [ NTree a ] = [] ec ys) = NNode v (bf ec) : bf ys 107 Vyhled/Ev/Ení Def: Nechť (K, <) je oeplrě uspoř/Edan/E množina XzMíčů, V je libovoln/E množina tzv. doplňujících oedajů. Nechť/7 = K x V je množina dvojic (k,v),v níž se každý klíč k vyskytuje nejvýše jednou (tj. každý z/Eznam z množiny/7 je určen jednoznačně svým klíčem). Probl0mu nal0zt k dan0mu ktí k z/Eznam(/c, v) G U se V\k/Evyhled/Evacíprobl0m Pozn/Emka: Například z/Eznamy mohou být osobní data a klíi jsou rodn/Eísla, anebo z/Eznamy jsou oedaje o knih/Ech v knihám klíče jsou knihovní signatury apod. 108 Pozn/Emka: V praxi m/E ětšinou smysl pouze případ, kdy množina V je netrivi/Elní, aby bylo co hledat. V uk/Ezkových algoritmech se však dopňující oedaječasto neuvažují, tj. vyhled/Evají se jen klíče. Příslušn0 rozšření těchto algoritmů je totiž přímočar0. Algoritmus bin/Erního vyhled/Ev/Ení type Elem = Integer; Pole = array [1..999] of Elem; function bSearch (k: Elem; var D: Pole; n: Integer): Integer; { Posl. D je rostoucí. Když D[i]=k, tak bSearch(k)=i, jinak bSearch(k) function bs (1, r: Integer) : Integer; var m : Integer; begin if 1 > r then bs := -1 {nenalezeno} else begin m := (1+r) div 2; if k < D[m] then bs else if k > D[m] then bs else {k = D[m]} bs end end {bs}; = bs(l,m-l) = bs(m+l,r) = m begin bSearch := bs (l,n) end Věta: Algoritmus bin/Erního vyhled/Ev/Ení m/E logaritmicloaisovou složitost, tj. jeho složitost je v (9 (log n), kde n je d0lka prohled/Evan0ho pole. Pozn/Emka: Extrasekvenční paměťov/E složitost algoritmu je konstantní, protože rekursivní vol/Ení v ěm jsou prost/E 110 Cvičení: Implementujte algoritmus bin/Erního vyhled/Ev/Ení bez potížekurse. Cvičení: Dokažte tot/Elní korektnost algoritmu bin/Erního vyhled/Eřu7E Hašov/Ení 0 množině K všech možných klíčů obecně předpokl/Ed/Eme jen to, že na ní existuje oepln0 uspoř/Ed/Ení.élkdy však tato množina může mít další speci/Elní vlastnosti jichž lze využít pro efektivní vyhled/Ev/Ení. Náfklad je-li K = {1,..., m} a číslo m je mal0, můžeme data z množiny V uložit do jednorozměrn0ho pole a klce využít jako indexy. Vyhled/Ev/Ení v takov0to datov0 struktioe je efektivní - stejně rychl0 jako indexov/Ení pole. Navíc, pokud se počet n skutečně uložených prvků bude blížit počtu m všech možných klíčů, bude efektivní 1 využití paměti. Pokud je \K\ = m, ale klíče nejsou čísla, lze to obejít pomocí bijektivní funkce h : K —>> {1,..., m} a pole indexovat pomocí fukčních hodnot h(k), kde k G K. Je však důležit0, aby výpočet hodnot funkce h byl rychlý, v ide/Elním pípadě aby měl konstantní časovou složitost. Funkci h nazýv/Emehašovací funkcí a pole indexovan0 jejími hodnotami nazýv/Emefrašoi/ac/' tabulkou. Hašovací tabulky Hašovací tabulka je datov/E struktura, pomocí níž lze praktiky efektivně realizovat „slovníkov0" operace vyhled/Ení, pd/Ení a zrušení položky. „Prakticky efektivně" znamen/E, že operace mají píznivou průměrnou časovou složitost (tedy ne nutně časovou složitost v nejhorším případě). Hašovací tabulka je jednorozměrn0 poleií indexovan0čísly 1,..., n. Převod klíčů na čísla realizuje hašovací funkce h : K —> {1,..., n}. Výpočet hodnot hašovací funkce musí být efektivní, nejl0pe složitosti 0(1). ni Častým případem však je, že počet n skutečně uložených prvků je podstatně menší než počet m všech možných klíčů. I v tomto případě lze postupovat podobně a data ukl/Edat do n-prvkov0ho pole, až na to, že funkce/i : K —>> {1,..., n} nebude injektivní. Bude tedy existovat index i a klíče fci,..., kr, tak, že h{k\) = • • • = h(kr) = i. To nemusí vadit, pokud je splněna n/Esledující podmínka. Oznáme K' podmnožinu klíčů, K' C K, těch dat, kter/E budou skutěně uložena (tedy \K'\ < n). Pak požadujeme, aby z každ0 množiny klíčů, kter0 hašovací funkce zobrazí na stejný index, byl v mncžině K' nejvýše jeden klíč. M/E-li pro pevě danou množinu K' klíčů skutečně uložených dat hašovací funkce tuto vlastnost, nazýv/Eme \dokonalou hašovací funkcí pro klíče z K'. Výhodou tabulek s dokonalými hašovacími funkcemi je optim/Elní složitost výiled/Ení, vložení i zrušení prvku; je stejn/E jako pro pole. Označme K' podmnožinu klíčů, K' C K, těch dat, kter/E budou skutěně uložena. Klíče z množiny K' nazveme použit0 klče. Je-li zoežení/ilx7 ' K' —> {1,..., n} injektivní, řík/Eme, že hašovací funkce je do/co/7a//B/zhledem k množině použitých klíčů K'. Věta: M/E-li výpčet hašovací funkce konstantní složitost a hašov/Ení je dokoal0 pro množinu použitých klíčů K', pak operace vyhled/Ení, vložení, resp. zrušení prvku v hašovací tabulce mají stejnou časovou složitost, jako vyhled/Ení, vložení, resp. zrušení prvku v poli. 112 Nevýhodou dokonalých hašovacích funkcí je, že z/Evisí na mnáině K'. Tato množina musí být zn/Ema pedem, abychom mohli dokonalou hašovací funkci sestrojit. V praxi však ukl/Edan/E datařpdem nezn/Eme a tato data se nšní. Proto v praxi používan0 hašovací funkce většinou nebývají dokonal0 a musí se počítat s takzvanými kolizemi. Kolize je případ, kdy m/E být více dat uloženo na jedn0 pozici hašovací teulky, tj. chceme uložit data s různými klíči fci,..., kr a h(k\) = • • • = h(kr). Kolize Tzv. kolize vznikají při nedokonal0m hašov/Ení: hašovací funkce zobrazuje více požitých klíčů na stejnou pozici pole. Nejjednodušší řešení kolizí je ukl/Edat do každ0 pozice po\®eznam prvků. V něm se pak hled/E sekvečně. Složitost přid/Ení prvku zůst/Ev/E stejn/E jako složitost indexov/Ere,|sd)é složitost vyhled/Ení i složitost zrušení prvku je(9(n). To je sice velmi špatný výsledek, ale v praxi nevadí, protože průměrn/E;asov/E složitost dopadne pro vhodě sestrojenou hašovací funkci mnohem I0pe. Věta: Nechť hašovací funkce zobrazuje použit0 klče na indexy 1,..., n rovnoměrně, tj. pravděpodobnost, že h(k) = i, je stejn/E pro všechny indexyi, 1 < i < n. Pak průměrn/Ešasov/E složitost vyhled/Ení,řj3d/Ení a zrušení prvku pak jeO ( K'\ /n), za předpokladu, že složitosti výpočtu hašovací funkce i indexov/Ení pole jsou konstantní. 113 Pravděpodobnostní rozložení výskytů klíčů v množině K' nemusí být rovnoměrn0, ale dobře navržen/E hašovací funkce transformuje toto rozložení na r n, kde n je velikost hašovací tabulky. Nechť p je prvočíslo, p > m, a nechť a, 6 jsou cel/Ecísla, 0 < a < p, 0 • STree a —>• Bool member _ Empty = False member k (Node v 1 r) = k == v I I k < v && member k 1 I I k > v && member k r Vyhled/Ev/Eni search : : a —>• STree a —>• STree a search _ Empty = Empty search k t@(Node v 1 r) I k == v = t I k < v = search k 1 I otherwise = search k r Vkl/Ed/Ení uzlu insert insert k Empty insert k t@(Node v 1 r) I k < v I k > v I otherwise :: a -> STree a -> STree = Node k Empty Empty = Node v (insert k 1) r = Node v 1 (insert k r) = t Rušení uzlu delete : : a —>• STree a —>• delete _ Empty delete k (Node v 1 r) I k < v I k > v I otherwise STree a Empty = Node v (delete k 1) = Node v 1 (delete k = join 1 r join :: STree a -> STree a -> STree a join 1 Empty = 1 join Empty r = r join 1 r = Node u (delete u 1) r where u = rightmostkey 1 rightmostkey (Node v _ Empty) = v rightmostkey (Node r) = rightmostkey r Cvičení: Vybudujte vyhled/Evací strom z posloupnosti klíů 9,12,10, 7,12,1,8, 5,11,4,0,14,13,3,6, 2. Cvičení: Zrušte v něm uzel s klíčem 5. Cvičení: Definujte v Haskellu funkci lef tmostkey. Cvičení: Dokažte, že bin/Erní strom vzniklý vložením resp. zrušením izlu z vyhled/Evacího stromu pomocí funkcí insert resp. delete bude opět vyhled/Evací. Cvičení: Modifikujte funkce member, search, insert, delete tak, aby pracovaly s realističtějším vyhled/Evacím stromem, v ěmž jsou kromě klíčů uložena i vlastní data: data STree a b = Empty I Node (a,b) (STree a b) (STree a b) member : : a —» STree a b —>> Bool search : : a —)> STree a b —)> Maybe b insert :: (a,b) —> STree a b —> STree a b delete : : a —)> STree a b —)> STree a b Složitost vyhled/Ev/Ení ve vyhled/Evacích stromech Označíme-li T : N —>- N složitost funkce search, pak T(0) = c T (h) = c' + max{T(/i/),T(/i//)} kde /i je hloubka vyhled/Evacího stromu/i' je hloubka jeho Iev0ho podstromu,^" je hloubka jeho prav0ho podstromu ac, c' jsou konstanty. Zřejmě max{T(/ž/), T(hff)} = h — 1 a řešením uveden0 rekursivní soustavy rovnic je line/Erní funkce. Složitost vyhled/Ev/Ení ve vyhled/Evacích stromech Složitosti operací vyhled/Ení, pid/Ení a zrušení položky ve vyhled/Evacím stroěijsou přímo oeněrn0 hloubce stromu. Ta je v nejhorším riípadě line/Erě z/Evisl/E na velikosti stromu (počtu jeho uzlů). Složitost vyhled/Ev/Ení, vkl/Ed/Ení a rušení v obecn0m vyľtaiŕfr stromě je tedy line/Erní. 119 AVL stromy Nazvan0 podle G. M. Adeľsona-Veľsk0ho a E. M. Landise. Def: Vyhled/Evací bin/Erní strom \áVL, když hloubka Iev0ho a prav0ho podstromu Iibovoln0ho uzlu se liší nejvýše o jednu. Věta: Hloubka AVL stromu v z/Evislosti na potu jeho uzlů je vždy v (9 (log). AVL stromy tedy mají logaritmickou hloubku — použijeme-li je jako vyhled/Evací stromy, pak m/E operace vyhled/Ení položky logaritmickou složitost. 120 Def: Fibonacciho strom ř/Edufc definujeme takto: FTq = empty FTi = node(empty, empty) pro k e N je FTk+2 = node(FTfc, FTk+1) Lemma: Pro k > 1 je Fibonacciho strom FTk minim/Elní(vzh\eóerr\ k počtu uzlů) AVL strom hloubky k — 1. Důkaz: Indukcí přes k se snadno uk/Eže, že hloubka nepr/Ezdn0ho stromET^ je A: — 1. Odtud a z definice Fibonacciho stromů vyplýv/E, že Fibonacdiio stromy jsou AVL. Minimalita je důsledkem předchozích dvou bodů: odebr/Ením ějak0ho uzlu z jin0 než nejpravější větve by někde vznikly sousední podstromy s hloubkami lišícími se aspoň o dvě; odebr/Ením uzlu z nejpraější větve by se snížila hloubka cel0ho stromu. Věta: Hloubka AVL stromu v z/Evislosti na potu jeho uzlů je vždy v (9(log). Důkaz: Označme N(k) velikost stromu FT^. Tedy N : N —>- N a N(0) = 0 N(l) = 1 pro A: G N je N (k + 2) = 1 + N (k) + iV(fe + 1) Protože funkce TV majorizuje Fibonacciho funkci, je N G Í2((p ), kde (p = -a za k 2 bereme ř/Ed stromu. Ale víme, žeř/Ed stromu a hloubka je (skoro) tot0ž, takže dost/Ev/Eme, že počet uzlů Fibonacciho stromu hloubky h roste aspoň tak rychle jako (fh. Protože Fibonacciho strom je minim/Elní AVL strom, m/Eme, žeqžet uzlů každOhoAVL stromu hloubky h roste aspoň tak rychle jako tph. Obr/Eceě, každý AVL strom velikosti n m/E hloubku 0(log^ n). Víme, že hloubka každ0ho bin/Erního stromu velikosti je /2(log2 n). Dohromady m/Eme hloubku vO(log^ n) fl i7(log2 rc) = <9(log). Operace na AVL stromech Datov/E struktura: data AVL a = Empty | Node Int a (AVL a) (AVL a) Každý uzel nese informaci o hloubce (jakožto parametr konstruktorov0 funkceNode). Vyhled/Ev/Ení v AVL stromu se neliší od vyhled/Ev/Eníežrlx0m vyhled/Evacím stromu. Po přid/Ení nebo odebr/Ení položky ovšem může nastat situace, ž^yhled/Evací strom přestane splňovat podmínku AVL. Pak je nutn0 pozměnit strukturu stromu. _) Přid/Ev/Ení položky (nov0ho uzlu) do AVL stromu Stejn0 jako u běžn0ho vyhled/Evacího stromu, ale s kontrolou vyv/Eženosti. Přid/Evaný uzel oznáíme x. Pokud se poruší vyv/Eženost stromu, nalezne se nejmenší podírom F, který je nevyv/Ežený. Oznáíme-li h jeho hloubku před přid/Ením uzlur, bude po přid/Ení jeho hloubka h + 1. Kořen stromu F označíme /. Bez oejmy na obecnosti lze pedpokl/Edat, že uzetc je přid/Ev/En dfev0/7opodstromu stromu F. Nechť B je levý podstrom stromu F, G je pravý podstrom stromu F. Strom B je nepr/Ezdný (jinak by pid/Ev/Ení uzlfir nemohlo porušit vyv/Eženost stromuF). Označíme A resp. D jeho levý resp. pravý podstrom, b bude kořen stromu B. _J Rozlišíme dva případy: 1. Uzel x je přid/En do stromuA. Pak strom A m/E hloubku/i — 1, stromy D, G mají hloubku h — 2. Vytvoříme strom T = Node h b A (Node (h-1) f DG). Pak T je AVL strom hloubky h se stejnými uzly jako v F. 2. Uzel x je přid/En do stromuD. Pak stromy A, G mají hloubku h — 2, strom D m/E hloubku h — 1. Označíme d resp. (7 resp. E1 kořen resp. levý podstrom resp. pravý podstrom stromu D. Vytvoříme strom T = Node h d (Node (h-1) b A C) (Node (h-1) f EG) 123 Dva dílčí podpřípady jsou: (a) Uzel x byl přid/En do stromuC. Pak C m/E hloubkiii — 2, E m/E hloubku/i — 3 (b) Uzel x byl přid/En do stromuE. Pak C m/E hloubku^ - 3, E m/E hloubku/i - 2 V obou případech však strom T m/E hloubku/i, je AVL a m/E stejn0 uzly jako strom F. V původním AVL stromu nahradíme podstrom F stromem T. Jelikož T m/E stejnou hloubku jako měl původní podstrom bez uzlu x, zůstane celý strom vyv/Ežený (AVL). Přepočít/Eme hloubky na cesi od kořene stromu T k uzlu x. Byl-li uzel x přid/Ev/En dpraK0/7opodstromu stromu F, je postup analogický (stranově převr/Ecený). 126 Složitost operace přid/Ení položky do AVL Hloubka AVL stromu je logaritmick/E vzhledem k potu jeho uzlů. Přid/Ení uzlíte: 0(log n). Nalezení nejmenšího nevyv/Ežen0ho podstromu: Protože hloubky podstromů jsou spočteny a uloženy v datov0 struktiře, stačí po cestě k uzlu x testovat, zda rozdíl spočtených hloubek Iev0ho a prav0ho podstromu každ0ho uzlu je v množině { — 1,0,1}. Nejnižší uzel, který tuto podmínku nesplňuje, je kořen podstromu F. Jeho nalezení trv/E0(log n). Hloubky podstromů se přepočít/Evají jen po cesš od kořene k x, tedy složitost t0to oepravy je0(log n). Celkov/E složitost pid/Ení uzlu je tedy0(log n). 127 Rušení položky (uzlu) z AVL stromu Rušení vnitřního uzlu převedeme na rušení listu (podobně jako u vyhled/Evacího stromu). Odebíraný list označíme x. Pokud se poruší vyv/Eženost stromu, nalezne se nejmenší podírom B, který je nevyv/Ežený. Oznáíme h jeho hloubku (před i po zrušení uzlu x je stejn/E). Bez oejmy na obecnosti lze pedpokl/Edat, že uzetc byl odebr/En z/ev0/7opodstromu stromu B. Nechť A je levý podstrom stromu B, F je pravý podstrom stromu B. Strom F je nepr/Ezdný (jinak by rušení uzlur nemohlo porušit vyv/Eženost stromufí). Označíme D resp. G jeho levý resp. pravý podstrom, / bude kořen stromu F. J 128 Rozlišíme dva případy: 1. Hloubka stromu G je větší nebo rovna hloubce stromu D. Vytvoříme strom T = Node tí f (Node (tí-1) b AD) G. Pak T je AVL strom hloubky h! se stejnými uzly jako v B, h' = h nebo hl — h — 1 2. Hloubka stromu G je menší než hloubka stromu D. Označíme d resp. C resp. E kořen resp. levý podstrom resp. pravý podstrom stromu D. Vytvoříme strom T = Node h' d (Node {h'—ľ) b A C) (Node {h'-ľ) f E G) Pak strom T m/E hloubku/ť = h — 1, je AVL a m/E stejn0 uzly jako rél strom B. V původním AVL stromu nahradíme podstrom B stromem T. Přepočít/Eme hloubky na cesi od kořene stromu T k uzlu x. V případě rušení uzlu se může st/Et, že hloubka podstromiíT bude menší než hloubka původního podstromu, který byl na jeho místě. Proto je nutn0 proces vyvažov/Ení opakovat: nalezne se nejmeší nadstrom T2 stromu T — Ti, který není vyv/Ežený, vyv/Ežíme ho, nalezneme další nevyv>§ny nadstrom T3... atd., až je vyv/Ežený celý stromy. Hloubky však stačí přepočít/Evat vždy od kčene stromu T ke kořenu nejbližšího vyvažovan0ho nadstromu. 130 Složitost operace rušení položky z AVL Zrušení listu: 0(log n). Nechť hloubka nejmenšího nevyv/Ežen0ho podstromúTi je h\. Nalezení tohoto podstromu trv/E 0(hi), jeho vyv/Ežení (rotace uzlů) trv/E konstantní dobu,řppočít/Ení hloubek trv/E 6(h\). Nechť pro 1 < i < k je h{ d0lka cesty z kďene podstromu T^_i do kořene stromu Ti Pak každ0 nalezení dalšího nevyv/Ežen0ho podstromy trv/E 0(hi), jeho vyv/Ežení trv/E 0(1), přepočít/Ení hloubek \rv/89(hi). To znamen/E, že celkov/E složitost rušení uzlu \& j ^ J = 0(log n). 131 Cvičení: Na vstupu jsou čísla 8, 3, 5, 0, 2,4,1, 6, 9, 7 a při jejich načít/Ení se postupe vytv/Eí AVL strom s uzly ohodnocenými těmito čísly. Nakreslete tento AVL strom v každ0m kroku vytv/Eení (tj. po přid/Ení každ0ho uzlu). Cvičení: Do AVL stromu, který je zpoč/Etku pr/Ezdný, se postupaipřid/Evají položky 4,1, 2, 7, 5, 6, pak se odebere položka 7, přid/E položka3, odeberou se postupně 5,6,1. Určete stav AVL stromu v každ0m kroku. Cvičení: AVL strom m/E uzly ohodnocen0ísly 1 až 20 a m/E strukturu Fibonacciho stromu Šest0hoř/Edu. Popište a nakreslete proces rušení listu obsahujícíb klíč 2. Cvičení: Fibonacciho strom Čtvrt0hoř/Edu na sedmi uzlech je ohodnocen jako AVL strom čísly 1, 3, 5, 7, 9,11,13. Do tohoto stromu přid/Eme jako další položku n/Ehodhzvolen0 sud0číslo k, 0 < k < 14. Jak/E je pravěpodobnost, že budeme muset rotovat uzly, abychom zachovali AVL vyv/Eženost? Černobíl0 stromy Černobíl0 stromy jsou bin/Erní vyhled/Evací stromy, jejiclwly nesou kromě klíče další atribut — barvu — černou nebo bílou. v _ _ Def: Černobílý strom je bin/Erní vyhled/Evací strom, jehož každý uzel je obarven černou nebo bílou barvou. Musí splňovat tyto podmínky: 1. Kořen stromu je černý. 2. Je-li vnitřní uzel bílý, jeho n/Esledníci (pokud existují) jsoučerní. 3. Všechny větve obsahují stejný počet černých uzlů. Pozn/Emka: Vedle n/Ezv\jčernobíl0 stromyse lze setkat i s doslovnými překlady anglick0ho n/Ezvwed-black tree (drzewo czerwono-czarne, rot-schwarzer Baum, rugnigra arbo, vörös-fekete fa,...). Def: Čern/E hloubkebemob\\0ho stromut je počet černých uzlů na Iibovoln0 větvi. Značíme ji bh(t). Lemma: Hloubka černobíl0ho stromut na n uzlech je nejvýše 2 log2(n + 1). Důkaz: Indukcí podle hloubky stromu se uk/Eže, že každýčernobílý strom ť m/E aspá 2bh(ť) - 1 uzlů. Odtud vyplýv/E bUjí') < log2(n + 1). Ale podle definice černobílOho stromu jeho hloubka nepřevyšuje dvojn/Esobek jehočernO hloubky. Odtud plyne tvrzení. Důsledek: Vyhled/Ev/Ení (operacmember a search) v černobílOm strorrě mají složitost 0(log n). 133 Cernobil0 stromy v Haskellu data Barva = Ce I Bi data CBS a = E I N Barva a (CBS a) (CBS a) Vyhled/Ev/Eni ®ernobil0m stromu je stejn0 jako v nevyv/Ezen0m vyhled/Evacst Zjisfov/Eni pislusnosti member : : a —>- CBS a —>- Bool member E = False member k (N _ v 1 r) = k == v II k < v && member k 1 II k > v && member k r Vyhled/Ev/Eni search :: a CBS a CBS a search E = E search k t@(N _ v 1 r) I k == v = t I k < v = search k 1 I otherwise = search k r Přid/Ev/Ení uzlu dóernobíl0ho stromu Přid/Evaný uzel bude bílý. Tím se neznění čern/E hloubka podstromů, ale mohou se dostat pod sebe dva bíl0 uzly. Se dvěma bílými uzly nad sebou a s černým uzlem nad nimi provedeme takovou rotaci, abychom snížili hloubku stromu, ale přebarvíme je tak, aby čern/E hloubka stromu zůstala zachov/Ena: kčen bude bílý a jeho dva n/Eslednícčerní. Tím se opět mohly dostat pod sebe dva bíl0 uzly. Proto celý postup opakijeme tak dlouho, dokud jsou někde pod sebou dva bíl0 uzly. Zůstane-li bílý kořen, přebarvíme ho na černo. Tím se čern/E hloubka cel0ho stromu zvýší o jedničku. _) Přid/Ev/Ení uzlu insert : : a ->> CBS a ->> CBS a insert k s = N Ce y tl tr where N _ y tl tr = ins s ins E = N Bi k E E ins t@(N b y 1 r) I k < y = bal (N b y (ins 1) I k > y = bal (N b y 1 (ins i I otherwise = t bal • • CBS a ĺ ->> CBS a bal (N Ce z (N Bi y (N Bi x a b) c) d) = rt bal (N Ce z (N Bi x a (N Bi y b c)) d) = rt bal (N Ce x a (N Bi z (N Bi y b c) d)) = rt bal (N Ce x a (N Bi y b (N Bi z c d))) = rt bal t = t where rt = N Bi y (N Ce x a b) (N Ce z c d) 138 Složitost operace přid/Ení uzlu Věta: Operace insert přid/Ení položky dočernobílOho stromu velikostin m/E časovou složitost (9 (log n). Důkaz: Vyplýv/E z logaritmicko hloubk>pernobíl0ho stromu a z toho, že operace vyv/Eženíbal m/E konstantní složitost. Cvičení: Proč se při přid/Ev/Ení položky dóernobíl0ho stromu obarvuje kďen cel0ho stromu na černo? Cvičení: Na vstupu je posloupnost 6, 5,4, 2, 3,1, 0, z jejíchž prvků se postupně vytv/Eí černobílý strom. Jak0 jsou tyto stromy v každ0m kroku? Cvičení: Nechť černožlutobílý strom je bin/Erní strom spňující podmínky: • každý uzel je obarven jednou barvou — černou, žlutou, anebo bílou • počet černých uzlů na každ0 větvi je stejný • bezprostřední předchůdce žlut0ho uzlu nesmí být žlutý • bezprostřední předchůdce bíl0ho uzlu nesmí být bílý ani žlutý • kořen stromu je vždy černý Jak/E je minim/Elní a jak/E maxim/Elní hloulóleanožlutobíl0ho stromu nan uzlech? Dokažte. Rušení uzlu z černobíl0ho stromu Rušení vnitřního uzlu převedeme zn/Emým způsobem na rušení listu. Je-li rušený liš bílý, je zrušení trivi/Elní — strom i bez listu zůstanečernobílý. Je-li rušený list černý, je nutno ho nejdříve „odbarvit". Odbarvíme-li černý list, stane se tento list bílým a můžeme ho snadno zrušit. Operace odbarvení spočív/E v pesunutí přebytečn0čern0 barvy blíže ke kďenu tak, aby čern0 d0lky všech štvi zůstaly stejnO. Fřitom může dojít k „přibarvení" černOho uzlu -přesuneme-li černou barvu na uzel, který byl s/Emčerný, stane se tento uzel „dvojn/Esobě černý" a je nutno ho d/Ele odbarvovat (pesouvat čerň st/Ele blíže ke kořenu), aby byl každý uzel „nejvýše jednou černý". Stane-li se dvojn/Esobě černý kořen celOho stromu, přebytečnou černou barvu z něho smažeme a nech/Eme ho „jednoučerný". Tím se sníží čern/E hloubka celOho stromu. 140 1. Bratr odbarvovan0ho uzlu je bílý — pevede se na případ 2 Bratr odbarvovan0ho uzlu ječerný 2a bližší synovec je bílý 2. Bratr odbarvovan0ho uzlu ječerný 2b vzd/Eleější synovec je bílý 2. Bratr odbarvovan0ho uzlu ječerný 2c ž/Edný synovec není bílý Rušení uzlu delete :: a -> CBS a -> CBS a delete k t = cbs (del t) where del E del (N b v 1 r) I k < v I k > v I otherwise lbal b v (del 1) rbal b v 1 (del join b 1 r join :: Barva -> CBS a -> CBS a -> CCBS a -- definice jako u binárního vyhledávacího stromu lbal : : Barva -> CCBS a -> CBS a -> CCBS a lbal Ce d (CeCe tb) (N Bi h tf tj) = -- m N Ce h (lbal Bi d (CeCe tb) tf) tj lbal co d (CeCe tb) (N Ce h (N Bi f te tg) ti) = -- (2a) N co f (N Ce d tb te) (N Ce h tg ti) lbal co d (CeCe tb) (N Ce f te (N Bi h tg ti)) = -- (2b) N co f (N Ce d tb te) (N Ce h tg ti) lbal co d (CeCe tb) (N Ce h tf tj) = -- (2c) cern (N co d tb (N Bi h tf tj)) lbal co d tb tf = o) N co d tb tf rbal :: Barva -> CBS a -> CCBS a -> CCBS a -- analogicky jako lbal _J data CCBS a = CeCe (CBS a) I Cbs (CBS a) cern :: CBS a -> CCBS a cern E = Cbs E cern (N Bi v 1 r) = Cbs (N Ce v 1 r) cern (N Ce v 1 r) = CeCe (N Ce v 1 r) cbs : : CCBS a ->> CBS a cbs (CeCe t) = t cbs (Cbs t) = t Složitost rušení uzlu z černobíl0ho stromu Element/Erní pesun čern0 barvy trv/E konstantní dobu, ale v nejhorším ppadě je nutn0 odbarvovat až ke kořenu, tj. (9 (log n). Nalezení rušen0ho uzlu a n/Ehrada rušení vrřtíího uzlu za rušení listu trv/E tak0 logaritmickou dobu, takže cel/E operace rušení zaberečas (9 (log n). J 148 Cvičení: Implementujte v Haskellu vyvažovači operaci rbal. Cvičení: Napište definici funkce join. Další typy vyhled/Evacích stromů s logaritmickou složitoší operací B-stromy Stromy s proměnným počtem n/Esledníků, ale omezeným zdolačíslem k a shora číslem 2k pro pevně zvolenou konstantu k, tzv. ř^EaB-stromu (viz PV062). Složitost operací přid/Ení/zrušení položky je0(log&n). 2-3-4-stromy Speci/Elní pípad B-stromů. Každý vnitřní uzel m/E buď dva, rii, anebo čtyři n/Esledníky. Mají opt logaritmickou hloubku. 149