为什么Quick-Union加权的索引在与更大的树合并时仍然保持大小为1？

Question

我一直在使用coursera上的一个类来研究算法。在首批讲座之一中，正在讨论快速联盟加权。我了解它的功能，并使用他们的代码对其进行了测试，并为其编写了一个小测试。

一切都很清楚，除了一点:当您创建两个对象的联合时，它会将具有最小树的对象添加到较大的对象中。同时，在一个单独的数组中，较大的树的大小将随着较小的树的大小而增加，该数组用于确定哪个树更大。既然数组的每个索引都是以值1初始化的(每个节点本身基本上都是一个包含1个对象的树)，为什么这个索引的值不设置为0，而是保持为1呢？

为了说明这一点：

// 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

为什么合并索引的大小是1而不是0？您可以在here中找到测试它的代码。请注意，实现与讲师提供的example相同，这就是为什么我假设我的代码是正确的。

Answer 1

我认为这是因为节点本身的大小也是1，并且没有任何子节点。然而，它可以有孩子。我实际上不熟悉Quick-Union加权算法，但如果它有点像我见过的其他union find算法，例如，您可以这样做

quw.union(0, 1);
ID: 0 0 2 3 2 2 6 2 8 9 
SZ: 1 1 4 1 1 1 1 1 1 1

quw.union(0, 2);
ID: 2 2 2 3 2 2 6 2 8 9 
SZ: 2 1 6 1 1 1 1 1 1 1

因此，现在0 en 1已经合并，并且从0开始的整个树再次与2合并，仍然使子树从0开始大小为2。

就像我说的，我不确定这在Quick-Union权重中是可能的，但'1‘的原因仍然是因为它本身也是大小为1的。