Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Disjoint Set Structures

  1. Jun 15, 2008 #1
    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.

    Code (Text):

    {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 ?
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted