How Does Tree Height Evolve in Disjoint Set Structures?

[khdani]

Hello,
The subject is disjoint set structures
There's following pseudocode for merging sets, by representing every
set as single rooted tree and merging is like merging trees.

{h[] is array of heights of trees}

Mege(a,b)
  if(h[a]==h[b])
     set parent of b is a
     h[a]++
  else if(h[a]>h[b])
     set parent of b is a
  else
    set parent of a is b

It's known that after succesive executions of Merge, the max height of
tree is log(n).
The question is if given 4 trees with 20 nodes, what's the maximum height of
a tree that can be ?

 

[KataKoniK]

Hello,

Thank you for sharing your pseudocode for merging sets using disjoint set structures. This is a very efficient way to merge sets and keep track of the heights of the trees.

To answer your question, the maximum height of a tree with 20 nodes after successive executions of Merge would be log(20), which is approximately 4.32. This is because the height of a tree is limited by the number of nodes it has, and in this case, the maximum number of nodes in a tree is 20. As the trees are merged, the heights of the resulting trees will also increase, but it will never exceed log(20).

I hope this helps answer your question. Keep up the great work with disjoint set structures!

 

[piercas]

Hello,

Thank you for bringing up the topic of disjoint set structures. These structures are used to represent a collection of sets that are disjoint, meaning they do not share any elements. This is a useful data structure for various applications, such as graph algorithms and image processing.

The pseudocode provided for merging sets is a common approach for implementing disjoint set structures. By representing each set as a rooted tree, merging becomes a simple process of connecting the roots of the trees. This approach also includes a mechanism for balancing the trees, which helps to maintain a maximum height of log(n) after successive merges.

To answer your question, given 4 trees with 20 nodes, the maximum height of a tree that can be achieved is log(20) = 4. This means that after merging all 4 trees, the resulting tree will have a maximum height of 4, which is the optimal height for efficient operations on the disjoint set structure.

I hope this helps to clarify the concept of disjoint set structures and their use in merging sets. Let me know if you have any further questions.