Union of Disjoint Sets with at Most k Sets - Algorithm

[evinda]

Hello! (Smirk)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.. \text{ 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 upper trees to which the nodes belong (the nodes can belong to any upper trees, even at the same in which case it appears an appropriate message). At merging, we have to apply techniques of path compression and height reduction.How could we do this? (Thinking)

 

[evinda]

This is the algorithm that merges two up trees, applying the technique of path compression:

pointer Union(S,T){
  if (S==NULL or T==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;
  }
}

 

[evinda]

What do we have to do in this case, where we have a hash table? (Thinking)