爲什麼Quick-Union Weighted中的索引在與更大的樹合併時保持大小1？

Question

我一直在研究在coursera上使用類的算法。在最初的講座之一中，正在討論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，並沒有任何孩子。它可以有孩子。實際上，我不熟悉的加權快速聯盟，但如果它像其他工會位找到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.

就像我說的，我不確定這是可能的快速聯合加權，但'1'的原因仍然是因爲它是也是1號本身。