Modify find method inside UF_WeightedQuickUnionPathCompression class to implemen

Question

Modify find method inside UF_WeightedQuickUnionPathCompression class to implement path compression like this. After calling find(x), every node on the path from x to the root has its parent changed to the root.

public class UF_WeightedQuickUnionPathCompression extends UF {
   private int[] sz; // size of component for roots (site indexed)

   public UF_WeightedQuickUnionPathCompression(int n) {
       super(n);
       sz = new int[n];
       for (int i = 0; i < n; i++) sz[i] = 1;
   }
  
   @Override
   // worst-case running time O(lgn)
   public int find(int p) {

//code goes here
       throw new UnsupportedOperationException();
   }  

   @Override
   // worst-case running time O(lgn)
   public void union(int p, int q) {
       int i = find(p);
       int j = find(q);
       if (i != j) {
           // Make smaller root point to larger one.
           if (sz[i] < sz[j]) {
               id[i] = j; sz[j] += sz[i];
           } else {
               id[j] = i; sz[i] += sz[j];
           }
           count--;
       }
   }      
}

Explanation / Answer

I have modified the FIND method in Modify in UF_WeightedQuickUnionPathCompression class.
Firstly we need to create a FIND Method which returns an id and call the validate function to give an valid index value.

FIND Method:-

// Created a find method with parameter x

public int find(int x) {
validate(x);
      
       // returns the id
      
return id[x];
}
  
// to validate the parameter x and gives the index base
  
private void validate(int x) {
int n = id.length;
      
       // check the conditions using if-else statement
      
if (x < 0 || x >= n) {
throw new IndexOutOfBoundsException("The index value" + x + " is not between 0 and " + (n-1));
}
}

Program:-

public class UF_WeightedQuickUnionPathCompression extends UF {
private int[] sz; // size of component for roots (site indexed)
public UF_WeightedQuickUnionPathCompression(int n) {
super(n);
sz = new int[n];
for (int i = 0; i < n; i++) sz[i] = 1;
}
  
@Override
// worst-case running time O(lgn)

// Created a find method with parameter x

public int find(int x) {
validate(x);
      
       // returns the id
      
return id[x];
}
  
// to validate the parameter x and gives the index base
  
private void validate(int x) {
int n = id.length;
      
       // check the conditions using if-else statement
      
if (x < 0 || x >= n) {
throw new IndexOutOfBoundsException("The index value" + x + " is not between 0 and " + (n-1));
}
}


@Override
// worst-case running time O(lgn)
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i != j) {
// Make smaller root point to larger one.
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i];
} else {
id[j] = i; sz[i] += sz[j];
}
count--;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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