BI-AG1 – Algoritmy a Grafy 1

Okruh 1

Základní pojmy teorie grafů & grafové algoritmy

Definice grafů, procházení do šířky, komponenty, topologické uspořádání, minimální kostra, Dijkstrův algoritmus.

🔵 Co je graf?

Neorientovaný graf G = (V, E) je dvojice, kde V je neprázdná konečná množina vrcholů a E je množina hran – každá hrana je dvouprvková podmnožina V, tedy neuspořádaná dvojice vrcholů {u, v}. Píšeme n = |V|, m = |E|.

Orientovaný graf G = (V, E) má orientované hrany – uspořádané dvojice (u, v). Vrchol u je předchůdce v, vrchol v je následník u.

Proč to tak je? Grafy modelují reálné vztahy: mapy ulic (vrcholy = křižovatky, hrany = ulice), sítě přátel, závislosti modulů při kompilaci, schémata zapojení.

Klíčová terminologie

Stupeň vrcholu deg(v) = počet hran obsahujících v; v orientovaném grafu rozlišujeme vstupní a výstupní stupeň.
Sousedé N(v) = množina vrcholů spojených s v hranou. deg(v) = |N(v)|.
Princip sudosti: Σ deg(v) = 2|E| – každá hrana přispěje ke stupni dvou vrcholů.
Izolovaný vrchol: deg(v) = 0, nemá žádné sousedy.
Regulární graf: všechny vrcholy mají stejný stupeň.

Speciální grafy

Úplný graf Kn: každé dva vrcholy jsou spojeny hranou. |E| = n(n-1)/2.
Bipartitní graf: vrcholy dělíme na dvě množiny A, B; hrany vedou pouze mezi A a B, nikdy uvnitř A nebo B. Úplný bipartitní K_n1,n2 má n1·n2 hran.
Cesta P_n: posloupnost vrcholů v1, v2, …, vn bez opakování.
Kružnice C_n: uzavřená cesta, n ≥ 3.
Klika: podmnožina vrcholů, kde každé dva jsou sousední.

📌 Reprezentace grafu v paměti
Matice sousednosti: A[i][j] = 1 iff {i,j} ∈ E. Paměť O(n²). Find souseda O(1), výpis sousedů O(n).
Seznam sousedů: Pro každý vrchol seznam jeho sousedů. Paměť O(n+m). Výpis sousedů O(deg(v)). Preferovaná reprezentace pro řídké grafy!

🛤️ Sled, cesta, vzdálenost

Sled délky k je sekvence v0, e1, v1, e2, …, ek, vk, kde ei = {vi-1, vi} ∈ E. Hrany i vrcholy se mohou opakovat.
Cesta je sled, kde se neopakují vrcholy (ani hrany).
Vzdálenost d(s, t) = délka nejkratší s-t-cesty (počet hran). Pokud cesta neexistuje, d = ∞.

Klíčové pozorování: Existuje-li sled z u do v, existuje i cesta (zkrácením cyklů).

🌲 Strom, les, kostra

Strom je souvislý acyklický graf. Les je acyklický graf (více komponent stromů). List je vrchol stupně 1.

Charakterizace stromů – pro graf G = (V, E) jsou ekvivalentní:

G je strom (acyklický + souvislý).
Pro každé dva vrcholy existuje právě jedna cesta.
G je souvislý a odebrání libovolné hrany ho odpojí.
G je souvislý a |E| = |V| − 1.

Věta o existenci listů: Každý strom s ≥ 2 vrcholy má alespoň 2 listy. (Důkaz: nejdelší cesta má listové konce.)

Věta o trhání listů: Strom G − v (po odebrání listu) je opět strom.

Kostra grafu G je podgraf K s V(K) = V(G) a K je strom. Existuje iff G je souvislý. Má |V| − 1 hran. Může jich být více (pokud G má kružnice).

🌊 BFS – Prohledávání do šířky

Motivace: Najít nejkratší cestu v neohodnoceném grafu (všechny hrany mají délku 1). Myšlenka: vlnový algoritmus – postupně „zaplavujeme" vrcholy ve vzdálenosti 0, 1, 2, …

Vstup / Výstup BFS
Vstup: Graf G = (V, E), startovní vrchol s.
Výstup: Pole vzdáleností D (D[v] = délka nejkratší s-v-cesty), pole předchůdců P (P[v] = předchůdce v na nejkratší cestě).
    

Algoritmus BFS(G, s):
(1)  Pro každý vrchol v: stav[v] = nenalezený, D[v] = P[v] = undef
(2)  Q = fronta s jediným vrcholem s
(3)  stav[s] = otevřený, D[s] = 0, P[s] = ⊥
(4)  Dokud Q neprázdná:
(5)    v = vyjmi z Q první prvek
(6)    Pro každého souseda w vrcholu v:
(7)      Pokud stav[w] = nenalezený:
(8)        stav[w] = otevřený
(9)        D[w] = D[v] + 1
(10)       P[w] = v
(11)       přidej w na konec Q
(12)   stav[v] = uzavřený
(13) Vrať (D, P)

Klíčové vlastnosti BFS

Stavy vrcholů: nenalezený → otevřený (v Q) → uzavřený. Každý vrchol přejde nejvýše jednou.
BFS hladiny H_i: H₀ = {s}, H_i = vrcholy otevřené ve fázi F_i-1. Vrcholy v H_i mají vzdálenost i od s.
Správnost: Po skončení D[v] = d(s,v) pro všechny dosažitelné vrcholy. Klíčový argument: dva sousední vrcholy leží v sousedních hladinách – nemohou přeskočit.
Časová složitost: O(|V| + |E|) při reprezentaci seznamem sousedů. Každý vrchol vyjmeme z Q jednou, každou hranu procházíme dvakrát (jednou z každé strany).

�� Rekonstrukce nejkratší cesty

      Po skončení BFS: začni z cílového vrcholu t a sleduj P[t] → P[P[t]] → … → s. Výsledná cesta je nejkratší.

BFS pro celý graf (zjišťování komponent): Opakovaně spouštíme BFS z nových nenalezených vrcholů. Komplexita celku zůstává O(|V| + |E|).

BFS na orientovaném grafu: Totéž, ale procházíme pouze hrany ve směru (následníky, ne předchůdce).

🧩 Souvislost a komponenty

Souvislý graf: pro každé u, v ∈ V existuje u-v-cesta.
Souvislá komponenta: maximální (v inkluzi) souvislý podgraf. Binární relace „existuje cesta" je ekvivalence – třídy jsou komponenty.

Graf je souvislý právě tehdy, když má jedinou komponentu. BFS spuštěný z vrcholu s uzavře přesně komponentu obsahující s.

Slabá a silná souvislost orientovaných grafů

Slabě souvislý: symetrizace (ignorování orientace hran) je souvislá.
Silně souvislý: pro každé u, v existuje orient. cesta z u do v i z v do u. Silnou souvislost lze otestovat pomocí DFS/BFS (viz BI-AG2).

DFS – Prohledávání do hloubky

Alternativa k BFS, přirozeně rekurzivní. Neudává nejkratší cesty, ale je elegantní pro detekci cyklů a topologické uspořádání.

DFS(v):
(1) Pokud stav[v] != nenalezený: return
(2) stav[v] = otevřený
(3) Pro každého souseda u vrcholu v:
(4)   DFS(u)
(5) stav[v] = uzavřený

Časová složitost DFS: O(|V| + |E|). Používá zásobník (rekurzi nebo explicitní zásobník).

📋 Topologické uspořádání (TopSort)

Topologické uspořádání (TU) orientovaného grafu G = (V, E) je seřazení vrcholů V = {v1, …, vn} tak, že pro každou hranu (vi, vj) ∈ E platí i < j. Všechny šipky vedou „zleva doprava".

Motivace: Nástroj make – pořadí kompilace modulů podle závislostí. Pokud A závisí na B, musíme B zkompilovat dříve než A.

Existence TU: Orientovaný graf má TU právě tehdy, když je acyklický (DAG – Directed Acyclic Graph). Pokud obsahuje orientovanou kružnici, TU neexistuje.

Zdroj: vrchol s nulovým vstupním stupněm (žádná hrana nevede dovnitř). Stok: vrchol s nulovým výstupním stupněm.

Věta: Každý DAG obsahuje alespoň jeden zdroj a jeden stok. (Důkaz sporem: bez zdroje jdeme zpět po hranách, nutně narazíme na cyklus.)

Algoritmus TopSort (Kahnův algoritmus)

TopSort(G = orientovaný graf):
(1) Spočítej vstupní stupně δ[v] pro všechny vrcholy
(2) Q = fronta všech zdrojů (δ[v] = 0)
(3) Dokud Q neprázdná:
(4)   z = vyjmi z Q
(5)   Vypiš z
(6)   Pro každou hranu (z, w):
(7)     δ[w]--
(8)     Pokud δ[w] = 0: přidej w do Q
(9) Pokud nebyly zpracovány všechny vrcholy: CYKLUS

✅ Správnost TopSort

      Vrchol w je zařazen do fronty, až když jsou všichni jeho předchůdci zpracováni (δ[w] = 0). Pokud po vyprázdnění fronty zbývají vrcholy – mají všechny nenulový vstupní stupeň → tvoří cyklus.

Časová složitost: O(|V| + |E|) – inicializace O(E), vkládání do Q O(V), zpracování hran O(E).

Alternativa přes DFS: TU = vrcholy v pořadí klesajícího uzavírací doby DFS.

🌳 Minimální kostra (MST)

Hranově ohodnocený graf: Každé hraně e přiřazena váha w(e) ∈ ℝ. Váha podgrafu = součet vah hran.
Minimální kostra (MST – Minimum Spanning Tree): kostra s nejmenší celkovou váhou hran.

Motivace: Propojit síťové uzly s minimálním celkovým kabelem; silniční sítě; návrh elektrických obvodů.

Klíčový nástroj: Elementární řez

Elementární řez R určený podmnožinou A ⊆ V: množina všech hran s jedním vrcholem v A a druhým v V\A.

🔑 Lemma o řezech

      Nechť R je elementární řez a e je nejlehčí hrana v R (váha unikátní). Pak e leží v každé minimální kostře. Intuice: pokud by e v kostře nebyla, může ji nahradit a váhu snížit.

Jarníkův (Primův) algoritmus

Myšlenka (hladový přístup): Začni s jedním vrcholem, postupně přidávej nejlehčí hranu vedoucí z dosud vytvořeného stromu do zbytku grafu.

MinKostraJarník(G, w):
(1) T = {libovolný vrchol v0}
(2) Dokud T neobsahuje všechny vrcholy:
(3)   Přidej nejlehčí hranu {u,v}, u ∈ T, v ∉ T, do T + vrchol v
(4) Vrať T

Proč funguje: V každém kroku přidáváme nejlehčí hranu elementárního řezu (T vs. V\T) → vždy leží v MST. Indukčně: celý strom je podgraf MST → je MST.

Implementace	Časová složitost
Naivní (průchod všech hran)	O(\|V\|·\|E\|)
S binární haldou (jako Dijkstra)	O(\|E\| log \|V\|)
S Fibonacciho haldou	O(\|E\| + \|V\| log \|V\|)

Jarník s binární haldou: Udržuj haldu vrcholů s klíčem d[v] = váha nejlehčí hrany z T do v. Při přidání vrcholu přepoč klíče sousedů (DecreaseKey). Složitost: O(|E| log |V|).

Kruskalův algoritmus

Myšlenka: Seřaď hrany vzestupně, postupně přidávej – přeskakuj hrany, které by vytvořily cyklus.

MinKostraKruskal(G, w):
(1) Seřaď hrany: w(e1) ≤ w(e2) ≤ ... ≤ w(em)
(2) T = (V, ∅)  // les izolovaných vrcholů
(3) U = Init(V) // Union-Find struktura
(4) Pro i = 1, ..., m:
(5)   u, v = krajní vrcholy ei
(6)   Pokud Find(u) ≠ Find(v):
(7)     E(T) += {ei}
(8)     Union(u, v)
(9) Vrať T

Proč funguje: Každá přidaná hrana je nejlehčí v elementárním řezu oddělujícím její komponentu od zbytku – leží v MST.

Union-Find (Disjoint Set Union): Struktura pro správu disjunktních množin. Operace Init, Find, Union. Keříková implementace: Find = jdi do kořene, Union = připoj mělčí pod hlubší. Hloubka keříku ≤ log n → Find/Union trvá O(log n). Celková složitost Kruskala: O(|E| log |V|).

⚡ Dijkstrův algoritmus – nejkratší cesty v ohodnoceném grafu

Problém: Orientovaný graf G s kladnými délkami hran ℓ : E → ℝ⁺, startovní vrchol v0. Najdi nejkratší vzdálenosti (nejmenší součet délek hran na cestě) z v0 do všech ostatních vrcholů.

Motivace: GPS navigace, routování síťových paketů, sociální sítě (6 stupňů odloučení).

Proč nestačí BFS? BFS předpokládá jednotkové délky. U ohodnocených hran je nejkratší cesta hledána podle součtu vah, ne počtu hran.

Klíčová myšlenka (relaxace): Udržuj pro každý vrchol w odhad h[w] vzdálenosti od v0. Při uzavření vrcholu v aktualizuj odhady sousedů: h[w] = min(h[w], h[v] + ℓ(v,w)).

Dijkstra(G, ℓ, v0):
(1) Pro všechny v: h[v] = +∞, stav[v] = nenalezený, P[v] = ⊥
(2) h[v0] = 0; stav[v0] = otevřený
(3) Dokud existují otevřené vrcholy:
(4)   v = otevřený vrchol s nejmenším h[v]
(5)   Pro každého následníka w vrcholu v:  // relaxace v
(6)     Pokud h[w] > h[v] + ℓ(v,w):
(7)       h[w] = h[v] + ℓ(v,w)
(8)       stav[w] = otevřený
(9)       P[w] = v
(10)  stav[v] = uzavřený
(11) Vrať (h, P)

Čtyři klíčové vlastnosti (invarianty) Dijkstry

Vlastnost O (ohodnocení): h[v] vždy odpovídá délce nějakého sledu z v0 do v; nikdy neroste.
Vlastnost M (monotonie): h[uzavřený] ≤ h[otevřený]. Uzavřený vrchol se neotevře znovu – proto kladné délky hran jsou nutné!
Vlastnost D (dosažitelnost): Po skončení jsou uzavřené právě dosažitelné vrcholy.
Vlastnost V (vzdálenost): Po skončení h[v] = d(v0, v) pro všechny v.

⚠️ Omezení Dijkstry

      Dijkstra nefunguje pro záporné délky hran! Záporná hrana by mohla zneplatnit už uzavřený vrchol. Pro záporné hrany (bez záporných cyklů) se používá Bellman-Fordův algoritmus (složitost O(V·E)).

Implementace	Celková složitost
Pole (hledáme min ručně)	O(\|V\|²)
Binární halda (ExtractMin + DecreaseKey)	O(\|E\| log \|V\|)
Fibonacciho halda	O(\|E\| + \|V\| log \|V\|)

Dijkstra s binární haldou: Vlož všechny vrcholy do haldy s klíčem h. ExtractMin vybere v s nejmenším h. DecreaseKey aktualizuje klíče sousedů. O(|V|) ExtractMin + O(|E|) DecreaseKey = O(|E| log |V|).

Vztah k Jarníkovi: Oba algoritmy jsou velmi podobné! Jarník přidává nejlehčí hranu do stromu; Dijkstra přidává nejbližší vrchol podle kumulativní vzdálenosti. Implementace pomocí haldy je identická, liší se jen klíč.

📝 Shrnutí Okruhu 1

Graf = (V, E); neorientovaný má neuspořádané hrany, orientovaný uspořádané. Strom = acyklický + souvislý, |E| = |V|-1.
BFS hledá nejkratší cesty v neohodnoceném grafu v čase O(V+E). Hladiny = vzdálenosti od startu.
TopSort existuje iff G je DAG; Kahnův algoritmus odebírá zdroje v čase O(V+E).
MST: Jarník (Prim) i Kruskal dávají O(E log V) pomocí haldy resp. Union-Find. Oba jsou hladové algoritmy korektní díky lemmatu o řezech.
Dijkstra: nejkratší cesty v ohodnoceném grafu s kladnými délkami; O(E log V) s binární haldou. Relaxace = aktualizace odhadu vzdálenosti.

❓ Kontrolní otázky ke státnicím (Okruh 1)

Proč BFS vždy nalezne nejkratší cestu v neohodnoceném grafu?

BFS zpracovává vrcholy v pořadí vzrůstající vzdálenosti od startu (hladiny). Dva sousední vrcholy leží vždy v sousedních hladinách – nemohou přeskočit hladinu. Pokud by existovala kratší cesta do vrcholu v, musel by vrchol přijít dříve do fronty – spor s tím, jak je fronta plněna.

Proč Dijkstrův algoritmus nefunguje pro záporné hrany?

Dijkstra spoléhá na invariant monotonie: h[uzavřený] ≤ h[otevřený]. Záporná hrana může snížit odhad uzavřeného vrcholu pod jeho uzavírací hodnotu, čímž by byl výsledek nekorektní. Pro záporné hrany bez záporného cyklu použijeme Bellman-Ford.

Jak Kruskalův algoritmus detekuje, zda hrana vytvoří cyklus?

Pomocí Union-Find struktury. Pokud Find(u) = Find(v), vrcholy u a v jsou ve stejné komponentě → přidání hrany by vytvořilo cyklus. Pokud Find(u) ≠ Find(v), hrana komponenty propojí (Union) a je přidána do kostry.

Co je topologické uspořádání a kdy existuje?

TU je seřazení vrcholů tak, aby všechny orientované hrany mířily od nižšího k vyššímu indexu. Existuje právě tehdy, když je graf DAG (acyklický orientovaný graf). Pokud existuje orientovaný cyklus, TU nelze sestavit, protože by cyklu odpovídalo protikladné požadované pořadí.

Jaký je rozdíl mezi Jarníkovým a Kruskalovým algoritmem pro MST?

Jarník (Prim) roste z jednoho vrcholu – vždy přidává nejlehčí hranu z aktuálního stromu do zbytku. Kruskal seřadí všechny hrany a přidává od nejlehčí, přeskakuje hrany, které by vytvořily cyklus. Oba dávají MST, obě implementace jsou O(E log V). Jarník je vhodnější pro husté grafy, Kruskal pro řídké.

Okruh 2

Binární haldy, binomiální haldy, BVS, AVL, hešování

Datové struktury pro efektivní správu dynamických množin: prioritní fronty, vyvážené stromy, rozptylovací tabulky.

🏔️ Binární minimová halda

Binární minimová halda je binární strom splňující:
(1) Tvar haldy: Všechny hladiny jsou plné kromě poslední, která je zaplněna zleva.
(2) Haldové uspořádání: Klíč každého vrcholu ≤ klíče jeho synů.

Důsledek: Kořen vždy obsahuje globální minimum. Na každé cestě z vrcholu do kořene jsou klíče nerostoucí.

Podpora operací a jejich složitosti

Operace	Složitost	Princip
HeapFindMin	O(1)	Vrátí klíč kořene
HeapInsert	O(log n)	Vlož jako nový list, BubbleUp
HeapExtractMin	O(log n)	Odstraň kořen, nahraď posledním listem, BubbleDown
HeapBuild	O(n)	BubbleDown od ⌊n/2⌋ dolů
HeapDecreaseKey	O(log n)	Sniž klíč, BubbleUp

HeapInsert (BubbleUp)

Přidej nový vrchol na první volnou pozici v poslední hladině. Pokud je klíč menší než klíč otce, prohoď je a pokračuj výše – až do kořene nebo do chvíle, kdy haldové uspořádání platí.

HeapInsert(H, k):
  Vlož nový list p s klíčem k
  BubbleUp(H, p)

BubbleUp(H, p):
  Dokud p != kořen:
    o = otec(p)
    Pokud k(o) ≤ k(p): return  // uspořádání platí
    Prohoď k(o) a k(p)
    p = o

HeapExtractMin (BubbleDown)

Prohoď klíč kořene s klíčem posledního listu (H.last). Odstraň poslední list. BubbleDown: opakovaně prohoď klíč vrcholu s menším ze synů, dokud je to potřeba.

HeapExtractMin(H):
  r = H.root, ℓ = H.last
  x = k(r)
  Prohoď k(r) a k(ℓ); odstraň ℓ
  BubbleDown(r)
  return x

BubbleDown(v):
  Dokud v má syny:
    s = syn v s menším klíčem
    Pokud k(v) ≤ k(s): return
    Prohoď k(v) a k(s)
    v = s

HeapBuild v čase O(n)

Naivní přístup: n volání HeapInsert = O(n log n). Lepší: vlož prvky do pole libovolně, pak od ⌊n/2⌋ do 1 volej BubbleDown. Listy (⌈n/2⌉ jich) jsou triviální haldy. Analýza: součet prací BubbleDown přes všechny hladiny = O(n) (geometrická řada Σ i/2ⁱ konverguje).

Reprezentace v poli

Číslujeme vrcholy po hladinách (kořen = 1). Vrchol s indexem i: levý syn = 2i, pravý syn = 2i+1, otec = ⌊i/2⌋. Tím halda = jednoduché pole bez ukazatelů!

Aplikace: HeapSort

HeapBuild(pole) v O(n) + n×ExtractMin v O(n log n) = O(n log n) celkem. Je in-place (výsledky zapisujeme do uvolněné části pole). Nevýhoda: špatná cache lokalita oproti QuickSortu.

📐 Počet hladin haldy

      Halda s n prvky má ⌊log n⌋ + 1 hladin. Proto BubbleUp i BubbleDown trvají O(log n).

🔗 Binomiální halda

Motivace: Binární halda neumí efektivně slučovat dvě haldy. Binomiální halda přidává operaci BHMerge v O(log n).

Binomiální strom B_k řádu k: B₀ = jeden vrchol; B_k vznikne připojením B_k-1 jako nejpravějšího syna kořene B_k-1. Alternativně: kořen má syny B₀, B₁, …, B_k-1.

Vlastnosti B_k: Počet vrcholů = 2^k. Počet hladin = k+1. Stupeň kořene = k. Počet vrcholů na i-té hladině = C(k,i) (binomiální koeficient – proto název).

Binomiální halda (BH) s n prvky je uspořádaná množina binomiálních stromů T1, …, Tℓ, kde:
– Každý strom Ti splňuje haldové uspořádání.
– Každý řád k se vyskytuje nejvýše jednou.
– Strukturu řádů určuje binární zápis čísla n: B_k ∈ BH iff k-tý bit n je 1.

🔢 Analogie s binárním číslem

      n-prvková BH ↔ binární zápis n. BHInsert ↔ přičtení 1 (binárním sčítáním). BHMerge ↔ binární sčítání dvou čísel. Proto BHInsert má amortizovanou složitost O*(1)!

Operace BHMergeTree

Sloučení dvou stromů stejného řádu k → strom řádu k+1 v O(1): kořen s menším klíčem se stane kořenem výsledku, druhý kořen se připojí jako jeho nejpravější syn. Zachovává haldové uspořádání.

Operace BHMerge

Simulujeme binární sčítání čísel a a b: procházíme řády od nejnižšího, slučujeme stromy stejného řádu (přenos), výsledné stromy tvoří novou BH. Časová složitost O(log n).

Operace	BH složitost	Binární halda
Insert	O*(1), O(log n) worst	O(log n)
FindMin	O(1) s ukazatelem	O(1)
ExtractMin	O(log n)	O(log n)
Merge dvou hald	O(log n) ✓	O(n) (HeapBuild)
DecreaseKey	O(log n)	O(log n)
Delete	O(log n)	O(log n)

BHExtractMin

Najdi strom T s minimálním kořenem (O(log n)). Odtrhni kořen T. Synové kořene (stromy B0, B1, …, Bk-1) tvoří novou BH H'. Proveď BHMerge(H, H'). Celkem O(log n).

Paměťová reprezentace

Každý prvek si pamatuje: klíč, ukazatel na otce, ukazatel na levého sourozence, ukazatel na nejpravějšího syna. Stromy jsou uloženy ve spojovém seznamu podle řádu.

🔍 Binární vyhledávací stromy (BVS)

Binární vyhledávací strom (BVS) je binární strom, kde každý vrchol v obsahuje unikátní klíč k(v) a platí:
– Všechny klíče v levém podstromu L(v) jsou < k(v).
– Všechny klíče v pravém podstromu R(v) jsou > k(v).

Klíčová vlastnost: InOrder průchod (Levý podstrom → Kořen → Pravý podstrom) dává vzestupně seřazenou posloupnost.

Operace BVS

Operace	Princip	Složitost
BVSFind(v, x)	Porovnej x s k(v), jdi do L nebo R podstromu	O(h)
BVSMin(v)	Jdi vždy doleva, až na list	O(h)
BVSMax(v)	Jdi vždy doprava	O(h)
BVSPred(v, w)	Max(L(w)) nebo první předek, kam vstoupíme zprava	O(h)
BVSInsert(v, x)	Find → vlož jako list na nalezenou pozici	O(h)
BVSDelete(v, x)	3 případy: list, 1 syn, 2 synové (nahraď následníkem)	O(h)

Kde h = hloubka stromu. V nejlepším případě h = O(log n), v nejhorším (seřazené vkládání) h = O(n).

Mazání vrcholu se dvěma syny

Nachycení u se dvěma syny: Najdi in-order následník w = BVSMin(R(u)). w má nejvýše jednoho syna. Nahraď k(u) klíčem k(w) a odstraň w (případ 1 nebo 2).

Proč nestačí dokonalé vyvážení?

Dokonale vyvážený BVS má h = O(log n), ale udržet ho po každém Insert/Delete je drahé – příkladem jsou střídající se Insert/Delete operace, které nutí přeorganizovat Ω(n) vrcholů v nejhorším případě.

⚖️ AVL stromy – hloubkové vyvážení

Hloubkové vyvážení: Pro každý vrchol v platí |h(L(v)) − h(R(v))| ≤ 1, kde h je hloubka podstromu.
Znaménko vrcholu δ(v) = h(R(v)) − h(L(v)) ∈ {-1, 0, +1}.

✅ Věta o hloubce hloubkově vyváženého stromu

      HV strom s n vrcholy má hloubku Θ(log n). Nejmenší HV strom hloubky h má Ah vrcholů, kde Ah = Ah-1 + Ah-2 + 1 (Fibonacciho růst ≈ φh). Proto h ≤ logφ(n) = O(log n).

Rotace pro obnovení vyváženosti

Rotace mění tvar stromu ale zachovávají vlastnost BVS (InOrder pořadí klíčů).

Rotace	Kdy použít	Výsledek
Jednoduchá doprava (R)	δ(x) = -2, δ(y=ℓ(x)) = -1	δ(x) = δ(y) = 0
Jednoduchá doleva (L)	δ(x) = +2, δ(y=r(x)) = +1	δ(x) = δ(y) = 0
Dvojitá LR	δ(x) = -2, δ(y=ℓ(x)) = +1	Překoření za z=r(y)
Dvojitá RL	δ(x) = +2, δ(y=r(x)) = -1	Překoření za z=ℓ(y)

AVLInsert

Vlož nový vrchol jako list (standardní BVSInsert). Propaguj nahoru informaci o prohloubení. V každém vrcholu x rozeznáváme:

δ(x) = +1 → změní se na 0, propagování STOP (hloubka T(x) se nezměnila).
δ(x) = 0 → změní se na -1, propagování POKRAČUJE (hloubka T(x) vzrostla).
δ(x) = -1 → δ(x) by bylo -2, nutno vyvažovat rotací (R, L, LR nebo RL). Po rotaci STOP.

AVLDelete

Odstraň vrchol standardně (BVSDelete). Propaguj nahoru informaci o zmenšení. V každém vrcholu x:

δ(x) = -1 → změní se na 0, propagování POKRAČUJE.
δ(x) = 0 → změní se na +1, propagování STOP.
δ(x) = +1 → δ(x) by bylo +2, rotace. Po rotaci může nebo nemusí pokračovat.

📌 Složitost operací AVL stromu

      AVLInsert i AVLDelete trvají O(log n). Počet rotací na operaci: Insert – nejvýše 1 rotace, Delete – až O(log n) rotací.

Praktická poznámka: Červeno-černé stromy (std::map v C++, TreeMap v Javě) jsou jiný typ vyváženého BST s podobnými složitostmi, ale méně rotacemi v praxi. AVL stromy jsou teoreticky jednodušší na analýzu.

🗂️ Hešovací tabulky (hash tables)

Slovník: Datová struktura pro dynamickou množinu K ⊆ U (univerzum) podporující Find(k), Insert(x), Delete(x).
Hešovací tabulka: Pole P = {0, …, m-1} přihrádek + hešovací funkce h : U → P. Prvek s klíčem k ukládáme do přihrádky h(k).

Proč hešovat? Přímé adresování (pole indexované klíčem) má paměť O(|U|), což je obrovské. Heš přiřadí klíče do malého pole m přihrádek a průměrně dosahuje O(1) pro Find/Insert/Delete při m = Θ(n).

Kolize

Kolize nastane, když h(k1) = h(k2) pro různé klíče k1 ≠ k2. Protože m ≪ |U|, kolizím se nelze úplně vyhnout (holubníkový princip).

Příklady hešovacích funkcí

Lineární kongruence: h(k) = (ak) mod m, kde m je prvočíslo a a je vhodná konstanta.
Vyšší bity součinu: h(k) = ⌊(ak mod 2^w) / 2^w-ℓ⌋ – stačí násobení + bitový posun, vhodné pro w-bitové klíče.
Polynom pro řetězce: h(k0, …, kd-1) = Σ aⁱkᵢ mod m.

Faktor naplnění: α = n/m. Vhodné je udržovat α ≤ 0.7–0.8. Při překročení prahu → přehešování: zdvojnásobíme m, nová hešovací funkce, přeložíme vše. Amortizovaně O*(1).

Řešení kolizí: Řetězení (chaining)

Každá přihrádka obsahuje spojový seznam všech klíčů zahešovaných do ní. Find, Insert, Delete = výpočet h(k) + průchod řetízku délky ⌈n/m⌉ (průměrně). Při α = Θ(1) jsou operace průměrně O(1). Paměť: O(n + m).

Řešení kolizí: Otevřená adresace

Všechny prvky jsou přímo v tabulce. Pro klíč k je definována vyhledávací posloupnost h(k, 0), h(k, 1), …, h(k, m-1). Find/Insert prochází posloupnost dokud nenalezne prázdnou přihrádku.

Lineární přidávání: h(k, i) = (f(k) + i) mod m. Jednoduché, cache-friendly, ale trpí shlukováním (clustering) → degradace pro vyšší α.
Dvojité hešování: h(k, i) = (f(k) + i·g(k)) mod m, m prvočíslo. Lepší distribuce, méně shlukování. Každá přihrádka navštívena právě jednou (m je prvočíslo ⟹ g(k) je s m nesoudělné).

Mazání při otevřené adresaci

Smazaný prvek nelze prostě odstranit – přerušilo by to vyhledávací posloupnost! Místo toho použijeme náhrobek † (tombstone): přihrádka je označena jako „smazáno". Find ignoruje náhrobky (prochází dál), Insert může náhrobek přepsat.

Nevýhoda: Hromadění náhrobků. Po překročení prahu → přehešování (odstraní náhrobky).

📊 Věta o efektivitě otevřené adresace

      Pokud jsou vyhledávací posloupnosti náhodné permutace, neúspěšné hledání navštíví průměrně nejvýše 1/(1-α) přihrádek. Pro α = 0.5 jsou to 2 přihrádky, pro α = 0.9 je to 10.

Metoda	Find průměr	Paměť	Poznámky
Řetězení	O(1 + α)	O(n+m)	Flexibilní; extra paměť pro seznamy
Lin. přidávání	O(1/(1-α)²)	O(m)	Cache-friendly, shlukování
Dvojité hešování	O(1/(1-α))	O(m)	Lepší distribuce, 2 hešovací funkce

Nafukovací (dynamická) hešovací tabulka

Analogie nafukovacího pole: na počátku malá tabulka, při α > Z zdvojnásobíme m a přehešujeme. Amortizovaná složitost Insert = O*(1). (Přehešování O(n) nastane jen logaritmicky mnohokrát.)

📝 Shrnutí Okruhu 2

Binární halda: kompletní binární strom + haldové uspořádání. FindMin O(1), Insert/ExtractMin O(log n), Build O(n). Reprezentace v poli bez ukazatelů.
Binomiální halda: sada binomiálních stromů, struktura daná binárním zápisem n. Klíčová výhoda: BHMerge v O(log n), BHInsert amortizovaně O*(1).
BVS: BST vlastnost zaručuje, že Find/Insert/Delete jsou O(h). Nevyvážený strom může mít h = O(n).
AVL stromy: hloubkové vyvážení (|h(L) - h(R)| ≤ 1) garantuje h = O(log n). Oprava rotacemi (R, L, LR, RL). Insert/Delete = O(log n).
Hešovací tabulky: průměrně O(1) pro Find/Insert/Delete při vhodném α. Řetězení vs. otevřená adresace. Klíčový problém: kolize a jejich řešení.

❓ Kontrolní otázky ke státnicím (Okruh 2)

Proč HeapBuild trvá O(n) a ne O(n log n)?

Klíčem je analýza práce BubbleDown: vrcholy na nižší hladině odvádějí méně práce (menší výška podstromu). Součet přes všechny vrcholy: Σ h(v) = n/2·0 + n/4·1 + n/8·2 + … = nΣi/2ⁱ = O(n), protože řada Σi/2ⁱ konverguje ke konstantě.

Proč má binomiální halda amortizovanou O*(1) pro Insert?

BHInsert odpovídá přičtení 1 v binárním čítači. Každé „přenesení" (sloučení dvou stromů stejného řádu) odpovídá bitové inverzi. Podle amortizované analýzy binárního čítače (bankéřova metoda) jsou celkové náklady n operací Inc rovno O(n) – tedy amortizovaně O*(1) na operaci.

Proč je potřeba dvojitá rotace u AVL stromů a nestačí jednoduchá?

Jednoduchá rotace selže, pokud nevyvážený vrchol x má y = ℓ(x) a z = r(y) přičemž z je hlubší než ℓ(y). Po jednoduché rotaci doprava bychom z příliš těžkého pravého podstromu y udělali ještě těžší pravý podstrom – problém přesuneme. Dvojitá rotace (LR nebo RL) nejprve „narovná" poměr, pak provede hlavní rotaci.

Co se stane při mazání z hešovací tabulky s otevřenou adresací, pokud prostě přihrádku vymažeme (bez náhrobku)?

Přeruší se vyhledávací posloupnost. Jiný klíč k', jehož vyhledávací posloupnost prošla přes smazanou přihrádku, by byl přeskočen – Find by odpověděl „nenalezen", i když k' v tabulce je. Náhrobek říká „přihrádka je volná ale vyhledávání pokračuje dál".

Jak se BVS liší od haldy? Lze pomocí BVS implementovat prioritní frontu?

BVS: Find libovolného klíče O(log n), seřazený výpis O(n). Halda: FindMin O(1), ale Find libovolného klíče O(n). BVS lze použít jako prioritní frontu (Min = BVSMin, ExtractMin = BVSMin + BVSDelete), ale halda je praktičtější díky O(1) FindMin a jednoduché implementaci polem.

Proč Jarníkův algoritmus a Dijkstrův algoritmus mají totožnou implementaci?

Oba udržují haldu vrcholů s klíčem d[v] a opakovaně vybírají minimum. Rozdíl je jen v definici klíče: Jarník = váha nejlehčí hrany do T; Dijkstra = celková vzdálenost od startu. Proto je i složitost stejná: O(E log V) s binární haldou.