Databases
StackOverflow2013
Postsdbo
POJava Need help implementing an algorithm
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POJava Need help implementing an algorithm
    primarykey
    data
    text
    <p><a href="https://stackoverflow.com/questions/1567532/java-algorithm-for-finding-the-largest-set-of-independent-nodes-in-a-binary-tree">This algorithm</a> is so advanced for my basic programming skills that I just don't see how I could implement it. I'm posting this in a new question because I can't keep bothering the guy who gave me the algorithm alone about this in the comment section in the previous question. </p> <pre><code>MaxSet(node) = 1 if "node" is a leaf MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) }, Sum{ i=0..1: MaxSet(node.Children[i]) }) </code></pre> <p>Thanks too <a href="https://stackoverflow.com/users/33708/mehrdad">mehrdad</a> for the algorithm. </p> <p>The problem here for me is to implement the part of the two sum lines, how can I do that? And I need to mark every node that this algorithm chooses. It's just a "marked" variable in the node class set to true. I don't understand were it makes a decision too choose a node? </p> <p>EDIT to include my code so far: </p> <pre><code>public int maxSet(Posisjon&lt;E&gt; bt){ if (isExternal(bt)){ return 1; } return Math.max(1 + helper1(bt), helper2(bt)); } private int helper1(Posisjon&lt;E&gt; node){ int tmp = 0; if (hasLeft(node)){ if(hasLeft((Position&lt;E&gt;)node.leftChild())){ tmp += maxSet(node.leftChild().leftChild()); } if(hasRight((Position&lt;E&gt;)node.leftChild())){ tmp += maxSet(node.leftChild().rightChild()); } } if(hasRight(node)){ if(hasLeft((Position&lt;E&gt;)node.rightChild())){ tmp += maxSet(node.leftChild().leftChild()); } if(hasRight((Position&lt;E&gt;)node.rightChild())){ tmp += maxSet(node.leftChild().rightChild()); } } return tmp; } private int helper2(Posisjon&lt;E&gt; node){ int tmp = 0; if(hasLeft(node)){ tmp +=maxSet(node.leftChild()); } if(hasRight(node)){ tmp +=maxSet(node.rightChild()); } return tmp; } </code></pre> <p>This seems to be working, what is left now. Is to actually mark the nodes as chosen? Were would I do that? </p> <hr> <p>Updated with code: </p> <pre><code>public ArrayList&lt;Posisjon&lt;E&gt;&gt; getSelectionSet(Posisjon&lt;E&gt; bt, ArrayList&lt;Posisjon&lt;E&gt;&gt; s){ if(bt.marked){ s.add(bt); } if(hasLeft(bt)){ if(hasLeft(bt.leftChild())){ getSelectionSet(bt.leftChild().leftChild(),s); } if(hasRight(bt.leftChild())){ getSelectionSet(bt.leftChild().rightChild(),s); } } if(hasRight(bt)){ if(hasLeft(bt.rightChild())){ getSelectionSet(bt.rightChild().leftChild(),s); } if(hasRight(bt.rightChild())){ getSelectionSet(bt.rightChild().rightChild(),s); } } return s; } public int maxSet(Posisjon&lt;E&gt; bt){ if (bt.visited){ return bt.computedMax; } bt.visited = true; int maxIfCurrentNodeIsSelected = 1 + helper1(bt); int maxIfCurrentNodeIsNotSelected = helper2(bt); if (maxIfCurrentNodeIsSelected &gt; maxIfCurrentNodeIsNotSelected){ bt.marked = true; bt.computedMax = maxIfCurrentNodeIsSelected; }else{ bt.marked = false; bt.computedMax = maxIfCurrentNodeIsNotSelected; } return maxSet(bt); } </code></pre> <p>After submission, I will post the entire code for this! </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USAlgific
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POJava Need help implementing an algorithm
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt looks like you're just asking for a complete solution. I think you'll get better responses if you post the code you have tried yourself, and ask a specific question about it.
      singulars
      1. POJava Need help implementing an algorithm
      1. USBart Kiers
    2. COI'll clean up my code an post it later if this doesn't help me out. I just used two helper functions as the Sum functions. They are huge, because I also have to check that the nodes aren't null. And the part about how to store the set, were would I mark the nodes as choosen? You can just point it out in the Pseudo algorithm.
      singulars
      1. POJava Need help implementing an algorithm
      1. USAlgific
    3. COUpdated with my code so far. It seems to work with counting the max and returning an int. Only tested on a tree with three elements tough. Were would I mark the nodes as chosen?
      singulars
      1. POJava Need help implementing an algorithm
      1. USAlgific
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload