Union of disjoint sets

Question

I am looking at disjoint sets that support the function of the Union.

The technique of height reduction of a tree:

We always merge the smaller tree to the greater one, i.e. we make the root of the smaller tree to point to the root of the greater tree.

A tree is greater than an other if it has more nodes.

Each node is a struct with fields: some information for the element, the pointer "parent" to the parent node, and a counter "count", that is used only if the node is the root and contains the number of the nodes at the up-tree.

The following algorithm merges two up trees:

pointer UpTreeUnion(pointer S,T) {
   if (S == NULL OR P == NULL) return;
   if (S->count >= T->count) {
       S->count = S->count + T->count;
       T->parent = S;
       return S;
   }
   else {
       T->count = T->count + S->count;
       S->parent = T;
       return T;
   }
}

Consider an implementation of disjoint sets with union, where there can be at most k disjoint sets. The implementation uses a hash table A[0.. max-1] at which there are stored keys based on the method ordered double hashing. Let h1 and h2 be the primary and the secondary hash function, respectively. A contains the keys of the nodes of all of the above trees and also a pointer to the corresponding node for each of them. I want to write an algorithm that takes as parameters the keys of two nodes and merges the up-trees to which the nodes belong (the nodes can belong to any up-trees, even at the same in which case it appears an appropriate message). At merging, we should apply techniques of path compression and height reduction.

Could you give me a hint how we could do this?

Suppose that we have this array:

At the beginning the nodes will be like that:

Then if k1=100, k2=5, after applying the algorithm, will we get this?

Then if we have k1=59, k2=5, we will get the following:

Right? Then applying the path compression we start doing this:

tmp=B
while (B->parent!=B)
      parent=B->parent;
      tmp->parent=B;
      tmp=parent;
}

So we will have parent=F, tmp->parent=B, tmp=F.

How do we continue?

Having then k1=14, k2=59 we get this:

Answer 1

First, when you get keys, you need to find them in the hash table.
Hash table contains entries: (key, pointer-to-node).
Let's say you want to find key k. You check:
A[h1(k) + 0*h2(k) mod size(A)] - if it contains key k, you read corresponding pointer-to-node.
If there is something other than k, you check:
A[h1(k) + 1*h2(k) mod size(A)],
A[h1(k) + 2*h2(k) mod size(A)],
A[h1(k) + i*h2(k) mod size(A)]... until you find key k.

Now that you have pointers to 2 nodes, you need to find roots of the trees those nodes belong to. To find the root, you go up the tree until you reach root node. You use parent pointer of each node for it and you can assume that root's parent pointer points to itself for example.

Now that you have 2 roots, you can merge them using upTreeUnion.

Path compression works like this:

After you have found root of a tree for node s, you follow the path from s to root one more time and set parent pointer of every node on the path to the root.

Update:

Algorithm(k1,k2){
   int i=0,j=0;
   int i1,i2;
   while (i<max and A[i1 = h1(k1)+i*h2(k1) mod size(A)]->key!=k1){
          i++;
   }
   while (j<max and A[i2 = h1(k2)+j*h2(k2) mod size(A)]->key!=k2){
          j++;
   }
   if (A[i1]->key!=k1) return;
   if (A[i2]->key!=k2) return;

   pointer node1,node2,root1,root2;
   node1=A[i1]->node;
   node2=A[i2]->node;
   root1=UpTreeFind(node1);
   root2=UpTreeFind(node2);
   if (root1==root2){
      printf("The nodes belong to the same up tree");
      return;
   }

   // path compression
   pointer tmp,tmpParent;

   tmp = node1;
   while (tmp->parent!=root1) {
       tmpParent=tmp->parent;
       tmp->parent=root1;
       tmp=tmpParent;
   }

   tmp = node2;
   while (tmp->parent!=root2) {
       tmpParent=tmp->parent;
       tmp->parent=root2;
       tmp=tmpParent;
   }

   UpTreeUnion(root1,root2);
}