Datové typy
■ jaká data jsou potřebné pro řešení problému?
■ jak se budou data reprezentovat?
■ jaké operace se budou nad daty provádět?
Datový typ
■ rozsah hodnot, které může nabývat proměnná daného datového typu
■ množina operací, které jsou pro daný datový typ povolené / definované
■ nezávisí na konkrétní implementaci
11. dubna 2016
Základní datové struktury
Datové typy a struktury
jednoduchý (skalární) datový typ
data zabírají vždy konstantní (typicky malé) množství paměti, zpřístupnění
hodnoty skalárního typu trvá konstantní čas
číselné a znakové typy, typ pravdivostních hodnot, výčtový typ
složený datový typ
implementace složeného datového typu se nazývá datová struktura
■ statický - pevná velikost; časová složitost zpřístupnění prvku je konstantní k-tice, pole konstantní délky
■ dynamický - neomezená velikost; časová složitost zpřístupnění prvku je funkcí závislou na velikosti
seznam, zásobník, fronta, slovník, strom, graf
o
11. dubna 2016       2 / 139
Dynamické datové typy
■ množina objektů; v průběhu výpočtu můžeme do množiny prvky přidávat a odebírat resp. množinu jinak modifikovat (tzv. dynamická množina)
■ každý prvek dynamické množiny je reprezentovaný jako objekt, jehož atributy můžeme zkoumat a modifikovat za předpokladu, že máme ukazatel / referenci na tento objekt
■ jeden z atributů objektu je jeho identifikátor - klíč key
■ jestliže všechny prvky mají různé klíče, často mluvíme o množině obsahující klíče
o
11. dubna 2016       3 / 139
Dynamické datové typy - základní operace
Search(S', k) pro množinu S a klíč k vrátí ukazatel x takový, že x.key — k resp. Nil, když objekt s klíčem k není obsažen v množině S
Insert^, x) do množiny S vloží objekt s ukazatelem x
Delete(S', x) z množiny S odstraní objekt s ukazatelem x
Maximum (S) pro množinu S s úplně uspořádanými objekty vrátí ukazatel x na objekt, jehož klíč je maximálni
Minimum(S') pro množinu S s úplně uspořádanými objekty vrátí ukazatel x na objekt, jehož klíč je minimálni
Successor(S', x) pro množinu S s úplně uspořádanými objekty vrátí ukazatel na objekt, jehož klíč následuje bezprostředně za klíčem x.key, resp. hodnotu Nil když x je maximální
Predecessor(S', x) symetricky k Successor
o
11. dubna 2016       4 / 139
Vyhledávací stromy
Datové struktury
□ Vyhledávací stromy
■ Binární vyhledávací stromy
■ Intervalové stromy
Červeno cerne stromy
■ Červeno černé stromy
■ Rank prvku
■ Zřetězené hašování
■ Otevřená adresace
o
11. dubna 2016       5 / 139
Vyhledávací stromy
Motivace
Problém rezervací
online rezervační systém
(např rezervace lékařského vyšetření, přistávací ranveje, ...)
■ množina rezervací R
■ požadavek t na rezervaci
■ rezervace může být potvrzena právě když v intervalu (t — k,t + k) není žádná jiná rezervace (fc je délka trvání události) a současně t je aktuální
■ mazání realizovaných aktualizací
příklad: R = {21, 26, 29, 36}, k = 3, aktuální čas 20
rezervace    24 není validní (možná), protože 26 G R
33 je OK
15 není validní, protože aktuální čas je 20
o
11. dubna 2016       6 / 139
Problém rezervací - řešení
jaký datový typ je vhodný pro reprezentaci R a realizaci požadovaných operací???
uspořádaný seznam
ověření rezervace v čase 0(n), záznam rezervace v čase 0(1)
uspořádané pole
ověření rezervace v čase 0(logn), záznam rezervace v čase 0(n)
neuspořádaný seznam / pole
ověření rezervace v čase 0(n), záznam rezervace v čase 0(1)
minimová halda
ověření rezervace v čase 0(n), záznam rezervace v čase 0(logn), aktuálnost rezervace v čase 0(1)
binární pole rezervace t je uložena v položce s indexem t - problém velikosti pole existuje lepší řešení?? současně efektivní vyhledávání i vkládání!
11. dubna 2016       7 / 139
Vyhledávací stromy
Binární vyhledávací stromy
Vyhledávací stromy
■ umožňují efektivní implementaci operací Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete
■ operace nad vyhledávacím stromem mají složitost úměrnou hloubce
stromu, tj. v nejhorším případě až lineární
■ binární vyhledávací stromy - každý vrchol stromu má nejvýše 2 následníky, tj. strom může mít až hloubku n
■ vyvážené binární vyhledávací stromy mají logaritmickou hloubku, tj. operace mají složitost O(logn)
o
11. dubna 2016       8 / 139
Vyhledávací stromy
Binární vyhledávací stromy
Binární vyhledávací stromy (BVS)
■ datová struktura, která využívá ukazatele
■ každý vrchol (uzel) stromu představuje jeden objekt
■ každý vrchol obsahuje
• klíč
• ukazatele /e/ŕ, right a p na levého syna, pravého syna a na otce; ukazatel má hodnotu Nil právě když vrchol nemá příslušného syna, resp. otce
• případné další data
v binárním vyhledávacím stromu jsou klíče vždy uloženy tak, že platí
BVS vlastnost
jestliže x je vrchol BVS a y je vrchol v levém podstromu vrcholu x, tak platí y.key < x.key y }e vrchol v pravém podstromu vrcholu x, tak platí y.key > x.key
o
11. dubna 2016       9 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - procházení stromu
■ cílem je projít strom tak, aby každý vrchol byl navštíven právě jednou
■ využití: provedení operace nad každým vrcholem, výpis klíčů, kontrola vlastností stromu, ...
■ strom procházíme rekurzivně
■ začínáme v kořeni stromu
■ (rekurzivně) navštívíme všechny vrcholy levého podstromu kořene
■ (rekurzivně) navštívíme všechny vrcholy pravého podstromu kořene
o
11. dubna 2016
Vyhledávací stromy
Binární vyhledávací stromy
BVS - výpis klíčů
klíče uložené v BVS můžeme vypsat v pořadí
inorder hodnotu klíče uloženého v kořeni vypíšeme mezi vypsáním klíčů uložených v jeho levém a pravém podstromě (2 3 5 5 7 8)
preorder hodnotu klíče uloženého v kořeni vypíšeme před vypsáním klíčů uložených v jeho levém a pravém podstromě (5 3 2 5 7 8)
postorder hodnotu klíče uloženého v kořeni vypíšeme po vypsání klíčů uložených v jeho levém a pravém podstromě (2 5 3 8 7 5)
o
11. dubna 2016        11 / 139
Vyhledávací stromy
Binární vyhledávací stromy
Inorder
lnorder_Tree_Walk(x)
1 if x ^ Nil
2 then lNORDER_TREE_WALK(x./e/í)
3 print x.key
4 lNORDER_TREE_WALK(x.rz^/lí)
5 fi
■ Inorder_Tree_Walk(T.rooí) vypíše klíče uložené v BVS T od nejmenšího po největší
■ časová složitost je 0(n), kde n je počet vrcholů stromu T
■ BVS Sort - časová složitost ???
o
11. dubna 2016        12 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - vyhledávání ve stromu
■ začínáme v kořeni stromu, postupujeme rekurzivně
■ porovnáme hledaný klíč k s klíčem uloženým v navštíveném uzlu, jestliže se rovnají, tak vyhledávání končí úspěchem
■ jestliže hledaný klíč k je menší než klíč x.key uložený v navštíveném uzlu x, tak pokračujeme v levém podstromu uzlu x
■ v opačném případě pokračujeme v pravém podstromu uzlu x
■ vyhledávání končí neúspěchem právě když hledaný klíč není uložen ani v navštíveném listu
Tree_Search(x, k)
1 if x — Nil V k = x.key
2 then return x fi
s if k < x.key
4 then return TREE_SEARCH(x./e/í, k)
5 else return TREE_SEARCH(x.rz^/ií, k) fi
o
11. dubna 2016        13 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - minimální a maximální klíč
■ jestliže hledáme minimální klíč, tak v stromu postupujeme vždy doleva
■ jestliže hledáme maximální klíč, tak v stromu postupujeme vždy doprava
Tree_Minimum(x)
1 while x.left ^ Nil doxf- x.left od
2 return x
Tree_Maximum(x)
1 while x.right ^ Nil doxf- x.right od
2 return x
o
11. dubna 2016        14 / 139
Binární vyhledávací stromy
BVS - předchůdce a následník
Vyhledávací stromy
■ předpokládáme, že všechny klíče uložené v stromě jsou vzájemně různé1
■ následníkem uzlu x je uzel, který obsahuje nejmenší klíč větší než x.key
(successor)
■ předchůdcem uzlu x je uzel, který obsahuje největší klíč menší než x.key
(predecessor)
analogicky se operace definují i pro strom, který může obsahovat uzly se stejnými
klíči
bm 11. dubna 2016        15 / 139
Vyhledávací stromy
Binární vyhledávací stromy
následníkem uzlu x je uzel, který obsahuje nejmenší klíč větší než x.key
■ jestliže uzel x má neprázdný pravý podstrom, tak jeho následníkem je nejmenší klíč uložený v jeho pravém podstromu
■ jestliže pravý podstrom je prázdný, tak
• následníkem x je uzel y takový, že x.key je největším klíčem v levém podstromu uzlu y
• uzel y je prvním uzlem na cestě z x do kořene stromu takový, že y.key > x.key (Jinými slovy x patří do levého podstromu uzlu y)
Tree_Successor(x)
1 if x.right ^ Nil
2 then return TREE_MiNiMUM(x.rz^/ií) fi
3 y <(— x.p
4 while y ^ Nil A x — y.right
5 do x <r- y
6 y ^y.p
7 od
8 return y
o
11. dubna 2016
Vyhledávací stromy
Binární vyhledávací stromy
BVS - přidání nového uzlu
■ procházíme strom stejně jako kdyby jsme klíč nového uzlu vyhledávali
■ hledáme vrchol, jehož příslušný podstrom je prázdný (levý podstrom když klíč nového uzlu je menší než klíč vrcholu, pravý podstrom když je větší) a nový uzel se stane jeho příslušným synem
Tree_lnsert(T, z)
1 y <- Nil
2 x T.root
3 while x    Nil do
4 y <- x
5 if z.key < x.key then x ^— x.left
6 else x <(— x.right fi
7 od
8 z.p <(— y
9 if y = Nil then T.root z
10 else if z.key < y.key then y.left <(— z
11 else y.right <(— z fi
12 fi
o
11. dubna 2016        17 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - odstranění uzlu - případ 1
při odstraňování uzlu \z, můžou nastat 3 případy z nemá žádného syna uzel odstraníme
NIL NIL
o
11. dubna 2016        18 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - odstranění uzlu - případ 2
z má jediného syna
syna přesuneme na pozici uzlu z tak, že otec uzlu z se stane otcem jeho syna
NIL
q
q
NIL
o
11. dubna 2016        19 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - odstranění uzlu - případ 3
z má dva syny
■ potřebujeme najít uzel y, který nahradí uzel z
■ vhodným kandidátem na y je následník uzlu z (symetricky by jsme mohli využít předchůdce uzlu z)
■ protože pravý podstrom uzlu zje neprázdný, tak následník y uzlu zje nejmenším uzlem v pravém podstromě uzlu z
■ y nemá levého syna proto ho můžeme ho přesunout na pozici z
o
11. dubna 2016
Vyhledávací stromy
Binární vyhledávací stromy
BVS - přesun podstromů
■ Transplant nahradí podstrom s kořenem u podstromem s kořenem v
■ otcem uzlu v se stane otec uzlu u
■ otec uzlu u bude mít uzel v jako svého syna
Transplant(T, u, v)
1 if u.p — Nil then T.rootv
2 else if u — u.p.left then u.p.left <(— v
3 else u.p.right <(— v
4 fi
5 fi
6 if v    iV*Z then u.p    «.p fi
0
11. dubna 2016       21 / 139
Vyhledávací stromy
Binární vyhledávací stromy
BVS - odstranění uzlu
Tree_Delete(T, z)
i if z.left = Nil
2 then Transplant(T, z, z.right)
3 else if z.right — Nil
4 then Transplant(T, z, z.left)
5 else y <— TREEJV[iNiMUM(;z.ri0/ii)
6 if y.p ^ z then Transplant(T, y, y.right)
7 y.right z.right
8 y.right.p y
9 fi
10 Transplant(T, z, y)
11 y-left ^— z.left
12 y.left.p y
13 fi
14 fi
o
11. dubna 2016       22 / 139
Vyhledávací stromy
Binární vyhledávací stromy
Složitost
všechny uvedené operace nad binárním vyhledávacím stromem mají složitost úměrnou hloubce stromu, tj. v nejhorším případě 0(n), kde n je počet uzlů stromu
při hledání předchůdce a následníka nemusíme vůbec porovnávat klíče
operace se dají využít k seřazení klíčů např. tak, že najdeme minimální klíč a pak (rekurzivně) jeho následníka (složitost?!)
o
11. dubna 2016       23 / 139
Vyhledávací stromy
Binární vyhledávací stromy
Vyvážené binární vyhledávací stromy
hloubka stromu je logaritmická
složitost operací je úměrná hloubce stromu
■ AVL stromy
■ 2 - 3 stromy
■ 2-3-4 stromy
■ B stromy
■ červeno černé stromy
Vyhledávací stromy
Binární vyhledávací stromy
Modifikace datových struktur
■ reálné situace, ve kterých potřebujeme datovou strukturu odlišnou od „učebnicových struktur"
■ ??? účelnost návrhu úplně nové struktury
■ možné řešení:
• rozšíření některé známé struktury o nové informace
• návrh nových operací nad takto rozšířenou strukturou
• ... při zachování efektivnosti původních operací
příklad: využití binárních vyhledávacích stromů pro reprezentaci množiny intervalů
o
11. dubna 2016       25 / 139
Vyhledávací stromy
Intervalové stromy
Reprezentace intervalů
■ číselný interval (£1,^2)
■ objekt i s atributy i.low a i.high
■ intervaly i a i' se překrývají právě když i.low < i'.high a současně i'.low < i.high
■ pro libovolné dva intervaly i a iř platí právě jedna z možností
• intervaly se překrývají
• interval i je vlevo od i', tj. i.high < i'.low
• interval i' je vlevo od i, tj. i'.high < i.low
hledáme datovou strukturu pro reprezentaci množiny intervalů nad kterou je možné efektivně implementovat operace
■ Interval_Insert(T, x) - do množiny intervalů T přidá objekt reprezentující interval x
■ Interval_Delete(T, x) - z množiny intervalů T odstraní objekt reprezentující interval x
■ Interval_Search(T, i) - vrátí ukazatel na objekt, který reprezentuje interval překrývající se s intervalem i resp. hodnotu Nil, když takový objekt neexistuje
bm 11. dubna 2016       26 / 139
Vyhledávací stromy
Intervalové stromy
řešení 1
■ seznam intervalů
■ přidání intervalu v konstantním čase
■ odebrání a vyhledání intervalu v čase 0(n)  (n je počet intervalů v množině)
reseni 2
■ uspořádaný seznam intervalů
■ všechny operace v čase 0{n)
intervalové stromy
■ rozšíření binárních vyhledávacích stromů
o
11. dubna 2016       27 / 139
Vyhledávací stromy
Intervalové stromy
Intervalové stromy
■ binární vyhledávací strom
■ každý uzel má atributy i.low, i.high, a i.max
■ jako klíč je použita hodnota x.low
■ x.max je maximální hodnota krajního bodu intervalu uloženého v podstromu s kořenem x
x.max — ma,x{x.high, x.left.max, x.right.max}
o
11. dubna 2016       28 / 139
Intervalové stromy
Přidání nového intervalu
Vyhledávací stromy
■ postupujeme jako v BVS od kořene, vkladaný uzel se stane listem
■ každému uzlu y na cestě z kořene do nového uzlu x aktualizujme hodnotu y.max právě když y.max < x.high
■ pro žádný vrchol neležící na cestě z kořene do nového uzlu se hodnota max nemění
o
11. dubna 2016       29 / 139
Vyhledávací stromy
Intervalové stromy
Odstranění intervalu
■ postupujeme jako v BVS
■ na pozici odstraněného uzlu se přesune uzel y
■ pro aktualizaci hodnot max procházíme cestu od původní pozice uzlu y do kořene a každému uzlu z na této cestě aktualizujeme hodnotu
z.max — ma,x{z.left.max, z.right.max, z.high}
■ složitost operace se navýší o 0{n)
■ celková složitost operace odstranění intervalu zůstává asymptoticky stejná
o
11. dubna 2016       30 / 139
Intervalové stromy
Vyhledávání intervalu
Vyhledávací stromy
lnterval_Search(T, i)
1 x     T.root
2 while x 7^ Nil A  intervaly i a (x.low, x.high) se nepřekrývají do
3 if x.left    Nil A x.left.max > How
4 then x <r- x.left
5 else x     x.right fi (5 od
7 return x
složitost
■ vyhledávání začíná v kořeni
■ po každé iteraci cyklu testujeme uzel, jehož hloubka je o 1 vyšší
■ složitost je úměrná hloubce stromu
o
11. dubna 2016       31 / 139
Vyhledávání intervalu
lnterval_Search(T, i)
1 x T.root
2 while x 7^ Nil A  intervaly i a (x.low, x.high) se nepřekrývají do
3 if x.left    Nil A x.left.max > i.low
4 then x x.left
5 else x ^— x.right fi od č return x
korektnost - případ 1 - ve vyhledávání postupujeme doprava
■ předpokládejme, že ve vyhledávání postupujeme z uzlu x doprava a levý podstrom není prázdný
■ platí x.left.max < i.low (jinak by jsme postupovali doleva)
■ pro každý interval (a, b) z levého podstromu platí
b < x.left.max (z definice hodnoty max)
■ b < i.low znamená, že i se nepřekrývá se žádným intervalem v levém podstromu
bm 11. dubna 2016       32 / 139
Vyhledávací stromy
Intervalové stromy
Vyhledávání intervalu
lnterval_Search(T, i)
1 x T.root
2 while x 7^ Nil A  intervaly i a {x.low, x.high) se nepřekrývají do
3 if x.left    Nil A x.left.max > i.low
4 then x <r- x.left
5 else x ^— x.right fi (5 od
7 return x
korektnost - případ 2 - ve vyhledávání postupujeme doleva
■ předpokládejme, že žádný interval levého podstromu se nepřekrývá s i
■ v levém podstromu leží interval (c, d) takový, že d — x.left.max
■ i.high < c (i a (c, d) se nepřekrývají)
■ pro každý interval (a, b) z pravého podstromu platí c < a      (vlastnost BVS)
■ i.high < a znamená, že i se nepřekrývá se žádným intervalem v pravém podstromu
bm 11. dubna 2016       33 / 139
Intervalové stromy - modifikace
■ vyhledávání všech překrývajících se intervalů
■ intervaly vyšší dimenze
■ namísto obecného binárního vyhledávacího stromu můžeme použít vyvážený binární vyhledávací strom
o
11. dubna 2016       34 / 13
Radix trees
■ využití binárních vyhledávacích stromů pro lexikografické řazení binárních retezcu
■ řetězce postupně vkládáme do vyhledávacího stromu
■ po vložení všech řetězců strom prohledáme a klíče vypíšeme v pořadí preorder
■ časová složitost je 0(n), kde n je součet délek všech řetězců
■ zobecnění pro řetězce nad libovolnou abecedou - použijeme stromy, jejichž arita je stejná jako velikost abecedy
o
11. dubna 2016       35 / 139
Červeno černé stromy
Datové struktury
■ Binární vyhledávací stromy
■ Intervalové stromy
□ Červeno černé stromy
■ Červeno černé stromy
■ Rank prvku
■ Zřetězené hašování
■ Otevřená adresace
o
11. dubna 2016       36 / 139
Červeno černé stromy
Červeno černé stromy
Červeno černé stromy
Červeno černý strom je binární vyhledávací strom, jehož každý uzel je obarvený červenou anebo černou barvou a splňuje podmínky
□ kořen stromu je černý
B listy stromu nenesou žádnou hodnotu, tj. jsou označeny Nil, a mají černou barvu
Q když je uzel červený, tak jeho otec je černý
Q pro každý uzel x stromu platí, že všechny cesty z uzlu x do listů obsahují stejný počet černých uzlů
alternativně: oba synové červeného uzlu mají černou barvu
■ každý uzel obsahuje atributy key, color, left, right, p
■ jestliže uzel nemá některého syna anebo otce, tak příslušný atribut má hodnotu Nil
o
11. dubna 2016       37 / 139
Červeno černé stromy
Červeno černé stromy
Výška uzlu a černá výška uzlu
■ výška uzlu x je rovna počtu hran na nejdelší cestě z x do listu
■ černá výška uzlu x, bh(x), je rovna počtu černých uzlů na cestě z x do listu (uzel x nezapočítavame)
(díky vlastnosti 4 je černá výška dobře definovaná!)
NIL    NIL   NIL    NIL NIL NIL
0
11. dubna 2016       38 / 139
Červeno černé stromy
Červeno černé stromy
Výška červeno černého stromu
Lema 1
Každý uzel s výškou h má černou výšku alespoň h/2.
z vlastnosti 4 plyne, že v nejhorším případě je každý druhý uzel na cestě červený Lema 2
Pro každý uzel x platí, že podstrom s kořenem x má alespoň 2bh^ — 1 vnitřních uzlů2.
důkaz indukcí k výšce h uzlu x
h — 0 x je list =^> bh(x) — 0 a současně počet vnitřních uzlů podstromu s kořenem x je 0
h > 0 • nechť x má výšku h a černou výšku bh(x) — b
• každý syn uzlu x má výšku h — 1 a černou výšku b anebo b — 1
• z indukčního předpokladu má podstrom každého syna alespoň 2bh(x)-i _ 2 vnitřních uzlů
• podstrom s kořenem x má alespoň 2{2bh^~1 — 1) + 1 = 2bh^ — 1 _vnitřních uzlů_
2vnitmím uzlem rozumíme uzel, který nese hodnotu, tj. list není vnitřním uzlem
bm 11. dubna 2016       39 / 139
Červeno černé stromy
Červeno černé stromy
Výška červeno černého stromu
Věta 3
Červeno černý strom s n vnitřními uzly má výšku nejvýše 21og2(n + 1).
■ nechť strom má výšku h a černou výšku b m z předchozích lemmat plyne
n > 2b - 1 > 2h/2 - 1
■ po úpravě log2(n + 1) > h/2, a tedy h < 2 log2(n + 1)
o
11. dubna 2016       40 / 139
Červeno černé stromy
Červeno černé stromy
Červeno černé stromy - operace
Search, Min, Max, Successor, Predecessor se implementují stejně jako pro binární vyhledávací stromy
vyjmenované operace mají složitost O(logn)
Insert a Delete modifikují strom
modifikace může porušit vlastnosti červeno černého stromu jsou potřebné další kroky, které vlastnosti obnoví
základní operací, která vede k obnovení požadovaných vlastností, je rotace
o
11. dubna 2016       41 / 139
Červeno černé stromy
Červeno černé stromy
Rotace
■ rotace zachovává vlastnost binárního vyhledávacího stromu
a G a,b G /3,c G 7     a < x < b < y < c
■ časová složitost 0(1)
o
11. dubna 2016       42 / 139
Červeno černé stromy
Červeno černé stromy
Rotace
Left_Rotate(T, x)
1 y x.right
2 x.right y.left
3 if y.left 7^ T.nil
4 then y.left.p    x fi
6 if x.p = T.nil
7 then T.rooty
s     else if x = x.p.left
9 then x.p.lefty
else x.p.right <(— y f i f i ii y.left x
o
11. dubna 2016       43 / 139
Červeno černé stromy
Červeno černé stromy
Přidání nového uzlu
■ uzel x do stromu přidáme stejným postupem jako do binárního vyhledávací stromu
■ jakou barvou máme obarvit nový uzel?
■ obě možnosti mají za důsledek porušení některých vlastností červeno černého stromu
■ řešení: obarvi uzel x červenou barvou
■ vlastnosti
1 (černý kořen)   jestliže x je kořenem, tak vlastnost neplatí
3 (otec červeného uzlu je černý)    nemusí platit
4 (stejná černá výška)    zůstává v platnosti
o
11. dubna 2016       44 / 139
Červeno černé stromy
Červeno černé stromy
Přidání nového uzlu - schéma
RB_lnsert(T, a)
1 Tree_Insert(T, a)
2 a.color red
3 while a ^ T.root A a.p.color = red
4 do if a.p — a.p.p.left
5 then d <(— a.p.p.right
6 if d.color — red
7 then případ 1
8 else if a — a.p.right
9 then případ 2 10 else případ 3 n fi
12 fi
is else stejně jako THEN se záměnou left a right
14 fi
15 od
16 T.root.color <(— black
o
11. dubna 2016       45 / 139
Červeno černé stromy
Červeno černé stromy
Přidání nového uzlu - schéma
případ 1
a.p.color black d.color black a.p.p.color red a a.p.p
případ 2
a <— a.p
Left_Rotate(T, a) případ 3
a.p.color black a.p.p.color red Right_Rotate(T, a.p.p)
o
11. dubna 2016       46 / 139
Červeno černé stromy
Červeno černé stromy
Přidání nového uzlu - korekce - případ 1
■ nově přidaný uzel a je červený
■ jeho otec b je červený a je levým synem svého otce3
■ strýc d uzlu a je červený
■ praotec c uzlu a je černý
■ obarvi otce (6) a strýce (oř) uzlu a černou barvou
■ obarvi praotce (c) uzlu a červenou barvou
x    y x y
stromy z> x, y)pj q mají černý kořen a všechny mají stejnou černou výšku
3situace když b je pravým synem svého otce se řeší symetricky
Červeno černé stromy
Červeno černé stromy
Přidání nového uzlu - korekce - případ 2
■ uzel a je červený a je pravým synem svého otce
■ jeho otec b je červený a je levým synem svého otce
■ strýc d uzlu a je černý
■ praotec c uzlu a je černý
■ proveď levou rotaci kolem otce (b) uzlu a
■ pokračuj na případ 3
x    y    Left_Rotate(Ô) z x
0
11. dubna 2016       48 / 139
Červeno černé stromy
Červeno černé stromy
Přidání nového uzlu - korekce - případ 3
■ uzel a je červený a je levým synem svého otce
■ jeho otec b je červený a je levým synem svého otce
■ strýc d uzlu a je černý
■ praotec c uzlu a je černý
proveď pravou rotaci kolem praotce (c) uzlu a
vyměň obarvení mezi otcem (6) uzlu a a jeho novým bratrem (c)
, b .
y       p q
p q
p q
o
11. dubna 2016       49 / 139
Červeno černé stromy
Červeno černé stromy
Složitost přidání nového uzlu
■ případ 1: změna obarvení 3 uzlů
■ případy 2 a 3: jedna nebo dvě rotace a změna obarvení 2 uzlů
■ v případě 1 může změna barvy praotce (c) uzlu a způsobit nový konflikt a to když otec uzlu c má červenou barvou
■ v popsaném případě musíme pokračovat další iterací a korigovat barvu uzlu c
■ konečnost je garantována faktem, že každou iterací se zmenšuje vzdálenost korigovaného uzlu od kořene stromu
■ celková složitost O(logn)
o
11. dubna 2016       50 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu
■ uzel x ze stromu odstraníme stejným postupem jako z binárního vyhledávací stromu
■ v případě, že odstraněný uzel měl červenou barvu, vlastnosti stromu zůstávají zachované
■ v případě, že měl černou barvu, může dojít k porušení vlastnosti 4 (stejná černá výška)
■ černou barvu z odstraněného uzlu přesouváme směrem ke kořenu tak, aby jsme obnovili platnost vlastnosti 4
o
11. dubna 2016       51 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu a - případy 1 a 2
a nemá levého syna
■ odstraň a a nahraď ho jeho pravým synem (b)
■ jestliže po přesunu uzel b a jeho otec porušují vlastnost 3 (oba jsou červené), tak uzel b obarvíme černou barvou; tím zachováme černou výšku (a musel být černý)
a nemá pravého syna - symetricky
o
11. dubna 2016       52 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu a - prípad 3
a má dva syny, následník (successor) uzlu a je jeho pravým synem
■ odstraň a a nahraď ho jeho následníkem (c)
■ levý syn uzlu a se stane levým synem následníka uzlu a
■ po přesunu obarvíme následníka (c) barvou uzlu a
■ jestliže následník měl původně černou barvu, tak černou barvu dostane jeho syn, tj. syn má dvě barvy (červenou a černou anebo černou a černou)
■ problém dvou barev vyřešíme při korekci
o
i
11. dubna 2016       53 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu a - případ 4
a má dva syny, následník (successor) uzlu a není jeho synem
■ následníka (d) nahraď jeho pravým synem (e)
■ odstraň a a nahraď ho jeho následníkem (d), synove uzlu a se stanou syny následníka (d)
■ po přesunu obarvíme následníka (d) barvou uzlu a
■ jestliže následník měl původně černou barvu, tak černou barvu dostane jeho syn, tj. syn má dvě barvy (červenou a černou anebo černou a černou)
■ problém dvou barev vyřešíme při korekci
o
11. dubna 2016       54 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu - korekce dvou barev - případ 1
uzel a má dvě barvy bratr (c) uzlu a je červený
proveď levou rotaci kolem otce (b) uzlu a
vyměň barvy mezi otcem (6) a praotcem (c) uzlu a
pokračuj některým z následujících případů
z    w    p q
Rotate_Left(6)
x    y    z w
x    y    z    w ;
Vv__________________'
jiný případ
stromy x,y, z,w,p,q mají stejnou černou výšku, nemají žádný uzel s dvěma barvami a neporušují žádnou vlastnost červeno černého stromu
o
11. dubna 2016
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu - korekce dvou barev - případ 2
uzel a má dvě barvy
bratr (c) uzlu a stejně jako oba jeho synové (d, e) mají černou barvu
■ vezmi jednu černou barvu z uzlu a a přesuň ji do jeho otce (b)
■ bratr (c) uzlu a dostane červenou barvu (aby se zachovala černá výška)
■ uzel se dvěma barvami se přesunul blíž ke kořenu, problém jeho dvou barev řešíme rekurzivně
o
11. dubna 2016       56 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu - korekce dvou barev - případ 3
uzel a má dvě barvy
bratr (c) uzlu a a jeho pravý syn (e) mají černou barvu, levý syn (d) je červený
■ proveď pravou rotaci kolem bratra (c) uzlu a
■ vyměň barvy mezi původním a novým bratrem uzlu a (d, c)
■ pokračuj případem 4
o
11. dubna 2016       57 / 139
Červeno černé stromy
Červeno černé stromy
Odstranění uzlu - korekce dvou barev - případ 4
uzel a má dvě barvy
bratr (c) uzlu a má černou barvu, jeho pravý syn (e) má červenou barvu
■ proveď levou rotaci kolem otce (b) uzlu a
■ obarvi nového praotce (c) uzlu a barvou jeho otce (b)
■ přesuň černou barvu z uzel a na jeho otce (6), otec (b) se stane černým
■ uzel (e) se stane černým
X
z    w    p q
RotateJLeft
x    y    z w
x    y    z w
0
11. dubna 2016
Červeno černé stromy
Rank prvku
Pořadí (rank) prvku
využití červeno černých stromů při určení ranku (pořadí) prvku a vyhledávání
prvku s daným rankem
■ množina A obsahující n vzájemně různých čísel
■ číslo x £ A má rank i právě když v A existuje přesně i — l čísel menších než x možné řešení
■ jestliže prvky A jsou uložené v poli, tak v čase 0{n) můžeme
• najít číslo s rankem i
• určit rank daného čísla
existuje efektivnější řešení?
při použití červeno černých stromů dokážeme oba problémy vyřešit v čase O(logn)
o
11. dubna 2016       59 / 139
Červeno černé stromy
Rank prvku
Rozšírení červeno černých stromů
požadujeme
■ efektivní implementaci standardních operací nad červeno černým stromem
■ efektivní implementaci operace RB_Select(x, i), která najde z-ty nejmenší klíč v podstromě s kořenem x
■ efektivní implementaci operace RB_Rank(T.x), která určí rank klíče uloženého v uzlu x
jestliže strom obsahuje uzly se stejnými klíči, tak rankem klíče je pořadí uzlu v Inorder uspořádání uzlů stromu
o
11. dubna 2016       60 / 139
Červeno černé stromy
Rank prvku
Princip
ke každému uzlu x přidáme atribut x.size - počet (vnitřních) uzlů v podstromě s kořenem x, včetně uzlu x
x.size = x.left.size + x.right.size + 1
NIL    NIL   NIL    NIL NIL NIL
0
11. dubna 2016       61 / 139
Červeno černé stromy
Rank prvku
Vyhledání klíče s daným rankem
RB_SelectO,z)
1 r     x.left.size + 1
2 if i — r then return x
3 else if i < r then return RB_SELECT(x./e/í, i)
4 else return RB-Select(x.right, i
r) fi fi
korektnost
■ z definice atributu .size plyne, že počet uzlů v levém podstromu uzlu x navýšený o 1 (r) je přesně rank klíče uloženého v x v podstromě s kořenem x
■ když i — r, tak x je hledaný uzel
■ když i < r, tak z-ty nejmenší klíč se nachází v levém podstromě uzlu x a je z-tým nej menším klíčem v tomto podstromě
■ když i > r, tak z-ty nejmenší klíč se nachází v pravém podstromě uzlu x a jeho poradiv tomto podstromě je i snížené o počet uzlů levého podstromu
o
11. dubna 2016       62 / 139
Červeno černé stromy
Rank prvku
Vyhledání klíče s daným rankem
RB_Select(>,z)
1 r     x.left.size + 1
2 if i — r then return x
3 else if i < r then return RB_SELECT(x./e/t, i)
4 else return RB_SELECT(x.rz^/it, i — r) fi fi
složitost
■ každé rekurzivní volání se aplikuje na strom, jehož hloubka je o 1 menší
■ hloubka červeno černého stromu je O(logn)
■ složitost RB_Select je O(logn)
o
11. dubna 2016       63 / 139
Červeno černé stromy
Rank prvku
Určení ranku daného prvku
NIL    NIL   NIL    NIL NIL NIL
rank prvku 11
■ všechny uzly v levém podstromě uzlu 11
■ sledujeme cestu od 11 do kořene
■ jestliže uzel na cestě je levým synem, nemění rank prvku 11
■ jestliže uzel na cestě je pravým synem, tak on sám jakož i jeho levý podstrom obsahují klíče menší než 11
o
11. dubna 2016       64 / 139
Určení ranku daného prvku
RB_Rank(T, x)
1 r     x.left.size + 1
2 y x
3 while y ^ T.root
4 do if y — y.p.right
5 then r <(— r + y.p.left.size + 1 f i
6 y ^— y.p od
7 return r
korektnost
invariant na začátku každé iterace while cyklu je r rovné ranku klíče x.key v podstromě s kořenem y
inicializace na začátku je r rovné ranku x.key v podstromě s kořenem x a x = y
o
11. dubna 2016       65 / 13
Červeno černé stromy
Rank prvku
RB_Rank(T, x)
1 r     x.left.size + 1
2 y x
3 while y ^ T.root
4 do if y — y.p.right
5 then r     r + y.p.left.size + 1 f i
6 y    y.p od
7 return r
invariant na začátku každé iterace while cyklu je r rovné ranku klíče x.key
v podstromě s kořenem y iterace
■ na konci cyklu se vykoná y <(— y.p
■ po provedení cyklu proto musí platit, že r je rank x.key v podstromě s kořenem y.p
■ jestliže y je levý syn, tak všechny klíče v podstromě jeho bratra jsou větší než x.key a r se nemění
■ jestliže y je pravý syn, tak všechny hodnoty v podstromě jeho bratra jsou menší než x.key a hodnota r se zvýší o velikost tohoto stromu plus 1 (klíč v uzlu y.p je taky menší než x.key)
bm 11. dubna 2016       66 / 139
RB_Rank(T, x)
1 r     x.left.size + 1
2 y x
3 while y ^ T.root
4 do if y — y.p.right
5 then r r + y.p.left.size + 1 f i č         y ^— y.p od
7 return r
invariant na začátku každé iterace while cyklu je r rovné ranku klíče x.key v podstromě s kořenem y
ukončení
výpočet končí když y = T.root, z platnosti invariantu plyne korektnost algoritmu
složitost
■ po každé iteraci se sníží vzdálenost y od kořene o 1
■ hloubka červeno černého stromu je O(logn)
■ složitost RB_Rank je O(logn)
o
11. dubna 2016
Červeno černé stromy
Rank prvku
Přidání nového uzlu
přidání uzlu postupujeme od kořene do listu, kde vytvoříme nový uzel, přitom se změní (o 1) pouze velikost podstromů těch uzlů, kterými procházíme
korekce stromu změna barvy uzlu nemění velikost podstromu při rotaci se může změnit velikost podstromů proceduru Left_Rotate doplníme o příkazy y.size x.size
x.size     x.left.size + x.right.size + 1 symetricky pro pravou rotaci
Left_Rotate(T, x) <-
11. dubna 2016       68 / 139
Červeno černé stromy
Rank prvku
Odstranění uzlu
první fáze odstraní uzel ze stromu
• na pozici odstraněného uzlu se přesune uzel y
• pro aktualizaci hodnot size procházíme cestu od původní pozice uzlu y do kořene a každému uzlu na této cestě snížíme hodnotu size o 1
• složitost operace se navýší o O(logn)
korekce obarvení stromu
• ke změně velikosti podstromu může dojít při rotaci, aktualizace hodnot viz přidání nového uzlu
• počet rotací je nejvýše 3, složitost se navýší o 0(1)
složitost přidávání i odstraňování uzlu zůstává asymptoticky stejná
o
11. dubna 2016       69 / 139
B-stromy
Datové struktury
■ Binární vyhledávací stromy
■ Intervalové stromy
■ Červeno černé stromy
■ Rank prvku
B B-stromy
■ Zřetězené hašování
■ Otevřená adresace
o
11. dubna 2016       70 / 139
B-stromy
B stromy
B stromy jsou zobecněním binárních vyhledávacích stromů
■ B strom je balancovaný, všechny listy mají stejnou hloubku
■ vnitřní uzel stromu obsahuje t — 1 klíčů a má t následníků
■ klíče ve vnitřních uzlech stromu zároveň vymezují t intervalů, do kterých patří klíče každého z jeho t podstromů
využití B stromů
■ B stromy se typicky používají v databázových systémech a aplikacích, kde objem zpracovávaných dat není možné uchovávat v operační paměti
■ počet klíčů uložených v uzlu (a tím i počet následníků) se může pohybovat od jednotek po tisíce; cílem je minimalizovat počet přístupů na disk
■ v pseudokódu modelujeme přístupy operacemi DiSK_READa Disk_Write
■ existují různé varianty, podrobněji viz např. PV062
■ Bayer, McCreight 1972
o
11. dubna 2016       71 / 139
B-stromy
B stromy vs BVS a červeno černé stromy
■ zachován princip vyhledávání
■ všechny uzly mají stejnou hloubku
■ uzly B stromů můžou mít víc následníků
■ výška B stromu je O(logn), díky většímu počtu následníků může být ale výrazně menší
■ operace minimalizují průchod stromem
o
11. dubna 2016       72 / 139
B-stromy
Stupeň B stromu
minimální stupeň stromu
číslo t, které definuje dolní a horní hranici na počet klíčů uložených v uzlu
■ každý uzel (s výjimkou kořene) musí obsahovat alespoň t — 1 klíčů
■ jestliže strom je neprázdný, tak kořen musí obsahovat alespoň jeden klíč
■ každý vnitřní uzel (s výjimkou kořene) musí mít alespoň t následníků
■ každý uzel může obsahovat nejvýše 2t — 1 klíčů
■ každý vnitřní uzel může mít nejvýše 2t následníků
■ uzel, který má přesně 2t následníků, se nazývá plný
■ nejjednodušší B strom má minimální stupeň 2
■ každý jeho vnitřní uzel má 2, 3 anebo 4 následníky
■ obvykle se označuje jako 2-3-4 strom
o
11. dubna 2016       73 / 139
B-stromy
Výška B stromu
kořen obsahuje alespoň jeden klíč, každý vnitřní uzel alespoň t — 1 klíčů
strom má 1 uzel hloubky 0 (kořen), alespoň 2 uzly hloubky 1, alespoň 2t uzlů hloubky 2, alespoň 2t2 uzlů hloubky 3, obecně alespoň 2th~1 uzlů hloubky h
h h-1
i=l i=0 th - 1
=   l + 2(í- 1)(——■—) =2th-l
L -L
z toho th <       a tedy logr th < log, □
11. dubna 2016       74 / 13
B-stromy
Definice B stromu
■ každý uzel x má atributy
• x.n - počet klíčů uložených v uzlu x
• klíče x.keyi,x.kei/2, • • • ,x.keyx.n, které jsou uloženy v neklesajícím pořadí
• x.leaf - booleovská proměnná nabývající hodnotu je true právě když uzel x je listem stromu
■ každý vnitřní uzel x obsahuje navíc x.n-\-1 ukazatelů x.ci, X.c2,..., x.Cx n+1
■ klíče x.keyi definují intervaly, z kterých jsou klíče uložené v každém
z podstromů; jestliže ki je klíč uložený v podstromě s kořenem x.Ci, tak platí
ki < x.keyi < k2 < x.key2 < ... < x.keyx.n < kx.n+i
■ všechny listy mají stejnou hloubku
o
11. dubna 2016       75 / 139
B-stromy
Operace nad B stromem
■ vytvoření stromu; vyhledávání, přidání a odstranění klíče
■ typické aplikace, které využívají B stromy, pracují s daty uloženými na externím disku
■ před každou operací, která přistupuje k objektu x, se nejdříve musí vykonat operace Disk_Read(x), která zkopíruje objekt do operační paměti
(za předpokladu, že tam není)
■ symetricky operace Disk_Write(x) se použije pro uložení všech změn vykonaných nad objektem x
■ předpokládáme, že kořen B stromu je vždy uložený v operační paměti a proto nad kořenem vykonáváme pouze operaci Disk_Write
■ asymptotická složitost všech operací je úměrná hloubce stromu, tj. O(logn), kde n je počet klíčů uložených v stromu
■ z důvodu optimalizace počtu přístupů na externí disk jsou všechny operace navrženy tak, aby se uzel stromu navštívil nejvýše jednou, tj. všechny operace postupují směrem od kořene dolů a nikdy se nevracejí do již navštíveného uzlu
o
11. dubna 2016       76 / 139
B-stromy
Vyhledávání
■ analogicky jako v binárním vyhledávacím stromě, vybíráme jednoho z následníků uzlu
■ argumentem operace je ukazatel T.root na kořen stromu a hledaný klíč k
■ jestliže klíč k je v B stromě, operace vrátí dvojici (y, i), kde y je uzel a i index takový, že y.keyi — k
■ v opačném případě vrátí hodnotu Nil
vyhledání klíče R
T.root
B C    F G    J K L
N P	R S	V W	Y Z
0
11. dubna 2016       77 / 139
B-stromy
Vyhledávání
B-Tree_Search(x, k)
1 i <-1
2 while i < x.n A x.keyi < k do
3 1 <r- Í + 1 Od
4 if i < x.n A x.keyi — k
5 then return (x, i) fi
6 if x.leaf then return TVzZ
7 else Disk_Read(x.q)
8 return B-Tree_Search(x.q, k) fi
■ počet Disk_Read operací je ohraničený hloubkou stromu h
■ počet opakování cyklu 2 - 3 je nejvýše 2t (t je minimální stupeň B stromu)
■ celková složitost je 0{th) — 0{t\ogtn)
o
11. dubna 2016       78 / 139
B-stromy
Vytvoření prázdného stromu
B-Tree_Create(T)
1 x <— Allocate_Node()
2 x.leaf trne
3 x.n 0
4 Disk_Write(x)
5 T.root x
celková složitost 0(1)
o
11. dubna 2016       79 / 139
B-stromy
Přidání klíče
■ podobně jako u BVS hledáme list, do kterého uložíme nový klíč
■ nemůžeme vytvořit nový list (jako v BVS), protože by jsme porušili vlastnost minimálního počtu klíčů v uzlu
■ klíč vložíme do existujícího listu
■ když vložením klíče dojde k porušení vlastnosti maximálního počtu klíčů, tak list rozdělíme na dva nové listy
■ rozdělením se zvýší počet následníků předchůdce původního listu
■ pokud se tím poruší vlastnost maximálního počtu následníků, tak musíme (rekurzivně) rozdělit i předchůdce
■ proces rozdělování uzlů se v nejhorším případě zastaví až v kořeni stromu
o
11. dubna 2016       80 / 139
B-stromy
Přidání klíče B do listu, který není plný
minimálny stupeň stromu je 3
J K	N O	R S T U V	Y Z
._GMPX
A B C D E    J K   NO   R S T U V   Y Z
0
11. dubna 2016       81 / 139
B-stromy
Přidání klíče Q do plného listu
minimálny stupeň stromu je 3
J K	N O	R S T U V	Y Z
A B C D E	J K	N O	Q R S	U V	Y Z
0
11. dubna 2016       82 / 139
B-stromy
Rozdělení uzlu - schéma
minimálny stupeň stromu je 4
/
CC
N W
y = x.cí u
\ \
/    .        . X
x
\o      \o \o
íS)-   <$>' <$>'
N. SW
y = cc. c*
2 = cc.ci+i
p		R	S	T	U	V		p	Q	R
					< >		f \	f \		f V
T	U	v
		f V
T\ T2 T3 T4 T5 T6 T7 T8
TľT2T3T4 T5T6T7T8
argumentem operace B-Tree_Split je
■ vnitřní uzel x, který není plný
■ index i takový, že x.ci je plný následník uzlu x
bm 11. dubna 2016       83 / 139
B-stromy
Rozdělení kořene - schéma
T.root
r
T\ T2 T3 T4 T5 Tq T7 T8
T.root
A	D	F	H	L	N	P	-*►	A	D	F
	f \									
Ti T2 T3 T4
L	N	P
V )		f V
T5 T6 T7 T8
když potřebujeme rozdělit kořen stromu, tak nejdříve vytvoříme nový, prázdný uzel, který se stane novým kořenem stromu
rozdělení kořene způsobí navýšení hloubky stromu o 1
11. dubna 2016       84 / 13
B-stromy
Rozdělení uzlu - implementace
B-Tree_Split(x, i)
1 z <— Allocate_Node()
2 y x.Ci
3 z.leaf y.leaf
4 z.n    t — 1
5 for j = 1 to t — 1 do z.keyj     y.key^+t od
(5 if -^y.leaf then for j; = 1 to £ do z.Cj y.Cj+t °d fi 7 y.n <r- t — 1
s for j — x.n + 1 downto i + 1 do x.cJ+i     x.Cj od
9 X.Ci+i z
i o for j = x.n downto i do x.keyj+i     x.keyi od
íí x.keyi y.keyt
12 x.n     x.n + 1
13 DlSK_write(y)
14 DlSK_write(2:)
15 Disk_Write(x)
o
11. dubna 2016       85 / 139
B-stromy
Rozdělení uzlu - složitost
■ rozdělujeme uzel y (řádek 2)
■ když y není list, tak má před rozdělením 2t následníků a po rozdělení počet jeho následníků klesne na t
■ zje nový uzel (řádek 1) a jeho následníky tvořit největších následníků uzlu y
■ celková složitost je 0{t)
■ počet operací Disk_Write a Disk_Read je (9(1)
o
11. dubna 2016       86 / 139
B-stromy
Přidání klíče - optimalizace
základní varianta
■ rozdělení uzlu způsobí navýšení počtu následníků předchůdce rozdělovaného uzlu
■ pokud se tím poruší vlastnost maximálního počtu následníků, tak musíme (rekurzivně) rozdělit i předchůdce
■ proces rozdělování uzlů se v nejhorším případě zastaví až v kořeni stromu optimalizace
■ cílem je realizovat celou operaci přidání klíče při jednom průchodu stromu od kořene k listu (optimalizace počtu přístupů na disk!!!)
■ rozdělování může nastat pouze u těch uzlů, které jsou plné, tj. obsahují maximální povolený počet klíčů (2t — 1)
■ vždy, když procházíme přes plný uzel, rozdělíme ho na dva nové uzly a to tak, že každý ze dvou nových uzlů dostane t — 1 klíčů a jeden klíč se přesune do jejich otce
■ korektnost postupuje garantována, protože předchůdce rozdělovaného uzlu není plný
bm 11. dubna 2016       87 / 139
B-stromy
Přidání klíče L - procházíme přes plný uzel
minimálny stupeň stromu je 3
J K	N O	Q R S	U V	Y Z
J K L	N 0		Q R S	U V	Y Z
0
11. dubna 2016       88 / 139
B-stromy
Přidání klíče - implementace
B-Tree_lnsert(T, k)
1 r T.root
2 if r.n — 2t — 1
s    then s <— Allocat_Node()
4 T.root <(— s
5 s.leaf ^— falše
6 s.n <(— 0
7 s.c\ <(— r
8 B-Tree_Split(s, 1)
9 B-Tree_Insert_Nonfull(5, k)
10 else B-TREE_lNSERT_nonfull(r, k)
11 fi
■ řádky 3-9 řeší plný kořen stromu
■ na konci se volá procedura B-Tree_Insert_Nonfull, která vloží klíč do stromu, jehož kořen není plný
o
11. dubna 2016       89 / 139
B-stromy
Přidání klíče - implementace
B-Tree_lnsert_Nonfull(x, k)
1 i <— x.n
2 if x.leaf
3 then while i > 1 A x.keyi > k
4 do x.keyi+i <— x.keyi
5 i ^— i — 1 od
6 x.keyi+i <—
7 x.n <(— x.n + 1
5 Disk_Write(x)
9 else while z > 1 A x.keyi > fc do i ^ z - 1 od
10 i <— z + 1
jj Disk_Read(x.q)
if x.Q.n = 2í - 1 then B-Tree_Split(x, i)
ís if x.keyi < k then i «— z + 1 fi fi
14 B-Tree_Insert_Nonfull(x.q, k)
15 fi
0			11. dubna 2016       90 / 139
B-stromy
Přidání klíče - složitost
■ počet operací Disk_Write a Disk_Read je 0{h)
(vždy jenom jedna mezi dvěma voláními B-Tree_Insert_NonfullJ
■ celková složitost je 0(th) — 0{t\ogtn)
■ procedura B-Tree_Insert_Nonfull je tail - rekurzivní, a proto je počet uzlů, které musí být uloženy v operační paměti, konstantní
o
11. dubna 2016       91 / 139
B-stromy
Odstranění klíče
odstranění probíhá analogicky jako u binárního vyhledávacího stromu
■ jestliže se klíč určený k odstranění nachází v listu, odstraníme ho
■ jestliže se klíč určený k odstranění nachází v uzlu, který není listem, nahradíme ho jeho následníkem (resp. předchůdcem) a následníka odstraníme z listu ve kterém se původně nacházel
■ samotné mazání klíče se vždy realizuje v listu
■ operace má stejnou asymptotickou složitost jako u BVS
■ samotná implementace má ale několik speciálních případů, protože klíč může být odstraněn z libovolného uzlu
■ v optimalizované variantě klíč odstraníme při jednom průchodu stromem od kořene dolů, s možnou výjimkou návratu do uzlu, ve kterém byl původně uložen odstraňovaný klíč
o
11. dubna 2016       92 / 139
B-stromy
Odstranění klíče - základní varianta
odstranění klíče k z listu x
□ list x je současně kořenem stromu
• klíč k odstraníme
Q list x není kořenem a obsahuje alespoň t klíčů
• klíč k odstraníme
B list x není kořenem a obsahuje přesně t — 1 klíčů
• vezmi toho bratra y listu x, který má více klíčů
• vytvoř seznam obsahující klíče z listů x b y b navíc ten klíč z otce p listu x, který tvoří hranici mezi x b y
• délka seznamu je t — 2 (= počet klíčů v x) + 1 (= klíč z otce) + počet klíčů ví/>t-2 + l+t-l
• rozlišujeme dva případy podle délky seznamu
o
11. dubna 2016       93 / 139
B-stromy
Odstranění klíče - základní varianta - délka seznamu
3 A seznam obsahuje alespoň 2t — 1 klíčů
■ seznam rozdělíme na 3 části: Left, Middle a Right, kde Middle je medián seznamu, Left obsahuje klíče menší než medián a Right klíče větší než medián
■ klíč Middle vrátíme do otce p, ze kterého jsme předtím odebrali hraniční klíč
■ klíče Left a Right vložíme do dvou uzlů x a y
■ uzly x a y mají alespoň t — 1 klíčů, počet klíčů v uzlu p zůstal nezměněný, hotovo
3 B seznam obsahuje právě 2t — 2 klíčů
■ uzly x a y nahradíme jediným uzlem obsahujícím všechny klíče seznamu
■ nový list má povolený počet klíčů
■ otec p má počet klíčů o 1 nižší než původně
■ v případě, že počet klíčů v uzlu p klesl pod minimální hranici t — 1, opakujeme (rekurzivně) postup pro uzel p
o
11. dubna 2016       94 / 139
B-stromy
Odstranění klíče - základní varianta
■ po odstranění klíče z listu může klesnout počet klíčů v jeho uzlu pod minimální hranici
■ musíme realizovat operace, které obnoví platnost podmínky minimálního počtu klíčů v uzlu
■ může nastat situace, když se prochází strom od kořene k listu a potom zpátky od listu ke kořeni (např když všechny uzly na cestě od kořene do listu obsahujícího klíč mají stupeň přesně ť)
■ podobně jako při vkládaní klíče optimalizujeme proces odstranění klíče tak, aby sme minimalizovali počet přístupů na disk
o
11. dubna 2016       95 / 139
B-stromy
Odstranění klíče - optimalizace
■ postupujeme od kořene směrem k listu
■ vždy, když procházíme přes uzel, který má přesně t — 1 klíčů, tak uděláme takovou korekci, která zvýší počet klíčů v uzlu na t
■ když narazíme na uzel, ze kterého potřebujeme odstranit klíč, máme garanci, že jeho otec má alespoň t klíčů
■ když odstranění klíče z uzlu způsobí snížení počtu klíčů v jeho otci, nevznikne žádný problém
o
11. dubna 2016       96 / 139
B-stromy
Optimální odstranění klíče - pravidla
odstraňujeme klíč k
1 když klíč A: je v listu x, odstraň k z x
2 když klíč k je ve vnitřním uzlu x, tak
a. jestliže syn y, který je před k v x, obsahuje alespoň t klíčů, tak najdi v podstromě s kořenem y předchůdce k' klíče k\ nahraď v x klíč k klíčem k'\ rekurzivně odstraň klíč k'
b. jestliže syn y má méně než t klíčů tak, symetricky, prozkoumej syna z, který následuje za k v x\ v případě že z obsahuje alespoň t klíčů, tak najdi v podstromě s kořenem z následníka k' klíče k\ nahraď v x klíč k klíčem k'\ rekurzivně odstraň klíč k'
c. v případě, že synové y i z mají jen t — 1 klíčů, tak do vrcholu y přesuň klíč k a všechny klíče z vrcholu z\ z vrcholu x odstraň k a ukazatel na z\ nový uzel y obsahuje 2t — 1 klíčů (mezi nimi i klíč k)\ rekurzivně odstraň k z y
o
11. dubna 2016       97 / 139
B-stromy
Odstranění klíče - pravidla, pokračování
3 když klíč k není ve vnitřním uzlu x , tak urči kořen x.ci stromu, který musí obsahovat k (za předpokladu, že A: je v stromě); v případě, že uzel x.Ci obsahuje jen t — 1 klíčů, pokračuj body 3.a. anebo 3.b. které zaručí, že rekurzivní volání se aplikuje na uzel obsahující alespoň t klíčů; rekurzivně odstraň klíč k z vhodného následníka uzlu x
a. v případě, že x.Ci obsahuje jen t — 1 klíčů, ale některý z jeho přímých bratrů obsahuje alespoň t klíčů, tak zvyš počet klíčů v x.Ci a to tak, že přesuneš klíč z x do x.Ci, přesuneš klíč z bratra x a přesuneš příslušný ukazatel na následníka z bratra do uzlu x.Ci
b. v případě, že x.Ci i jeho jeho přímí bratři obsahují jen t — 1 klíčů, tak přesuň do x.Ci jeden klíč z x a všechny klíče z jednoho z bratrů
o
11. dubna 2016       98 / 139
B-stromy
Odstranění klíče F - případ 1
t = 3
		.C.GM.	
A B	D E F    J K L NO		
		. C, G M. / \	
A B	DE    J K L NO		
Q R S N U V
Y Z
Q R S \\U V
0
11. dubna 2016       99 / 139
B-stromy
Odstranění klíče M - případ 2a
t = 3
		, C, G M-/ \			
A B	D E		J K L		N 0
Q R S N U V
Y Z
A B	D E	J K	N 0
Q R S \ \U V
Y Z
0
11. dubna 2016        100 / 139
Odstranění klíče G — případ 2c
t = 3
A B	D E	J K	N 0
Q R S \\U V
N 0		Q R S	U V
Odstranění klíče B — případ 3a
t = 3
A B   E J K   N O    Q R S
A C	J K	N 0	Q R S
B-stromy
Odstranění klíče Z — případ 3b
t = 3
A C	J K	N O	Q R S	U V	Y Z
E. L.P.T
A C	J K	N O	Q R S	U V X Y
0
11. dubna 2016        103 / 139
B-stromy
Odstranění klíče D — případ 3b
t = 3
AB   D E J K NO
Q R S II U V H Y Z
A B	E J K	N 0	Q R S	U V	Y Z
					
					
		-  / \^			
A B	E J K	N 0	Q R S	U V	Y Z
					
11. dubna 2016        104 / 13
B-stromy
Odstranění klíče - složitost
■ v případě, že se odstraňovaný klíč nachází v listu, procedura prochází od kořene k listu bez nutnosti návratu
■ v případě, že se klíč nachází ve vnitřním uzlu, tak procedura postupuje od kořene k listu s možným návratem do vrcholu, ze kterého byl klíč odstraněn a nahrazen svým předchůdcem anebo následníkem (případy 2.a., 2.b.)
■ mezi dvěma rekurzivními voláním se vykoná nanejvýš jedna operace Disk_Write a jedna operace Disk_Read; jejich celkový počet je proto
O(h)
■ celková složitost je 0{th) — 0{t\ogtn)
o
11. dubna 2016        105 / 139
B+ stromy
■ klíče jsou uloženy pouze v listech
■ zřetězení listů zachovává pořadí klíčů
■ vnitřní uzly B+ stromů indexují listy
výhody a nevýhody
■ klíč v B stromě se najde před dosažením listu
■ vnitřní uzly B stromů jsou větší, do uzlů se proto může uložit méně klíčů strom je hlubší
■ operace vkládaní a odstraňování klíče z B stromu jsou komplikovanější
■ implementace B stromu je náročnější než implementace B+stromu
o
11. dubna 2016
Hašovaní
Datové struktury
■ Binární vyhledávací stromy
■ Intervalové stromy
■ Červeno černé stromy
■ Rank prvku
□ Hašovaní
■ Zřetězené hašovaní
■ Otevřená adresace
o
11. dubna 2016        107 / 139
Hašovaní
Slovník
■ dynamický datový typ pro reprezentaci množiny objektů
■ podporované operace
Insert^, x) do množiny S přidá objekt x Search(S', x) zjistí, zda množina S obsahuje objekt x Delete(S', x) z množiny S odstraní objekt x
vhodné datové struktury pro implementaci slovníku
seznam všechny operace mají složitost 0(n) (n je mohutnost množiny S)
vyhledávací strom se dá použít za předpokladu, že objekty mají číselný klíč, při použití vyváženého stromu je složitost operací O(logn)
cíl: složitost všech operací v nej horším případě Q(n) v očekávaném případě 0(1)
o
11. dubna 2016        108 / 139
Přímé adresování
■ každý prvek reprezentované množiny prvků má přiřazen klíč vybraný z univerza U — {0,1,..., m — 1}
■ žádné dva prvky nemají přiřazený stejný klíč
■ pole T[0.. .m - 1]
• každý slot (pozice) v T odpovídá jednomu klíči z U
• když reprezentovaná množina obsahuje prvek x s klíčem k, tak T [k] obsahuje ukazatel na x
• v opačném případě je T[k] prázdné (Nil)
■ složitost operací je konstantní
11. dubna 2016
Přímé adresování - schéma
Výhody a nevýhody přímého adresování
výhody
■ konstantní složitost všech operací
■ jednoduchá implementace
nevýhody
■ v případě, že univerzum ř7 je veliké, tak uchovávání tabulky velikosti univerza je neefektivní resp. nemožné
■ v případě, že množina aktuálně uložených klíčů je malá ve srovnání s velikostí univerza, tak větší část paměti alokované pro tabulku T je nevyužitá
■ problém objektů se stejným klíčem
o
11. dubna 2016        111 / 139
Hašovaní
Přímé adresování
Hašovací tabulka
v případě, že množina aktuálně uložených klíčů K je výrazně menší než U, využívá hašovací tabulka výrazně méně paměti, než tabulka s přímým přístupem
potřebný prostor se dá redukovat až na Q(\K\)
složitost operací zůstává konstantní avšak v očekávaném (a ne v nejhorším) případě
přímé adresování   prvek x s klíčem k uloživ tabulce na pozici T[k] hašování prvek x s klíčem k uloživ tabulce na pozici T[h(k)]
■ h je funkce h : U —> {0,1,..., m — 1}
■ h se nazývá hašovací funkce
o
11. dubna 2016        112 / 139
Hašovaní
Přímé adresování
Hašovací tabulka - problémy k řešení
1. řešení kolizí
kolize « dva anebo více klíčů zahašujeme na stejnou pozici
pro x 7^ y je h(x) — h(y), x a y mají stejný otisk
■ zřetězené hašovaní (chaining)
■ otevřená adresace (open adressing)
2. výběr hašovací funkce
■ minimalizovat počet kolizí
■ efektivní výpočet funkce
o
11. dubna 2016        113 / 139
Zřetězené hasovani
■ každá položka tabulky obsahuje (ukazatel na) seznam prvků zahašovaných na stejnou pozici
■ seznam je prázdný právě když žádný prvek nebyl zahašovaný na danou pozici
■ vkládání prvku x do hašovací tabulky T se realizuje jako přidání prvku na začátek seznamu T[h(x.key)]
■ prvek x vyhledáváme v seznamu T[h(x.key)]
■ prvek x odstraníme vymazáním ze seznamu T[h(x.key)]
o
11. dubna 2016        114 / 139
Hašovaní
Zřetězené hašovaní
0
11. dubna 2016        115 / 139
Hašovaní
Zřetězené hašovaní
Zřetězené hašovaní - složitost
složitost v nejhorším případě
Insert konstantní (za předpokladu, že vkládaný prvek není v tabulce)
Search úměrná délce seznamu; v nejhorším případě 0(n), kde n je počet prvků uložených v tabulce
Delete (asymptoticky) stejná jako složitost Search (za předpokladu dvousměrného seznamu)
složitost v průměrném případě
záleží od výběru hašovací funkce
o
11. dubna 2016        116 / 139
Zřetězené hašování - průměrná složitost
předpokládáme, že hašovací funkce je jednoduchá uniformní (simple uniform), tj. že pro každý prvek univerza je pravděpodobnost jeho zahašování na kterýkoliv index tabulky stejná (a nezávislá od toho, kam jsou zahašovány zbylé prvky univerza)
složitost operací se vyjadřuje vzhledem k faktoru naplnění (had factor)
pro danou tabulku s m pozicemi, ve které je uložených n prvků, definujeme faktor naplnění a předpisem a — n/m, tj. průměrný počet prvků zahašovaných na stejnou pozici
pro j — 0,1,..., m — 1 nechť rij označuje délku seznamu T[j
pro jednoduchou uniformní hašovací funkci platí, že očekávaná délka
seznamu T
3\ Je
E[rij] — a — n/m
předpokládáme, že výpočet hodnoty funkce má konstantní časovou složitost
o
11. dubna 2016        117 / 139
Hašovaní
Zřetězené hašovaní
Zřetězené hašovaní - průměrná složitost
V hašovací tabulce, ve které jsou kolize řešeny zřetězením a ve které se používá jednoduchá uniformní funkce, má operace neúspěšného vyhledávaní prvku průměrnou časovou složitost 0(1 + a).
V hašovací tabulce, ve které jsou kolize řešeny zřetězením a ve které se používá jednoduchá uniformní funkce, má operace úspěšného vyhledávaní prvku průměrnou časovou složitost 0(1 + a).
■ v případě, že počet pozic v tabulce je proporcionální počtu prvků v tabulce, n — O (m), platí a — n/m — 0{m)/m — 0(1)
■ vyhledávaní prvku má konstantní průměrnou složitost
■ samotné vložení prvku a odstranění prvku ze seznamu má konstantní složitost
■ všechny operace mají za daných předpokladů konstantní průměrnou složitost
bm 11. dubna 2016        118 / 139
Výběr hašovací funkce
jak vybrat dobrou hašovací funkci?
■ funkce by měla mít vlastnosti jednoduché uniformní funkce: každý klíč je zahašován na všechny pozice se stejnou pravděpodobností
■ v praxi je těžké ověřit podmínku uniformity, protože nepoznáme rozložení klíčů (a navíc jsou často na sobě závislé)
■ v praxi využíváme při volbě hašovací funkce znalosti rozložení klíčů s cílem, aby se často společně se vyskytující klíče zahašovali na různé pozice
■ příklad: když klíče jsou vybírány náhodně s uniformním rozdělením z intervalu (0,1), tak hašovací funkce h{k) — \ k • m\ je jednoduchou uniformní funkcí
o
11. dubna 2016        119 / 139
Hašovaní
Hašovací funkce
Klíče jako přirozené čísla
■ většina hašovacích funkcí je navržená pro univerzum - množinu přirozených čísel N
■ když klíče nejsou přirozená čísla, můžeme je interpretovat jako přirozená čísla použitím vhodného kódování
příklad
• znakový řetězec interpretujeme jako číslo (ve vhodně zvolené číselné soustavě)
• řetězec CLRS
• ASCII hodnoty: C = 67, L = 76, R = 82, S = 83
• máme 128 ASCI hodnot, volíme proto číselnou soustavu se základem 128
• CLRS interpretujeme jako (67 • 1283) + (76 • 1282) + (82 • 1281) + (83 • 128°)
o
11. dubna 2016        120 / 139
Hašovací funkce - metoda dělení
h(k) — k   mod m
příklad m = 20, k = 91       h(fc) = 11 výhody rychlost
nevýhody špatné chování pro některé m
• pro m — 2P je hodnota h[k) vždy p nejpravějších bitů z fc
• když   je znakový řetězec interpretovaný při základě 2P, tak hodnota
m — 2P — 1 není vhodná, protože po permutaci řetězce se hodnota hašovací funkce nezmění
• dobrou volbou pro m je prvočíslo
bm 11. dubna 2016        121 / 139
Hašovaní
Hašovací funkce
Hašovací funkce - metoda binárního násobení
■ předpoklad: univerzum je U množina binárních čísel délky w
■ předpoklad: velikost m tabulky je mocninou dvojky, m — 2p
■ cílem je zahašovat ^-bitové čísla na p-bitové čísla
■ zvolíme libovolnou konstantu A, 0 < A < 1
h>A(k) — \_m (k A   mod 1)J
postup výpočtu
□ vynásob klíč k konstantou A b ze součinu vezmi desetinnou část výsledek vynásob číslem m a ze součinu vezmi celou část
o
11. dubna 2016        122 / 139
hA(k) =
m (k A   mod 1)J
■ zvolíme A tvaru s/2w
■ vynásobíme čísla kas
■ výsledkem násobení je 2w bitové číslo, kde r\ je celočíselná část součinu k A a ro je desetinná část součinu (viz obrázek)
■ pro další výpočet potřebujeme pouze ro
■ potřebujeme celou část součinu čísel ro a m
■ vzhledem k tomu, ze m — 2P, násobení znamená posun o p bitů doleva
■ ve skutečnosti nemusíme vůbec násobit a stačí vzít p nejvýznamnějších bitů čísla ro
w bitů
r~ ^
x I       s = A.2W I
ri
vezmi p nejlevějších bitů
11. dubna 2016        123 / 13
Hašovaní
Hašovací funkce
Metoda binárního násobení - příklad
■ w = 5, m = 8, w = 3, tj. hašujeme 5 bitové čísla, velikost tabulky je 8 = 23 a chceme hašovat na 3 bitové čísla
■ hašujeme klíč k — 21
■ vybíráme konstantu A tvaru s/2w a takovou, aby 0 < A < 1 - proto musí platit 0 < s < 25, vybereme s = 13      A = 13/32
výpočet hA(k) podle vzorce — Lm     ^- mo(i 1)J
• kA = 21- 13/32 = 8^|
• kA mod 1 = 17/32
• m(kA mod 1) = 8 • 17/32 4|
• lm(kA mod 1)J = 4 = hA(k)
implementace
• fcs = 21 • 13 = 273 = 8 • 25 + 17
• r\ — 8,ro = 17; bitový zápis ro je 10001
• vezmeme p = 3 nejvýznamnější bity ro, tj. 100 (4 v desítkové soustavě)
• hA(k) = 4
WSĚ 11. dubna 2016        124 / 139
Hašovaní
Univerzální hašování
Univerzální hašování
scénář ani nejlepší hašovací funkce negarantuje dobré chování hašování v případě, že klíče určené k zahašování jsou vybrány tím nejhorším možným způsobem (můžeme si představit útočníka, který pozná náš hašovací program a hašovací funkci a na základě toho dokáže vybrat takové klíče, které se zahašují na stejnou pozici, viz analogii s výběrem pivota pro Quicksort)
řešení při každém použití hašovacího programu vybereme náhodně jinou hašovací funkci
(když útočník neví, jaká hašovací funkce bude vybrána, nemůže záměrně vybírat vstupy, které povedou k špatnému chování)
výběr funkce samotný fakt náhodného výběru funkce ještě negarantuje efektivitu hašování; je potřebné vybírat z vhodných kandidátů
o
11. dubna 2016        125 / 139
Univerzální hašování
Definice 4
Nechi T-L je konečná množina hašovacích funkcí, které mapují univerzum klíčů U na m pozic. T-L je univerzální množinou hašovacích funkcí právě když pro každou dvojici klíčů k,l £ U, k ^ l, je počet hašovacích funkcí h £ %, pro které h(k) — h(l), nejvýše \H\/m.
Věta 5
Předpokládejme, že hašovací funkce, náhodně vybraná z univerzální množiny hašovacích funkcí, je použita pro za hašovánín klíčů do tabulky s m pozicemi. Pak pro klíč k platí, že když
• k není v tabulce, tak očekávaná délka seznamu, do kterého se zahašuje k, je nejvýše a — n/m
• k je v tabulce, tak očekávaná délka seznamu, který obsahuje k, je nejvýše < 1 + a.
o
11. dubna 2016        126 / 139
Hašovaní
Univerzální hašování
Univerzální hašování - složitost
Důsledek 6
Libovolná posloupnost n operací Insert, Search a Delete, z nichž nejvýše 0(m) operací je typu Insert, má očekávanou časovou složitost @{n) za předpokladu použití zřetězeného hašování, univerzální množiny hašovacích funkcí a tabulky s m pozicemi.
Důsledek 7
Použitím univerzálního hašování a řešení kolizí řetězením v tabulce s m pozicemi zabere očekávaný čas @{n) jakákoliv posloupnost n operacíInsert, Search a Delete, která obsahuje O(m) operacíInsert.
o
11. dubna 2016        127 / 139
Hašovaní
Univerzální hašování
Konstrukce univerzální množiny hašovacích funkcí
příklad univerzálního hašování
■ zvolíme prvočíslo p takové, že žádný klíč není větší než p
■ pro libovolná čísla a E {1,2, ...p—1} a b E {0,1,.. .p — 1} definujeme hašovací funkci předpisem
hab(k) — {{ak + b)   mod p)   mod m)
■ množina funkcí
T-tpm = {hab\a E {1, 2,... p — 1}, b E {0,1,.. .p - 1}
je univerzálni množinou hašovacích funkcí
■ výběr prvočísla umožňuje efektivní implementaci operací mod
přesné důkazy tvrzení jako i další podrobnosti týkající se univerzálního hašovaní jsou v literatuře, např v monografii T. Cormen, Ch. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Third Edition. MIT Press, 2009
bm 11. dubna 2016        128 / 139
Hašovaní
Otevřená adresace
Otevřená adresace
■ všechny klíče ukládáme přímo do tabulky, počet klíčů nemůže přesáhnout velikost tabulky
■ při vyhledávání se systematicky zkoumají pozice tabulky, dokud není nalezen hledaný klíč nebo není jasné, že v tabulce není
■ nepotřebujeme seznamy a ukazatele, místo nich se počítá sekvence pozic v tabulce, které mají být prozkoumány (tzv. sondování)
o
11. dubna 2016        129 / 139
Hašovaní
Otevřená adresace
Otevřená adresace - vyhledávání
■ hašovací funkce je typu h : U x {0,1,..., m — 1} —>► {0,1,..., m — 1}
■ pro každý klíč potřebujeme posloupnost (h(k, 0), h(k, 1),... h(k, m — 1)), která je permutací posloupnosti (0,1,..., m — 1)
■ každá pozice tabulky obsahuje buď klíč, anebo hodnotu Níl
■ při hledání klíče k
• proměnná zje rovna pořadovému číslu testu, iniciální hodnota i je 0
• vypočítáme hodnotu h(k,i) a testujeme obsah pozice h(k,i)
• když pozice h(k,i) obsahuje klíč k, vyhledávání je úspěšné
• když pozice h(k,i) obsahuje hodnotu Nil, vyhledávání je neúspěšné (tabulka neobsahuje klíč k)
• když pozice h(k,i) obsahuje neprázdnou hodnotu různou od k, tak zvýšíme pořadové číslo testu a vypočítáme novou pozici v tabulce jako funkci k a pořadového čísla testu a klíč hledáme pomocí této nové hašovací funkce
o
11. dubna 2016       130 / 139
Otevřená adresace - vkládání
■ analogicky jako při vyhledávání najdeme volnou pozici v tabulce
■ vkládání skončí úspěchem když je nalezena volná pozice, na kterou se klíč vloží
■ když počet testů dosáhne m, tak vkládání končí neúspěchem
o
11. dubna 2016        131 / 13
Hašovaní
Otevřená adresace
Otevřená adresace - odstranění klíče
■ vyhledáme klíč k v tabulce, nechť se nalézá na pozici j
■ může nastat situace, že po odstranění klíče k budeme v tabulce vyhledávat klíč k', který je v tabulce uložen) a v průběhu jeho vyhledávání budeme zkoumat i pozici j
■ když by jsme na pozici j vložili hodnotu Nil, tak by jsme při následném vyhledávání klíče k' dostali nesprávný výsledek
řešení
■ místo hodnoty Nil použijeme speciální hodnotu Deleted
■ operace Insert považuje pozici s hodnotou Deleted za prázdnou
■ operace Search považuje pozici s hodnotou Deleted za obsazenou, ale obsahující jinou hodnotu než hledaný klíč
o
11. dubna 2016        132 / 139
Hašovaní
Otevřená adresace
Otevřená adresace - výpočet sekvence sond
nejčastěji se používají k výpočtu sekvence sond tři techniky
■ lineární adresace (linear probing)
■ kvadratická adresace (quadratic probing
■ dvojité hašování (double hashing)
o
11. dubna 2016        133 / 139
Otevřená adresace - lineární
využívá pomocnou hašovací funkci h! : U —> {0,1,..., m — 1}
i) = (h!(k) + i)   mod m
pro daný klíč je nejdříve prozkoumána pozice T[h'(k)}, pak pozice T[tí(k) + 1].....T[m - 1] a pak zase od T[0] až k T[V(fc) - 1]
problémem je tzv. primární shlukování, které může výrazně zvýšit složitost operací
o
11. dubna 2016        134 / 139
Hašovaní
Otevřená adresace
Otevřená adresace - kvadratická
využívá pomocnou hašovací funkci h' : U —> {0,1,..., m — 1} a pomocné konstanty ci,    ^ 0
i) = (h'(k) + cii + c2í2)   mod m
■ pro daný klíč je nejdříve prozkoumána pozice T[h'{k)}, dále pak pozice posunuta o offset závislý kvadratickým způsobem na pořadí sondy
■ kvadratická adresace je obvykle lepší než lineární
■ problémem je vhodný výběr konstant c\ a c2 a velikosti tabulky m
■ když dva klíče jsou primárně zahašovány na stejnou pozici protože h!{k\) — h'{k2)i tak mají stejnou celou posloupnost sond - tzv. sekundární shlukování
o
11. dubna 2016        135 / 139
Hašovaní
Otevřená adresace
Otevřená adresace - dvojité hašování
využívá dvě pomocné hašovací funkce /ii,/i2
h(k,i) — (hi(k) Jrih2{k))   mod m
■ pro daný klíč je nejdříve prozkoumána pozice T[hi(k)], následující pozice je posunuta o offset Ii2(k) mod m
■ hodnota h,2(k) musí být nesoudělná s velikostí hašovací tabulky m, aby byla prohledána celá tabulka
■ vhodnou volbou je vzít m jako mocninu 2 a navrhnout I12 tak, že výsledkem bude vždy liché číslo, nebo
■ zvolit m jako prvočíslo a navrhnout /12 tak, že výsledkem bude vždy kladné číslo < m
■ dvojité hašování je lepší než kvadratické, protože generuje 0(m2) posloupností sond místo O(m) jako kvadratická adresace
bm 11. dubna 2016       136 / 139
Otevřená adresace - složitost
Věta 8
Pro hašovací tabulku s otevřenou adresaci s faktorem naplnění a = n j m < 1 je očekávaný počet sond při neúspěšném hledání nejvýše 1/(1 — a) a to za předpokladu uniformního basování.
Věta 9
Pro hašovací tabulku s otevřenou adresaci s faktorem naplnění a — n j m < 1 je očekávaný počet sond při úspěšném hledání nejvýše ^ ln       a to za předpokladu uniformního basování.
uniformní hašováníje takové, že každý klíč má jako posloupnost sond se stejnou pravděpodobností libovolnou z m\ permutací (0,1,..., m — 1
11. dubna 2016        137 / 13
Hašovaní
Kukaččí hašovaní
Kukaččí hašovaní (Cuckoo hashing)
■ pro hašovaní se používají dvě tabulky velkosti m a dvě hašovací funkce
/ii, Yt2 : U —> {0,1,... m — 1}
■ každý klíč   je zahašovaný buď na pozici h\{k) v první tabulce, anebo na pozici /i2(fc) v druhé tabulce
■ hledání klíče má konstantní složitost, protože stačí otestovat dvě pozice
■ odstranění klíče má konstantní složitost, analogicky jako jeho hledání
■ při vkládání nového klíče k se použije hladová strategie: nejdříve se pokusíme vložit klíč k na pozici h\{k)
■ když je pozice /ii(/c)obsazena, tak klíč y uložený na pozici h\{k) přesuneme do druhé tabulky na jeho alternativní pozici /^(y)
■ proces opakujeme a přepínáme se mezi tabulkami dokud nenajdeme volnou pozici, anebo se proces zacyklí
R. Pagh, F. Rodler: Cuckoo hashing. Journal ofAlgorithms 51 (2004) 122 - 144
o
11. dubna 2016        138 / 139
Hašovaní
Dokonalé hašovaní
Dokonalé hašovaní (Perfect hashing)
■ hašovaní, které má konstantní složitost i v nej horším případě
■ předpokladem je statická množina klíčů
■ využívá dvě úrovně hašovaní
první úroveň
v podstatě stejná, jako zřetězené hašovaní druhá úroveň
■ místo seznamů použijeme sekundární hašovací tabulky Sj s asociovanou hašovací funkcí hj, přičemž vhodným výběrem můžeme zajistit, aby na druhé úrovni nebyly žádné kolize
■ velikost rrij tabulky Sj je kvadratická vůči počtu klíčů zahašovaných na pozici j
■ hašovací funkce na první úrovni se vybírá z univerzální množiny hašovacích funkcí T-Lpm, na druhé úrovni z univerzální množiny T-Lprn-
o
11. dubna 2016        139 / 139