Disjoint Set是一個判斷元素和元素之間是否連結的ADT(Abstract Data Type)：

Interface DisjointSet<Integer>{
	void connect(int p, int q);
	boolean isConnected(int p, int q);
}

如以下示意圖，connect方法可以建立元素之間的連結，而isConnected就是判斷丟進來的兩個引數之間是否有相連，這個相連不一定是要直接相連，只要有路可以通到就算：

接著就要來探討，該如何實作出這樣的功能呢？

實作一（ListOfSetsDS）

最直覺的想法，大概就是建一個List<Set>來存不同群已經相連的元素，只不過這樣在connect跟isConnected的方法實作上會很慢，因為你必須把每一個Set抓出來檢查，看看方法丟進來的引數在哪一個Set。

結論：connect會是O(N)，isConnected會是O(N)

這邊是Big O是因為最快的情況o.o.g(order of growth)不會到N。

實作二（QuickFindDS）

這個實作滿酷的，就是只使用一個array來存元素，並利用array的index來當作實際的元素，而array裡面存的是群組的標籤，如下圖：

這樣實作有個很明顯的優勢，就是isConnected超級快，只要Θ(1)就可以完成，因為直接判斷int[p] == int[q]就結束了。

但是connect就還是跟ListOfSetsDS實作差不多慢，因為我們不會直接知道各個index的群組標籤是多少，只能透過一個一個從array抓出來才知道。

結論：connect會是Θ(N)，isConnected會是Θ(1)

這邊用Θ是因為就算是最快的情況，o.o.g還是會到N。

實作三（QuickUnionDS）

上面使用了兩種實作，都無法解決connect沒有效率的問題，是時候需要來點突破性的思考了。

關鍵的問題就在於，能不能只改變一個值就做到connect的效果？

這時候就要來介紹樹狀結構了，我們設計如下的概念在array中，-1代表該index是樹狀的根，其他值則以其上一層元素(parent)來定義，如1和4是0這棵樹的第一層，所以他們的值設為0；而5是3這棵樹的第一層，其值設為3：

這樣就能夠讓connect指更改一個值就辦到嗎？是的：

因為Disjoint Set的特性是只要不同群中的某一個元素相連，那就代表這兩群會變成同一群，而這樣的特性在樹狀結構中只要去把root改變，就可以很順利的辦到。

不過isConnected就無法像QuickFindDS那樣是Θ(1)了，因為我們必須得透過root(n)方法找回到root才能判斷是否為同一群。

而且這樣的樹狀結構有個隱憂，就是當樹的層數越來越高時，root(n)方法會越來越慢！最糟的情況有可能會有如下的樹狀結構：

不過這個情況是可以解決的～就在下一個實作方法。

結論：connect會是O(N)，isConnected會是O(N)

看起來沒有很快，是因為目前還是有可能遇到沒有分支、直直一條的樹，下一章節就會解決這個問題。

實作四（WeightedQuickUnionDS）

在進入詳細介紹前，要先理解樹高問題。以下的情況中，哪個作法比較好：

答案會是讓最終樹高比較低的，因為在實作三中我們知道，不管在進行connect或isConnected，都勢必得使用root(n)方法去找到root是誰，才有後續的動作，而影響root(n)方法的關鍵就是樹高！因為層數越低，我們一路爬回root的步數就越少。

用肉眼看我們可以很快判斷哪種作法會比較好，那該如何定義出某個規則來達到這樣的效果呢？

最常見的做法就是讓weight比較小的樹加進weight比較大的樹。(weight是指樹所擁有的元素數)

這樣的做法可以變多快？以下會應用weighted tree的規則套到connect方法來看看，若我們要讓height最快速的增長，所需最少的weight是多少：（也就是worst case）

一開始只有一個元素時，height會是0，這應該沒有異議：

要讓height變成1，就是加一個元素就能做到了：

那要讓height變3呢？如果我們一次只加一個元素進去，依據weighted tree的規則，它們的parent會不斷被認列為root 0，這樣永遠也無法成為height 3的樹；根據weighted的規則，勢必也得加入一個weight為2的樹，才能讓height變為3：

接著要讓height變成4呢？同理推論，得加入height同為2的tree：（由於所有connect方法都套用weighted tree規則，所以要達到height2的樹，會長得一樣）

然後讓height變成4的話：

可以觀察到，在weighted規則下我們想辦法讓height以最快速度增長的話，其所能容納的weight是一個logN的關係；反之，當我們應用weighted tree作為Disjoint Set的connect實作方法時，其效能就是O(logN)！因為實際情況有可能N會更少，也就是更難讓樹變高；最壞的情況就是剛剛推導的狀況了，所以是Big O logN。

結論：connect會是O(logN)，isConnected會是O(logN)

以下為本章節談到的四種實作法的效能總結：

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License