Union operaton應該如何正確實現不相交集數據結構？

Question

有許多不同的描述和例子可以在線使用不相交集結構。

在某些情況下，對於每組，它存儲「等級」。當一個集合被合併到另一個集合中時，前者的等級增加1，如果他們是同一等級的話。

在其他情況下，對於每組，它存儲其大小。當一個集合被合併到另一個集合中時，它們的大小被添加。

Here它存儲排名。

在the wikipedia article中，它存儲等級。

In the Cornell University lecture notes，它存儲等級。

在example從"Algorithms", by Sedgewick and Wayne，它存儲大小。

Here，它也存儲大小（main site）。

Cormen et al。寫：

顯而易見的方法是使樹的根更少，節點指向更多節點的樹的根。我們將使用一種可以簡化分析的方法，而不是明確跟蹤每棵根節點處的子樹的大小。對於每個 節點，我們維護一個等級，這是節點高度的上限。按照排名合併，在UNION操作期間，對具有較大排名的根進行較小排名點 的根。

哪個更好/更合適？

Answer 1

所有的分析（是？）表明，這兩種方法提供最佳的O（alpha）複雜性，當與樹木崩潰技術結合。

然後唯一的實現特定差異來自大小或等級變量的大小。大小可以高達size_t，但等級可以總是以三位進行編碼。

有時候可以將這三位編碼到要處理的數據/節點中未使用的位中，從而提高性能（速度和大小）。