Pfad-Kompression mit gewichteten Union (zweite Verbesserung)

Problem: Folge von k Find - und Union -Operationen auf einen Operation mit n Elementen, darunter n-1 Union .

Implementierung: Gewichtete Union , Find 's für Pfad-Kompression:

Bemerkung: Nach der Definition ist $\log^* = \min \{ i \geq 1; \underbrace{\log\log\log\dots\log{n}}_{i-\log\text{'s}} \leq 1\}$.
Beispiele:
$\log^*0 = \log^*1=1$
$\log^*2 = 1$
$\log^*3 = 2$
$\log^*16 = 2^{2^{2}}=3$
$\log^*2^{65536} = 2^{2^{2^{2^{2}}}}=5$

Beweis: Sei T' der (endgültige) In-Baum, der durch die Folge der Union 's, ohne die Find 's entstehen würde (also keine Pfad-Kompression). Ordne jedem Element x drei Werte zu:

• rank(x):= Höhe des Unterbaums in T' mit Wurzel x
  
• class(x):= $\left\{\begin{array} {ll} i\geq 1 &\text{ falls }a_{i-1} < \text{ rank}(x) \leq a_i \text{ ist }(i\geq 1)\\ 0 &\text{ falls rank}(x) = 0\\ \end{array} \right.$
  
  
  Dabei gilt: $a_0=0, a_i=2^{\left. 2^{.^{.^{2}}}\right\}i-2'\text{en} }$ für $i\geq 1$
  
  

  
  
  

• dist(x) ist die Distanz von x zu einem Vorfahr y im momentanen Union-Find-Baum (mit Pfad-Kompression) mit class(y) > class(x) bzw. y ist Wurzel des Baumes.

Definiere eine geignete Potentialfunktion:

• Potential := $c\sum_x \text{dist}(x)$    c ist eine geignete Konstante >0

Beobachtungen:

i)

Sei T ein Baum in der aktuellen Union-Find-Stuktur (mit Pfad-Kompression), seien x,y Knoten im T, y Vater von x $\Rightarrow$ class($x)\leq$ class(y).

ii)

Aufeinander folgende Find(x) besitzen (bis auf eine) verschiedene Kanten. Diese Kanten sind (im wesentlichen) eine Teilfolge der Kanten in T' auf dem Pfad von x zur Wurzel.

Amotisierte Kosten Find(x) :
Sei $x_0 \rightarrow x_1 \rightarrow x_2 \dots x_k = r$ die Pfad von x₀ zur Wurzel. Kanten (x_i-1,x_i) mit class(x_i-1) = class(x_i). Es gibt höchstens $\log^*n$-Kanten (x_i-1,x_i) mit class(x_i-1) < class(x_i). Ist class(x_i-1) = class(x_i) und i<k (also $x_i\neq r$), dann ist dist(x_i-1) vor der Find(x) -Operation $\geq 2$, nachher gleich 1.
Damit können die Kosten für alle Kanten (x_i-1,x_i) mit class(x_i-1)=class(x_i) aus dem Potentialverringerung bezahlt werden und es ergeben sich amortisierte Kosten:



Amortisierte Kosten aller (n-1)- Union 's zusammen:

Die gesamte Potentialerhöhung durch alle Union 's ist nach oben durch das Potential von T' beschränkt (Beobachtung ii).

$$\begin{split} \text{Potential}(T') & \leq \sum_{i=0}^{log^*n... ...} = \sum_{i=0}^{log^*n} 1 =\mathcal{O}(n\log^*n)\\ \end{split}$$

$\Diamond$