Please enable JavaScript.
Coggle requires JavaScript to display documents.
17. Datové struktury založené na stromech (Haldy (binomiální halda…
17. Datové struktury založené na stromech
BVS
vyvážený BVS
B-stromy
řádu n (max počet synů - ukazatelů 1 vrcholu)
uzly min n/2 a max n potomků
kořen max n potomků (min - neomezeně)
všechny listy na stejné úrovni
využití
apliakce, kde není celá struktura v RAM, ale v sekundární paměti (HDD), např. databáze, snaha o minimalizaci počtu přístupů - pomalá paměť
NTFS (souborové systémy), databáze,...
= vyvážený vyhledávací strom, kde vyhledávání a odstranění v O(logn)
vlastnosti
každý uzel - klíče v uspoř. a neklesajícím pořadí
vnitřní uzel - ukazatele na syny
klíče v uzlech odděluji intervaly možných hodnot v podstromech
všechny listy stejná hloubka
výška O(logn)
minimalizace průchodu stromem
vnitřní uzel s n klíči - n+1 následníků
stupeň t >= 2
každý uzel min t-1 klíčů
max 2t-1 klíčů a 2t následníků
plný uzel - 2t následníků
arita 2t /následníci)
n >= 1 klíčů a min stupněm t >= 2: hloubka mx logt((n+1)/2)
2-3-4 strom
min. stupeň 2, 2-4 následníci
operace
vyhledávání O(tlogt(n)) - vrací (y, i)
přidání klíče (netvoříme nový list - dělíme)
vytvoření stromu O(1)
dělení - uzlu, kořene
optimalizace (dělení plných uzlů, při 1 průchodu)
zápis/čtení z disku - O(h)
mazání - nahradíme následníkem, VŽDY v listu
Č-Č stromy
vyhledávání, vkládání, mazání
= jako BVS
vložení/odebrání - může porušit pravidla
vyvažování
přebarvování
rotace
zachovává vlastnosti BVS, složitost O(1)
O(logn)
vložení
stejně jako BVS
obarvíme na červeno
odspodu kontrolujeme vlastnosti BVS, případně přebarvíme
mazání
podobně jako BVS
červený - nic, černý - přesouváme červnou nahoru, obnova vlast.
= vyvážený BVS, každý uzel obarven č/č barvou (vyvažování)
podmínky
stejný počet černých
kořen - černý
cíl - min. černá hloubka
červený uzel - černí následníci
uzel: key, color, l, r, p
výška x černá výška
hloubka log2(n+1)
př.: AVL stromy, B stromy, Č-Č stromy
složitost úměrná hloubce
operace
přidání uzlu
pamatuji si uzel, v němž procházení skončilo - pod něj nový uzel
O(log n) - při průběžném vyvažování
jako vyhledávání
mazání uzlu
potřeba správně navázat následníky
lze O(logn)
a) nemá násl. odstraň
b) 1 syn - nahraď jím otce
c) 2 synové (násl. / předchůdce)
vyhledávání uzlu s hodnotou X
porovnání <= výška stromu
kořen --> listy - porovnáváme uzel s X
vyvážené BVS - log. složitost
nalezení / neexistuje následník - hodnota není ve stromě
= binární strom nad úplně uspořádanou množinou (klíčů) (K, <=), pro každý jeho podstrom platí:
hodnoty uzlů v levém podstromu t jsou menší než hodnota v kořenu t
v pravém naopak
každý uzel 0-2 potomků
využívá ukazatele (left, right, p)
následník, předchůdce uzlu
Haldy
využití: vyhledávání, heapsort
implementace
opměrně jednoduchý alg.
nalezení max/min v konstantním čase
snadná realizace v poli
odebrání min k kořene a přidání kového prvku v log. čase
nový prvek - na konec -> probublání na správnou pozici
mazání vrcholu
smažu kořen + nahradím posledním prvkem + probublám
binomiální halda
navíc rychlé spojení 2 hald
použití
kde je třeba rychle MIN a MERGE
Dijkstra (nejkratší cesta)
kořenový strom s lib. větvením a s ohodnocenými uzly
řádu 0 - samostatný vrchol
strom řádu k může být složen ze 2 stromů řádu k-1 - 1 jako nejlevější potomek 2. - konstantní čas
řádu k - kořen + potomci jsou binom. haldy řádu k-1,...,0
binární halda = bin. strom, uzly ohodnoceny
délky větví se liší max o 1 (h / h-1) + zarovnány vlevo
hodnoty uzlů ve větvi - sestupně (min) / vzestupně (max)
merge - vytvoří nové pole, nakopíruje, reheap
operace, složitost, implementace, příklady použití
Stromové datové struktury
kořenové stromy
u předkem v, následníkem
hloubka vrcholu
společný rodič --> dourozenci
výška stromu (největší hloubka)
hrana z u do v --> u rodič, v syn
list / vnitřní vrcholy
orientovaný je kořenový, když má kořen vstup. stupeň 0 a ostatní 1
isomorfismus kořenových stromů (kořen na kořen)
= orientovaný strom, má určen význačný vrchol (kořen) - v něm existuje orientovaná cesta do všech vrcholů
n-ární strom (nejvýše n potomků), úplný n-ární (vnitřní - plné + stejná hloubka)
uspořádaný strom
indukovaný podgraf (vymaž vrcholy + zasahující hrany)
binární strom (uspořádaný 2-ární)
podstrom
strom
souvislý graf, který neobsahuje kružnice (po přidání lib. hrany vznikne kružnice)
každé 2 vrcholy spojené právě jednou cestou
alespoň 1 hrana --> min 2 vrcholy stupně 1
n vrcholů --> n-1 hran
orientované - varianta
les
množina navzájem nepropojených stromů
n vrcholů, k komponent --> n-k hran
průchody stromem
inorder
postorder
preorder
B+ strom
klíče pouze v listech
vnitřní uzly - indexy
zřetězení listů - uspořádané klíče