java - 为什么 Quick-Union Weighted 中的索引在与更大的树合并时保持大小 1？

Question

我一直在使用 coursera 上的类(class)研究算法。在第一个讲座中，正在讨论 Quick Union Weighted。我明白它的作用，我已经使用他们的代码对其进行了测试并为其编写了一个小测试。

一切都很清楚，但有一点:当您创建两个对象的并集时，它会将具有最小树的对象添加到较大的树中。同时，较大树的大小将随着较小树的大小在一个单独的数组中递增，该数组用于确定哪棵树更大。由于数组的每个索引都以值 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 并且没有任何子节点。但是它可以有 child 。我实际上对 Quick-Union Weighted 并不熟悉，但如果它有点像其他 union find algoritmes 我已经看到你可以例如做

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 Weighted 中是否可行，但“1”的原因仍然是因为它本身也是大小 1。