MHB Union of Disjoint Sets with at Most k Sets - Algorithm

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Sets
AI Thread Summary
The discussion revolves around implementing disjoint sets with union operations using a hash table and double hashing techniques. The focus is on merging two trees corresponding to nodes, utilizing path compression and height reduction methods. The proposed algorithm, `pointer Union(S,T)`, merges two trees by comparing their sizes and adjusting parent pointers accordingly. The challenge presented is how to adapt this merging algorithm within the context of a hash table, which stores keys and pointers to the nodes of the trees. The conversation seeks to clarify the integration of the union operation with the hash table structure while maintaining the efficiency of the disjoint set operations.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Last edited:
Technology news on Phys.org
This is the algorithm that merges two up trees, applying the technique of path compression:
Code:
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;
  }
}
 
Last edited:
What do we have to do in this case, where we have a hash table? (Thinking)
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top