1.  Union find

1.1  operations

• union( u,v )
• is u = v ? = (find(v)=find(u))

used by Kruskal's algorithm

1.2  implementation

Have a large array (one entry per element) which points towards a representative member of each equivalence class. Each equivalence class has some root representative member.

1.2.1 implementing union

Union is implemented by linking the root of one tree to the root of another tree.

Improvement: (weighted union) Link the smaller tree to the larger tree to improve balance. It's necessary to keep along a 'size' field.

1.2.2 find

Recurse towards the root and return the root.

Improvement: (path compression) When you find the representative from an element, adjust every pointer in the path to point directly towards the root.

1.3  analysis

1.3.1 Tree height limitation

Let T, a tree. height(T)=#edge on max length path

lemma: with weighted union |T| ³ 2^height(T)

proof: assume |T₁| ³ 2^h(T₁) , |T₂| ³ 2^h(T₂) and without loss of generality |T₁| ³ |T₂|

T = union(T₁,T₂) .

case 1: height(T) = height(T₁) . Ok, because the height hasn't increased while the size has.

tcase 2: height(T) = 1+height(T₂) . Ok, because 2^{1+height(T₂)} = 2*2^height(T₂) £ 2*|T₂| £ |T₂|+|T₁| = |T|

1.3.2 Ackermann function

• A₀(x) = x+1
• A_k+1(x) = A_k^x(x) where A_kⁱ(x) = A_k(A_k(...(A_k(x))..)

This is pretty fast.

• A₀(x) = x+1
• A₁(x) = A₀^x(x) = 2x
• A₂(x) = A₁^x(x) = 2^xx
• A₃(x) = A₂^x(x) ³ 2^2...2x etc...

Now, define the ackermann function as A(k) = A_k(2) .

Define the inverse Ackermann as: a(n) = min{k:A(k) ³ n} . This grows pretty slow.

1.3.3 union find analysis

• T_t(u) = subtree rooted at u at time t
• rank_t(u) = 2+height(T_t(u))

Rank increases while a node is a root, but never increases when it is not a root.

define: 0 £ d(u) = max{k|rank(parent(u)) ³ A(rank(u)) . Then for n ³ 5 , d(n) £ a(n)

• if $ ancestor(x)=y s.t. d(y) = d(x) then charge x
• else charge 'Find'

'Find' has a(n) cost because it can only be charged once for each value of d.

let x' = parent(x), v = root

• rank(x¢) ³ A_k(rank(x))
• max i of rank(x') ³ A_kⁱ(rank(x))
• rank(v) ³ rank(y¢) ³ A_k(rank(y) ³ A_k(rank(x¢)) ³ A_k(A_kⁱ(rank(x))) = A_kⁱ⁺¹(rank(x))

If x gets rank(x) charges then d(x) increases. This means it can in incur at most rank(x)a(n) charges. This is a rather large number in comparison to a(n) but we are save by the lemma limiting the number of nodes at a particular rank.

total charges < å_{i = 1}^log(n)ra(n)([(n)/( 2^r-2)]) £ na(n)å_{i = 1}^infinity[(r)/( 2^r-2)] = O(na(n))

This means with m union-finds on a set of size n, the timing is O((m+n)a(n))