Geek asks and answers

Weighted Rule

Can someone check with me if I use the rule correctly in the last step (7)?

UPDATE:

The numbers inside parentheses are the number of elements (weight (?)) Of each set participating in the Union. Uppercase letters are set names.

As I understand it: we use the number of elements as our rank? This is confusing; everyone uses different terms for the same material.

We have Unions:

  • U (1,2, A)
  • U (3.4, B)
  • P (A, B, C)
  • U (5,6, D)
  • U (7.8, E)
  • V (D, C, F)
  • V (E, F, G)

enter image description here

+3
source share
2 answers

Step 7 (and others) looks correct, but step 6 does not work.

In step 6-4, there should be a root, as this is a larger tree.

+1
void combine(int x,int y)
{
    int xroot=find(x),yroot=find(y);
    if(rank[xroot]<rank[yroot]) 
        parent[xroot]=yroot;
    else if(rank[xroot]>rank[yroot]) 
    parent[yroot]=xroot;
    else 
    {///rank of both is equal..
        parent[yroot]=xroot;
        rank[xroot]++;
    }
}

, size of set, , 6 .

size?
, , update .

CLRS ( ).

, !

0

More articles:


All Articles