Quick-Union with Union-by-Rank (10 marks) In class, we saw the Weighted Quick-Un

Question

Quick-Union with Union-by-Rank (10 marks) In class, we saw the Weighted Quick-Union algorithm, which performs UNION in the following way: make the root of the tree containing less elements the child of the root of the tree containing more elements (with ties resolved arbitrarily). Let's call this version of UNION "Union-by-Weight". We w now look at a similar algorithm, which instead uses a version of UNION we will call "Union-by-Rank". Union-by-Rank proceeds by making the root of the tree of smaller height a child of the root of the tree of greater height (with ties resolved arbitrarily) Let n be the number of vertices. Prove that when using Quick-Union with Union-by Rank, a call to CONNECTED takes time O(log n) in the worst case.

Explanation / Answer

public class WeightedQU
{
private int[] id;
private int[] iz;

public WeightedQU(int N)
{
id = new int[N];
iz = new int[N];
for(int i = 0; i < id.length; i++)
{
iz[i] = i;
id[i] = i;
}
}

public int root(int i)
{
while(i != id[i])
{
id[i] = id[id[i]];
i = id[i];
}
return i;
}

public boolean connected(int p, int q)
{
return root(p) == root(q);
}

public void union(int p, int q)
{
int i = root(p);
int j = root(q);
if(iz[i] < iz[j])
{
id[i] = j;
iz[j] += iz[i];
}
else
{
id[j] = i;
iz[i] += iz[j];
}
}
}

import java.util.Arrays;

public class QuickUnionUF {

private int[] id;
private int[] sz;

public QuickUnionUF(int N) {
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; ++i) {
id[i] = i;
sz[i] = 1;
}
}

private int root(int i) {

if(i == id[i]){
return i;
}
id[i] = root(id[i]);
return id[i];
}

void initialize( int Arr[ ], int N)
{
for(int i = 0;i<N;i++)
Arr[ i ] = i ;
}

bool find( int Arr[ ], int A, int B)
{
if(Arr[ A ] == Arr[ B ])
return true;
else
return false;
}

void union(int Arr[ ], int N, int A, int B)
{
int TEMP = Arr[ A ];
for(int i = 0; i < N;i++)
{
if(Arr[ i ] == TEMP)
Arr[ i ] = Arr[ B ];
}
}
public boolean connected(int p, int q) {
System.out.println(p + " and "+ q+" whether connected: "+(root(p) == root(q)));
return root(p) == root(q);
}

public void union(int p, int q) {
int i = root(p);
int j = root(q);
if (i == j) {
return;
}
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
System.out.println("Attach root("+p+") = "+i+" to root("+q+") = "+j+". Size"
+ " root("+q+") = "+sz[j]);
} else {
id[j] = i;
sz[i] += sz[j];
System.out.println("Attach root("+q+") = "+j+" to root("+p+") = "+i+". Size"
+ " root("+p+") = "+sz[i]);
}
}

public static void main(String[] args) {
QuickUnionUF qf = new QuickUnionUF(10);
qf.union(1, 2);
qf.union(3, 4);
qf.union(3, 5);
qf.union(2, 3);
qf.union(6, 7);
qf.union(7, 8);
qf.union(9, 0);
qf.union(8, 9);
qf.union(3, 6);

System.out.println(qf.id[0]);
System.out.println(qf.id[9]);
System.out.println(qf.id[6]);
System.out.println(qf.id[3]);

System.out.println("Calling root(0)");
System.out.println(qf.root(0));
System.out.println("After path compression: ");

System.out.println(qf.id[0]);
System.out.println(qf.id[9]);
System.out.println(qf.id[6]);
System.out.println(qf.id[3]);


System.out.println("Other elements remain as they were before");
System.out.println(qf.id[8]);

}
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.