????????眾所周知，學習一個數(shù)據(jù)結(jié)構(gòu)就要了解它的三要素：邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)，數(shù)據(jù)的運算。那么首先我們要知道并查集的邏輯結(jié)構(gòu)是什么？（邏輯結(jié)構(gòu)就是元素間的邏輯關(guān)系，包括線性結(jié)構(gòu)，非線性結(jié)構(gòu)（集合、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)））。

????????并查集是一種集合，但是它是把屬于同一個集合的元素放到同一棵樹上，這樣多個集合就是多個互不相交的樹。并和查就是其兩個基本操作，查就是從這個元素找到其根節(jié)點從而確定其屬于哪個集合，并就是讓一棵樹成為另一棵樹的子樹，把兩個集合并起來。

????????而樹的表示主要有三種：雙親表示法，孩子表示法，孩子兄弟表示法。

????????顯然，雙親表示法來表示樹，更容易實現(xiàn)并查集。因為雙親表示法是在每個節(jié)點中保存一個指向父節(jié)點的指針，因為指針都是指向父節(jié)點的，因此找到根節(jié)點實現(xiàn)查操作就更容易，如果想要進行并操作，則只需讓其中一棵樹的根節(jié)點指向另一棵樹的根節(jié)點。

????????用這種方式，并查集,并的時間復(fù)雜度為O(1)，find查的最壞時間復(fù)雜度為O(n)，樹的高度越高最壞時間復(fù)雜度越大，因此我們要盡可能讓樹變矮。最直接的辦法，就是在并的時候讓小樹并到大樹上，如何判斷樹大樹小呢，我們可以用根節(jié)點的絕對值表示樹的節(jié)點總數(shù)。同時在union時記得累加節(jié)點總數(shù)。優(yōu)化后樹的高度會不超過[log2n]+1。