티스토리 뷰

엄~청 짜기 쉽고 유용한 트리.

유니온 파인드 트리라고만 부르고 있었는데, 서로소 집합이라는 말이 더 나은거 같다. 


기본적으로 루트가 하나 있고, 이 루트를 parent로 가지는 노드가 주렁주렁 달린 트리이다.

두가지 연산을 지원하는데,

1. p의 루트를 부르는 find(p)

2. p와 q를 같은 집합에 넣는 union(p,q)


아무 생각없이 짜면

int parent[1000], size[1000];

void init(){
    for (int i=0; i<1000; i++) {
        parent[i] = i;
        size[i] = 1;
    }
}
int find(int p){
    if(parent[p] == p) return p;
    else return find(parent[p]);
}

void uni(int p, int q){
    p = find(p);
    q = find(q);
    parent[p] = q;
    size[q] += size[p];
}

이렇다.

이러면 쓰기는 편하지만 빠르지는 않다. (아마 원소 n개 넣으면 최대 O(n^2)..?)


하지만 개선할 수 있다.

* 1. 만약에 5 -> 4 -> 3 -> 2 -> 1 이런 식으로 트리가 달려있다 치자.

그러면 find(5)를 부르면 4번 정도를 거쳐서 1이 나올 것이다.

이럴 바에 그냥 parent[5] = 1로 압축을 해주면 한번에 갈텐데..


그래서, find(p)를 부를 때 압축까지 해줄 수 있다.


int find(int p){
    if(parent[p] == p) return p;
    else return parent[p] = find(parent[p]);
}

이렇게 하면, parent[5] = parent[4] .... = 1로 경로를 압축해 줄 수 있다.


* 2. 얘도 트리다 보니까 편중되는 (skewed) 것을 막을 수가 없다.

이진 탐색 트리하고 비슷한데, 해결책은 두가지가 있다.


1. 근본적인 해결책이다. rank를 만들어서 그 트리의 깊이를 대략 저장한다. (완벽하게 저장하진 않는다.)

int parent[1000], size[1000], rank[1000]; void init(){ for (int i=0; i<1000; i++) { parent[i] = i; size[i] = 1; rank[i] = 0; } } void uni(int p, int q){ p = find(p); q = find(q); if(rank[p] < rank[q]) parent[p] = q, size[q] += size[p]; else parent[q] = p, size[p] += size[q];; if(rank[p] == rank[q]) rank[p]++; }

여기서 rank는 트리의 크기는 아니더라도 트리의 크기에 비례하는 값들이다. (rank가 높으면 작은 걸로 반대로 알았음 ㅠㅠ 늦게나마 수정합니다.) 작은 애들을 큰 애에 옮겨 주는 것이 이득이리라.

rank 대신 size를 써도 똑같은 효과를 볼 수 있다.


2. 이진 탐색 트리의 Treap과 비슷한 방법이다.

야매에 가까우니 까먹었을때만 쓰자

int parent[1000], size[1000];

void uni(int p, int q){
    p = find(p);
    q = find(q);
    if(rand()&1) parent[p] = q, size[q] += size[p];
    else parent[q] = p, size[p] += size[q];;
}

처음 들었을 때 약간 벙쪘던 방법인데.. 뭐. 안될건 없지 않는가.

1번 방법을 까먹었을 때 유용하지만. 1번 방법이 뭐 레드 블랙 트리 구현하는 것도 아니고.. 그냥 알아만 두자.


서로소 집합의 시간복잡도를 설명할때는 생전 처음 보는 기호가 등장한다.

인데, 에커먼 함수의 역함수이다.

저게 얼마나 작냐면 거의 10^10000000 정도의 n이 들어와도 4밖에 안되고, 보통 10만 정도 들어오는데 이때도 4다.

아마 이진 탐색 트리에 붙어있는 계수보다도 작을 듯.

그래서 보통은 union. find 연산 모두 O(1)으로 간주한다. 계산할때도 그렇게 계산하면 된다.


만약에 연습해보고 싶으면

 * 최소 신장 트리 구해보기 (Kruskal Algorithm) 아마 프림 알고리즘에는 손도 안 대게 될 것이다. 구현하기 매우 편하다.

* http://koistudy.net/?mid=prob_page&NO=962

* https://www.acmicpc.net/problem/2463

를 풀어보는 것을 추천한다.

댓글
  • 프로필사진 Cloge Union-find tree에서
    rank가 작은 쪽이 큰 쪽 아래로 들어가야 하는 것 아닌가요?
    그렇게 할 경우에 편향되지 않고 큰 쪽의 rank로 유지되지 않나요?

    if(rank[p] > rank[q]) parent[p] = q, size[q] += size[p];
    else parent[q] = p, size[p] += size[q];
    if(rank[p] == rank[q]) rank[q]++;

    -->
    if(rank[q] > rank[p]) parent[p] = q, size[q] += size[p];
    else parent[q] = p, size[p] += size[q];
    if(rank[p] == rank[q]) rank[p]++;
    2015.11.04 10:14
  • 프로필사진 구사과 늦은 답변 죄송합니다.

    작성할 때 실수가 있었던 거 같습니다. (전 랭크를 써서 코딩한 적이 없어서..)
    해당 부분 수정하겠습니다.

    지적해주셔서 감사합니다.
    2015.11.08 11:45 신고
  • 프로필사진 알려주세요 rank 말고 사이즈가 큰쪽에 merge 시키는 방법을 써서 편중을 막을 수 있을 것 같은데, 굳이 rank를 쓰는 이유가 머죠 2016.10.15 21:52
  • 프로필사진 구사과 rank compression + path compression을 합치면 ackermann(n) 이 보장 되기 때문으로 알고 있습니다. size compression + path compression을 합쳤을 때 ackermann(n)이 보장된다는 말은 들어본 적이 없네요.

    문제 풀이에서는 뭘 쓰든 상관없습니다. size compression만 써도 lgN이 보장되는 게 맞습니다.
    2016.10.17 16:26 신고
  • 프로필사진 카제비 ㅎㅇ 2018.02.25 14:37
  • 프로필사진 구사과 아기제비!! 2018.03.03 22:43 신고
댓글쓰기 폼
공지사항
Total
638,014
Today
106
Yesterday
451