Clean Code hochulshin.com

Data Structure - disjoints-set

2015-08-06

집합을 자료구조 중 array를 이용해 만드는 disjoints-set을 이해해 보자.

자료 구조

int parent[MAX_LENGTH];

makeset(x)

유일한 멤버 x를 포함하는 집합 만드는 함수이다. 초기화 함수로 모든 멤버들을 각기 독립적인 set으로 만든다.

makeset(x)
  parent[x] = x; 

findset(x)

x를 포함하는 집합(정확히 말하면 집합의 root parent index)를 찾는 함수이다.

findset(x)
   if x == parent[x] //root parent
      return x;
    else 
      return findset(parent[x]); //recursion

skewed tree가 되는 것을 막기위해 찾으면서 그 결과를 이용해 tree를 평탄화시키는 것은 아래와 같다.

findset(x)
   if x == parent[x] //root parent
      return parent[x];
    else 
      return parent[x] = findset(parent[x]); //recursion 하며 결과로 자신의 parent를 갱신

unionset(x, y)

x와 y를 포함하는 두 집합을 합치는 함수이다.

union(x)
   parent[findset(y)] = findset(x);

두 개의 원소가 같은 집합에 속해 있는지 판단하기

findset(x)와 findset(y)가 같은 결과가 아니면 다른 집합이다.

isUnion(x, y)
  if findset(x) != findset(y)
    return false;
  return true;

기타

성능을 최적화하는 방법으로 집합을 union할때 높이가 낮은 쪽으로 연결되도록 rank를 사용하는 경우도 있다.


Comments