Databases
StackOverflow2013
Postsdbo
POWhy does an index in Quick-Union Weighted remain size 1 when merged with a bigger tree?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy does an index in Quick-Union Weighted remain size 1 when merged with a bigger tree?
    primarykey
    data
    text
    <p>I've been looking into algorithms using a class on coursera. In one of the first lectures, Quick Union Weighted is being discussed. I get what it does and I've tested it out using their code and written a small test for it. </p> <p>Everything is clear but one point: when you create a union of two objects, it will add the object with the smallest tree to the bigger one. At the same time, the size of the larger tree will be incremented with the size of the smaller tree in a separate array which is used to determine what tree is bigger. Since the array is initiated with value 1 for every index (every node on its own basically is a tree of 1 object), why isn't the value of this index set to 0 instead of remaining on 1?</p> <p>In order to illustrate this:</p> <pre><code>// Quick Union Weighted ID: 0 1 2 3 4 5 6 7 8 9 SZ: 1 1 1 1 1 1 1 1 1 1 quw.union(2, 4); ID: 0 1 2 3 2 5 6 7 8 9 SZ: 1 1 2 1 1 1 1 1 1 1 quw.union(5, 4); ID: 0 1 2 3 2 2 6 7 8 9 SZ: 1 1 3 1 1 1 1 1 1 1 quw.union(2, 7); ID: 0 1 2 3 2 2 6 2 8 9 SZ: 1 1 4 1 1 1 1 1 1 1 // Whereas I would've expected to end up with this // to point out that the index is empty. SZ: 1 1 4 1 0 0 1 0 1 1 </code></pre> <p>Why are the sizes of merged indices 1 instead of 0? You can find the code to test it out <a href="https://github.com/Vannevelj/Algorithms/tree/master/src/unionfind" rel="nofollow">here</a>. Note that the implementation is the same as the <a href="http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html" rel="nofollow">example</a> provided by the lecturers, which is why I'm assuming my code is correct. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJeroen Vannevel
    1. USJeroen Vannevel
    plurals
    1. This table or related slice is empty.
    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. POWhy does an index in Quick-Union Weighted remain size 1 when merged with a bigger tree?
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

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