집합

상호배타적 집합의 처리

• 이 포스트에서는 상호배타적 집합만을 대상으로 한다. 그러므로 교집합은 없다.
• 지원할 연산
  • Make-Set(x): 원소 x로만 이루어진 집합을 만든다.
  • Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다.
  • Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합의 합집합
• 집합을 표현하는 대표적인 2가지 방법
  • 연결리스트 (linked list)를 이용하는 방법
  • 트리를 이용하는 방법

---

1. 연결 리스트를 이용한 처리

• 같은 집합의 원소들은 하나의 연결 리스트로 관리한다.
• 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.

하나의 원소로 이루어진 집합

• 대표원소로 본인을 가리키고, 다음 노드를 가리키고 있지 않다.

연결 리스트로 된 두 집합

• 여러 원소를 가진 집합은 위와 같이 표현할 수 있다. 각 원소들은 대표원소를 가리키고 있고, 서로 링크드리스트로 연결되어 있다.
• 이때, 두 집합을 합치게 되는 경우, 적은 수의 원소를 가진 집합을 다른 한 집합의 뒤에 합치는 것이 효율적이다.

• 연결리스트로 된 두 집합을 합칠 때, 작은 집합을 큰 집합의 뒤에 붙인다. (포인터 갱신 작업을 최소화)

---

2. 트리를 이용한 처리

• 같은 집합의 원소들은 하나의 트리로 관리한다.
  • 자식 노드가 부모 노드를 가리킨다. (보통은 부모노드가 자식노드를 가리킴)
• 트리의 루트를 집합의 대표 원소로 삼는다.

트리로 이루어진 집합

• 자식이 부모를 가리키고, 루트 노드는 자신을 가리킴

• 두 집합을 합치게 되는 경우, 한 집합의 루트 노드를 다른 집합의 루트 노드를 가리키게 함으로써 두 집합을 합친다.

---

집합의 연산을 위한 함수

Make-set()

Make-Set(x) { // 노드 x를 유일한 원소로 하는 집합을 만든다.
    p[x] <- x;
}

Union(x,y)

Union(x, y) { // 노드 x가 속한 집합과 노드 y가 속한 집합을 합친다.
    p[Find-Set(y)] <- Find-Set(x);
}

Find-Set(x)

Find-Set(x) { // 노드 x가 속한 집합을 알아낸다.
	      // 노드 x가 속한 트리의 루트 노드를 리턴한다.
    if ( x== p[x]) then return x;
    	else return Find-Set(p[x]);
}

---

집합을 합치는 연산의 효율을 높이는 방법

• 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크 (Rank)라는 이름으로 저장한다.

연산의 효율을 높이는 방법
1. 랭크를 이용한 Union
: 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
트리의 깊이를 낮게 유지하기 위한 방법.

2. 경로 압축
   : Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾸어준다.

랭크를 이용한 Union의 예

• 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
  이를 통해 트리의 깊이를 낮게 유지하고, 이는 연산하는 속도를 높인다.

랭크를 이용한 Union에서 랭크가 증가하는 예

• Union을 하였을 때, 결과 집합의 랭크가 증가하는 경우도 있다.
  합치고자 하는 두 집합의 랭크가 동일 할 때, 합쳐진 집합의 랭크는 이전의 랭크+1의 값을 가지게 된다.

경로 압축

• 랭크를 낮게 유지하기 위해 랭크를 압축하는 경우가 있음

Find-Set(g)의 연산과정에서 g의 원소 그리고 g의 원소와 연결되어 있는 원소가 대표원소를 가리키게 한다.

랭크를 이용한 Union과 Make-Set

Make-Set()

Make-Set(x) { //  노드 x를 유일한 원소로 하는 집합을 만든다.
    p[x] <- x;
    rank[x] <- 0;

Union(x, y)

Union(x,y) { // 노드 x가 속한 집합과 노드 y가 속한 집합을 합한다.
    x' <- Find-Set(x);
    y' <- Find-Set(y);
    if ( rank[x'] > rank[y'])
    	then p[y'] <- x';
    else {
        p[x'] <- y;
        if (rank[x'] = rank[y'])
            then rank[y'] <- rank[y'] + 1;
    }
 }

경로 압축을 이용한 Find-Set

Find-Set(x) { // 노드 x가 포함된 트리의 루트를 리턴한다.
    if (p[x] != x ) then p[x] <- Find-Set(p[x]);
    return p[x];
}