Předchozí řešení můžeme vylepšit tak, že při každém zavolání $\FIND(v)$ a tedy při každém průchodu orientované cesty z $v$ do kořene $r_v$, přepojíme všechny vrcholy na této cestě přímo do kořene $r_v$. Následující řešení využívá rekurze, ale můžete ho implementovat i bez ní (v prvním průchodu najdete kořen a ve druhém přesměrujete všechny vrcholy do kořene).

FIND($v$):
	 if $v\not=\pi(v)$ then
	 	 $\pi(v):=\FIND(\pi(v))$
	 return $\pi(v)$

Tato heuristika zvýší čas operace $\FIND{}$ jen malinko a snadno se naprogramuje. Z dlouhodobého hlediska nám tato trocha práce navíc může hodně pomoci. Pokud znova zavoláme $\FIND{}$ na stejný vrchol, tak už kořen stromu najdeme na jeden krok. Heuristika s kompresí cestiček se vyplatí, pokud budeme operaci $\FIND{}$ volat častěji než $\UNION{}$. To ale v grafových algoritmech nastává skoro vždy. Operaci $\UNION{}$ můžeme zavolat nejvýše $n$ krát, protože pak už budou všechny vrcholy v jedné komponentě. Operaci $\FIND{}$ typicky voláme pro každou hranu grafu (například v algoritmech pro hledání minimální kostry). A hran může být řádově až $n^2$.

Dá se ukázat, že v implementaci s kompresí cestiček bude $m$ operací $\UNION{}$ nebo $\FIND{}$ trvat $\OO(m \alpha(n))$, kde $\alpha(n)$ je inverzní Ackermannova funkce (pro prakticky použitelná čísla je to konstanta menší rovná $4$, ale jinak pro hodně velká $n$ roste až do nekonečna). Amortizovaný čas obou operací tedy je $\OO(\alpha(n))$, což je prakticky konstantní čas $\OO(1)$.

Poznámka: Prakticky se dobře chová i následující řešení, které při zavolání $\FIND{(v)}$ přepojí do kořene pouze vrchol $v$. Také se o něm dá ukázat, že časová složitost $m$ operací $\UNION{}$ nebo $\FIND{}$ trvá $\OO(m \alpha(n))$.

FIND($v$):
	 while $\pi(v)\not=\pi(\pi(v))$ do
	 	 $\pi(v):=\pi(\pi(v))$
	 return $\pi(v)$

Poznámka: Inverzní Ackermannova funkce $\alpha(n)$ je inverzní funkce k Ackermannově funkci $A(n)$. Ackermannova funkce je definovaná jako diagonála Ackermannovy hierarchie, tedy $A(n) := A(n,n)$. Funkce $A(n)$ roste mnohem rychleji než libovolný polynom, exponenciála či $n!$. Ackermannova hierarchie se počítá rekurzivně.
$$A(m,n)=\left\{
\begin{array}{ll}
n+1 & \mbox{pro $m=0$,} \\
A(m-1,1) & \mbox{pro $m \gt 0$ a $n=0$,} \\
A(m-1, A(m, n-1)) & \mbox{pro $m \gt 0$ a $n \gt 0$.}
\end{array}
\right.$$
Funkce v jednotlivých řádcích jsou $A(1,n)=n+2$, $A(2,n)=2n+3$, $A(3,n)=2^{n+3}-3$, $A(4,n)=\underbrace{2^{2^{2^{\cdot^{\cdot^{{2}}}}}}}_{n+3}-3$.

Hodnoty $A(n)$ pro $n=0,1,2,\dots$ jsou $1$, $3$, $8$, $61$, $2^{2^{2^{65533}}}-3$,….

Upočítání amortizovaného času $\OO(\log^* n)$

V předchozích sekcích jsme si dokázali, že časová složitost operace $\UNION{}$ nebo $\FIND{}$ je v nejhorším případě $\OO(\log n)$ a zmínili jsme se, že se dá pro kompresi cestiček ukázat amortizovaný čas jedné operace $\OO(\alpha(n))$. Teď si ukážeme malinko slabší, ale prakticky dostačující, odhad amortizované časové složitosti.

Číslo $\log^* n$ je definováno jako počet po sobě aplikovaných operací $\log$ takový, abychom z čísla $n$ dostali něco menšího nebo rovno $1$. Například $\log^* 1000 = 4$ protože $\log \log \log\log 1000 \leq 1$. Pro všechna prakticky použitelná čísla $x$ je $\log^* x \leq 5$. Aby byl iterovaný logaritmus $\log^* x \gt 5$, tak bychom potřebovali $x\gt 2^{65536}$. S tak velkým číslem se ale prakticky nikdy nesetkáte.

Věta: Pokud začneme s prázdnou datovou strukturou obsahující $n$ jednoprvkových komponent a provádíme posloupnost $m$ operací $\UNION{}$ nebo $\FIND{}$, tak je celkový čas provedení všech $m$ operací $\OO( (m+n)\log^* n )$.

Operace $\UNION{(u,v)}$ najde reprezentanty komponent (kořeny stromů) zavoláním $\FIND{(u)}$, $\FIND{(v)}$ a pak natáhne šipku mezi kořeny spojovaných komponent. Komprese cestiček na ní nemá žádný vliv. Natažení šipky mezi kořeny zabere jen konstantní čas. Proto při odhadu celkové časové složitosti budeme počítat jen čas operací $\FIND{}$ (místo času pro $\UNION{(u,v)}$ budeme počítat čas $\FIND{(u)}$, $\FIND{(v)}$) a k nim přičteme $\OO(\mbox{#operací $\UNION{}$})$.

Rank vrcholů mění pouze operace $\UNION{}$. Rank kořene se ještě může zvýšit, ale jakmile vrchol přestane být kořenem, tak už se jeho rank nemění. Kompresí cestiček se $rank(v)$ nezmění. Na druhou stranu už ho nebudeme moci interpretovat jako délku nejdelší orientované cesty vedoucí do vrcholu $v$.

Pozorování: $\;$

  • Pro každý vrchol $v$ je $rank(v)<rank(\pi(v))$. <li=““> Každý kořen s rankem $k$ má alespoň $2^k$ potomků.
  • Pokud máme celkem $n$ vrcholů, tak vrcholů s rankem $k$ je nejvýše $n/2^k$.

Důkaz: První vlastnost platí, protože vrchol ranku $k$ vznikl povýšením při spojování dvou kořenů ranku $(k-1)$ (a jejich podstromů). Z toho indukcí dokážeme i druhou vlastnost (zkuste to).

Druhou vlastnost můžeme rozšířit i na vrcholy, které už nejsou kořenem. Každý takový vrchol musel být jednou kořenem a tehdy pro něj vlastnost platila. Od té doby se jeho rank, ani jeho potomci nezměnili.

Protože jsou všechny podstromy určené vrcholy ranku $k$ vzájemně disjunktní, a každý má $2^k$ vrcholů, tak je vrcholů ranku $k$ nejvýše $n/2^k$.

Pracujeme s $n$ vrcholy a proto jejich rank může nabývat pouze hodnot od $0$ do $\log n$ (dle předchozího pozorování). Tyto hodnoty si rozdělíme do následujících pečlivě vybraných intervalů (důvod vyplyne později)

$$
\{1\},\;
\{2\},\;
\{3,4\},\;
\{5,6,\dots, 16\},\;
\{17, 18,\dots, 2^{16}=65536\},\;
\{65537,\dots, 2^{65536}\},\dots
$$

Každý interval je tvaru $\{k+1, k+2, \dots, 2^{k}\}$, kde $k$ je mocnina dvojky. Počet těchto skupin je $\log^* n$. Prakticky si vystačíme s prvními pěti intervaly, protože jinak bychom museli mít více než $2^{65536}$ vrcholů. To se prakticky nikdy nestane.

V posloupnosti operací trvá každá operace $\FIND{}$ jinak dlouho. Pro výpočet amortizovaného času operace $\FIND{}$ použijeme účetní metodu (viz zavedení amortizované časové složitosti). Za každý krok práce budeme muset zaplatit jednou korunu.

Každý vrchol dostane na účet nějaké peníze a to tak, aby všechny vrcholy dohromady dostaly nejvýše $\OO(n\log^* n)$ Kč. Každá operace $\FIND{(v)}$ dostane $\OO(\log^* n)$ Kč. Z těchto peněz musí zaplatit všechnu svoji práci (průchod z $v$ do kořene a kontrakce této cesty). Pokud by jí peníze nestačili, tak si může na platbu půjčit od vrcholů, které prochází. Celkový čas $m$ operací $\FIND{}$ bude nejvýše počet peněz a to je $\OO(m\log^* n)+\OO(n\log^* n)$.

Nyní zbývá ukázat: (a) jak rozdělit $\OO(n\log^* n)$ Kč mezi vrcholy a (b) jak budou probíhat platby za prováděnou práci, abychom na žádném účtu neklesly do mínusu.

Nejprve k rozdělení peněz. Každý vrchol dostane peníze v momentě, kdy přestane být kořenem. Od této chvíle už se jeho rank nemění. Pokud jeho rank leží v intervalu $\{k+1, k+2, \dots, 2^{k}\}$, tak dostane $2^k$ Kč. Z pozorování [ref]observation_unionfind_rank[/ref] víme, že počet vrcholů s rankem větším než $k$ je nejvýše

$$ \frac{n}{2^{k+1}} + \frac{n}{2^{k+2}} + \frac{n}{2^{k+3}} + \cdots \leq \frac{n}{2^k} $$

Proto vrcholům s rankem v jednom konkrétním intervalu zaplatíme nejvýše $n$ korun. Různých intervalů je $\log^* n$ a tudíž celkem vrcholům rozdělíme $\leq n\log^* n$ Kč.

Teď se podíváme na to, jak budou probíhat platby. Čas jedné operace $\FIND{(v)}$ je počet skoků po šipkách z vrcholu $v$ do kořene, v každém vrcholu na cestě musíme vykonat jeden krok práce. Rank vrcholů na této cestě roste. Každý vrchol $x$ na této cestě padne jedné ze dvou kategorií: buď je $rank(\pi(x))$ ve vyšším intervalu než $rank(x)$, a nebo jsou oba ve stejném.

Vrcholů prvního typu je nejvýše $\OO(\log^* n)$ a proto práce v nich zabere nejvýše čas $\OO(\log^* n)$. Tuto práci platí operace $\FIND{(v)}$ ze svého účtu.

Vrcholy druhého typu musí práci zaplatit ze svého účtu. Za odměnu budou “převěšeni” a budou si ukazovat na rodiče s vyšším rankem než byl rank jejich původního rodiče.

Pokaždé, když vrchol druhého typu platí ze svého účtu, tak je povýšen. Tedy po nejvýše tolika povýšeních, kolik dostal peněz (to je nejvýše počet různých hodnot v daném intervalu), dosáhne nirvány a bude si ukazovat na rodiče z vyššího intervalu (už nebude muset nikdy platit).