攤還分析

按秩合併(union by rank)

當並查集結構合併兩個群組時,它讓一個群組的根指向另一個的根。哪個根成為新的頂端,對樹的高度影響極大。按秩合併就是這條規則:總把較矮的樹的根掛在較高的樹的根之下。反過來做會把群組疊成又高又細的鏈;這樣做則讓樹維持矮而蓬鬆。

每個根帶有一個叫做秩的數,是樹高的保守估計。要合併兩棵樹,比較秩:秩較小的根成為秩較大的根的子節點,高度不變。只有當兩個秩相等時,存活的根的秩才加一。這條規則保證:根的秩為 r 的樹至少含 2^r 個節點——由歸納法證明,因為秩 r 的根只能由接合兩棵秩 r-1 的樹形成,每棵至少 2^(r-1) 個節點。反過來,n 個節點的樹高度至多 log n,所以不用任何其他技巧,每次 Find 本就花 O(log n)。「按大小合併」改比節點數而非秩,給出同樣的保證。

按秩合併是快速並查集的另一半,與路徑壓縮互補。兩個啟發法一起用,把每個操作的攤還成本一路推到 O(alpha(n)),即反阿克曼界——遠勝任一個單獨使用。誠實的細節:秩是高度的上界而非確切高度,且路徑壓縮可能使某節點的秩大於它的真實深度(秩從不減少),但這從不破壞界,因為分析只把秩當作上限使用。單靠按秩合併給出每操作 O(log n);近乎常數的界需要把它與路徑壓縮配對。

把一棵秩 2 的樹(>= 4 個節點)與一棵秩 1 的樹(>= 2 個節點)合併:秩 1 的根成為秩 2 根的子節點,總高度維持在秩 2 樹的高度,合併後的根保持秩 2。若你反而把較高的樹掛在較矮的根下,結果會無故多深一層。

把較矮的樹掛在較高的樹下使高度至多 log n,所以即使在路徑壓縮之前,Find 也花 O(log n)。

秩是高度的上界而非確切高度;路徑壓縮壓平樹卻不降低已存的秩,所以節點的秩可能超過它的真實深度。分析只把秩當上限倚靠,所以這從不使界失效。

又稱
union by sizerank heuristic按大小合併按秩聯集