UNION-FIND 연산

서로소인 집합 표현

union과 find 연산

union과 find 연산의 분석

union 연산의 가중치 법칙

find 연산의 경로 압축

서로소인 집합 표현

트리를 이용한 집합 표현을 생각하여 보기로 한다. 집합의 원소는 모두 [eqn: 0, 1, cdots , n-1] 등 정수이고, 각 집합은 서로소(disjoint)이라고 가정한다. 두 집합의 교집합이 공집합이 될 때 두 집합을 서로소이라고 말한다. 아래에 집합 [eqn: S_1 = \{ 0, 6, 7, 8 \}], [eqn: S_2 = \{ 1, 4, 9 \}], [eqn: S_1 = \{ 2, 3, 5 \}]을 트리를 이용하여 표현하고 있다.

여기서 고려하고 있는 연산은 union과 find이다.

□ union(i,j) 연산은 두 집합 [eqn: S_i]와 [eqn: S_j]가 서로소일 때, [eqn: S_i cup S_j]를 구하여 하나의 집합으로 표현하는 연산이다.

□ find(i) 연산은 원소 [eqn: i]에 대해서 [eqn: i]를 포함하는 집합을 찾는 것이다.

union과 find 연산

집합 [eqn: S_1]과 [eqn: S_2]에 대한 UNION은 두 집합 중 하나를 표현하는 트리를 다른 트리의 부트리를 만드는 것으로 충분하다.

union 연산에서 집합 이름이 필요한 경우는 아래와 같이 루트가 집합 이름에 대한 포인터를 가지고 있으면 충분하다. 집합 이름이 필요 없는 경우는 루트가 나타내는 원소를 가지고 집합을 구별한다.

find 연산은 어떻게 구현할 수 있을까?

union과 find 연산의 분석

[eqn: n]개의 원소 [eqn: 0, 1, cdots , n-1]에 대해서 아래와 같이 union, find 연산이 수행되었을 때를 생각하여 보자.

union(0,1); find(0)

union(1,2); find(0)

union(2,3); find(0)

...

union(n-2,n-1); find(0)

최악의 경우에 아래와 같이 skewed 트리가 만들어질 수도 있다. union 연산이 상수 시간에 수행될 수 있다고 하더라도, [eqn: n-1]번의 find 연산의 합은 [eqn: O(n^2 )] 시간이 소요된다.

union 연산의 가중치 법칙

union(i,j) 연산에서 가중치 법칙(weighting rule)이란 트리 [eqn: i]의 노드 수가 트리 [eqn: j]의 노드 수보다 작으면 [eqn: i]의 루트를 [eqn: j]의 자식 노드로 만들고, 그렇지 않으면 [eqn: i]의 루트를 [eqn: j]의 부모 노드로 만든다. 앞에서 보인 연산들에 이 법칙을 적용하여 보기로 한다.

정리. 가중치 법칙에 따라 구성된 트리의 높이는 노드 수를 [eqn: n]이라 할 때 [eqn: lfloor log_2 n rfloor]을 넘지 않는다.

위 정리를 [eqn: n]에 대한 귀납법으로 증명하여 보시오.

find 연산의 경로 압축

find(i)를 수행할 때 [eqn: j]가 [eqn: i]에서 루트까지의 경로 상에 있을 때, [eqn: j]를 루트의 자식 노드로 만드는 것을 경로 압축(path compression)이라고 한다.

정리. 가중치 법칙과 경로 압축 법칙을 적용하여 union 연산을 [eqn: n-1]회, find 연산을 [eqn: m ge n]회 수행할 때의 시간 복잡도는 [eqn: O(m alpha(m,n))]이다. 여기서 [eqn: alpha(m,n)]는 Ackerman 함수의 역함수로 매우 천천히 증가하는 함수이다.