Union-find
Union-find je dátová štruktúra, ktorá spomínané dve operácie -- union (zjednotenie množín) a find (testovanie, či dva prvky ležia v rovnakej množine) -- implementuje efektívne, v logaritmicom (alebo dokonca lepšom) čase.
Základná myšlienka je, že množiny si reprezentujeme ako zakorenené stromy, kde koreňom je vždy konkrétny prvok. Každý prvok si pamätá iba svojho rodiča (teda vie, že je určite v rovnakej množine, ako iný konkrétny prvok). Koreň je jediným prvkom, ktorý žiadneho rodiča nemá (môžeme to implementovať tak, že je sám označený ako svoj rodič).
Keď chceme zistiť, či dva prvky ležia v rovnakej množine, pre každý z nich prehľadávame postupne reťaz jeho rodičov, až kým nenarazíme na koreň. Ak z oboch prvkov nájdeme rovnaký koreň, ležia v jednej množine.
Ak chceme dva prvky spojiť, najskôr overíme, či už náhodou neležia v jednej množine. Ak áno nemusíme robiť nič. Ak nie, pre každý z daných dvoch prvkov si nájdeme koreň množiny, do ktorej patrí. Potom jednému z týchto dvoch koreňov priradíme druhý z nich ako rodiča. Tým sa z prvého koreňa stane obyčajný vrchol a z druhého koreň celej množiny.
Ako dlho to trvá? Spojiť dva korene je rýchle, porovnať ich tiež. Limitujúcim krokom je nájsť pre každý vrchol jeho koreň, keďže reťaz rodičov môže byť pri neoptimálnom poradí spájania veľmi dlhá. Pokiaľ máme $N$ vrcholov, môže každá operácia trvať až $O(N)$ času.
Zrýchliť to dokážeme niekoľkými spôsobmi.
Prvé zrýchlenie -- union podľa hĺbky
Pri operácií find trávime veľa času tým, že prechádzame rodičov jednotlivých vrcholov až po koreň. Ak nechceme, aby cesty z vrcholov do koreňa boli príliš dlhé, môžeme sa snažiť vždy zjednocovať množiny tak, aby bol výsledný strom čo najmenej hlboký. Pre každý koreň si budeme pamätať maximálnu hĺbku vrcholov v jeho strome. Pri spájaní potom porovnáme hĺbky a zapojíme plytší koreň pod hlbší.
Maximálna hĺbka vrcholu v podstrome koreňa zjednotenej množiny môže byť najviac o jedna väčšia, ako bola pred zjednotením. To platí, pretože hĺbka vrcholov v jeho pôvodnom podstrome sa nezmenila a hĺbka vrcholov z druhého podstromu sa zväčšila o $1$ (a každý vrchol z druhého podstromu mal najviac takú hĺbku, ako najhlbší vrchol z prvého podstromu, inak by sme ich zapojili naopak).
Toto nám výrazne zlepší časovú zložitosť -- pozrime sa na to, aká môže byť maximálna hĺbka množiny v závislosti of počtu vrcholov. Jeden vrchol má vždy hĺbku $1$. Dva vrcholy majú maximálnu hĺbku v podstrome $2$. Pokiaľ chceme hĺbku stromu s hĺbkou $2$ zväčšiť, musíme pripojiť ďalší strom aspoň rovnako hlboký. Výsledný strom hĺbky $3$ bude mať teda aspoň $4$ vrcholy. Ak chceme jeho hĺbku ešte zväčšiť, potrebujeme k nemu pripojiť ďalší strom s aspoň rovnakou hĺbkou...
Vidíme teda, že aj najmenší počet vrcholov, ktoré môže mať strom s určitou minimálnou hĺbkou, sa s danou hĺbkou zväčšuje exponenciálne. Hĺbka teda s počtom vrcholov rastie logaritmicky. Vďaka tomu nebude žiadna hĺbka väčšia ako $O(log N)$, a teda ani žiadna cesta do koreňa nebude mať viac hrán. Operácia find teda bude trvať len $O(log N)$.
Druhé zrýchlenie -- kompresia ciest pri find
Druhá možnosť je čas, ktorý pri operácií find trávime hľadaním koreňa, využiť na úpravu dátovej štruktúry, aby sme nabudúce mohli byť rýchlejší. Konkrétne tak, že potom, ako nájdeme koreň pre nejaký vrchol, prehľadáme celú postupnosť vrcholov ešte raz, ale každému vrcholu, ktorý pritom navštívime, nastavíme už nájdený koreň rovno ako rodiča. Tým cesty z daných vrcholov do koreňa skrátime na dĺžku $1$.
Ako sa zlepší časová zložitosť? Keď použijeme obidve zlepšenia, dá sa dokázať (hoci veľmi zložitým spôsobom), že časová zložitosť bude $O(\alpha(N))$ na každú z operácií. $\alpha$ označuje takzvanú inverznú Ackermanovu funkciu, ktorá stúpa tak pomaly, že pre všetky rozumne použiteľné vstupy má hodnotu $\leq 5$.