[자료구조] 트리 - 분리 집합

분리 집합(Disjoint Set)

• 집합의 정의 : 특정 조건에 맞는 원소의 모임
• 분리 집합(Disjoint Set) : 서로 공통된 원소를 갖지 않는, 즉 교집합을 갖지 않는 복수의 집합
  • 분리 집합의 개념은 2개 이상의 집합을 일컬을 때만 사용할 수 있음
• 분리 집합은 교집합을 허락하지 않기 때문에 소속 관계가 분명해야 하는 데이터를 다룰 때 아주 유용함
  • ex) 도서 판매 관리 프로그램에서 일반 도서 집합과 베스트셀러 집합을 만들고, 베스트셀러들의 BookPrice가 베스트셀러 집합의 원소가 되도록 함
• 이처럼 분리 집합은 원소 또는 개체가 '어느 집합에 소속되어 있는가?'라는 정보를 바탕으로 무언가를 하는 알고리즘에 응용할 수 있음

분리 집합 표현

 

• 보통의 트리와 이진 트리는 부모가 자식을 가리키는 포인터를 갖고 있음
• 분리 집합은 이와 반대로 자식이 부모를 가리킴
• 뿌리 노드는 집합 그 자체이고, 뿌리 노드 자신을 포함한 트리 내의 모든 노드는 그 집합에 소속됨
  • 연결 리스트에서 헤드 노드가 연결리스트를 나타낸다는 점을 떠올려 이해해보면 도움이 됨
• 분리 집합 노드의 구조체
  • 자식 노드에 대한 포인터는 존재하지 않음
  • 부모 노드에 대한 포인터만 있음
  • 뿌리 노드는 부모 노드가 없으므로 Parent가 NULL임
  • Data 필드를 void* 형으로 선언한 이유는 어떤 자료형의 데이터든 입력 받을 수 있게 하기 위해서임

typedef struct tagDisjointSet {
    struct tagDisjointSet* Parent;
    void*                  Data;
} DisjointSet;

분리 집합의 기본 연산

• '합집합'과 '집합 탐색 연산'을 기억하자
  • 분리 집합의 목적은 원소가 어느 집합에 귀속되어 있는지 쉽게 알아내는 데 있음

합집합 연산

• 합집합(Union) : 두 집합을 더하는 연산
• 한 집합의 뿌리 노드를 다른 집합의 뿌리노드의 자식으로 만들면 됨

void DS_UnionSet( DisjointSet* Set1, DisjointSet* Set2 ) {
    Set2 = DS_FindSet(Set2);
    Set2->Parent = Set1;
}

집합 탐색 연산

• 분리 집합의 탐색(Find)은 집합에서 원소를 찾는 것이 아니라 원소가 속한 집합을 찾는 연산임.
• 집합 내 어떤 노드에게든 트리의 최상위에 있는 뿌리 노드가 곧 자신이 속한 집합을 나타내므로, 원소(노드)가 어떤 집합에 속해 있는지 알려면 이 원소가 속한 트리의 뿌리 노드를 찾으면 됨
• 각 노드는 '부모' 노드를 가리키는 포인터를 가지고 있기 때문에, 이 포인터를 타고 쭉 올라가면 부모가 NULL인 뿌리 노드를 만날 수 있음
  • 이 뿌리 노드는 곧 집합을 나타내므로, 이것을 반환하면 해당 노드가 소속된 집합을 반환하게 되는 것

DisjointSet* DS_FindSet( DisjointSet* Set ) {
    while ( Set->Parent != NULL )
    {
        Set = Set->Parent;
    }

    return Set;
}

집합 생성/소멸

• 집합 생성

DisjointSet* DS_MakeSet( void* NewData ) {
    DisjointSet* NewNode = (DisjointSet*)malloc(sizeof(DisjointSet));
    NewNode->Data   = NewData;
    NewNode->Parent = NULL;

    return NewNode;
}

• 집합 소멸

void DS_DestroySet( DisjointSet* Set ) {
    free( Set );
}

분리 집합 예제 프로그램

int main( void ) {
        int a=1, b=2, c=3, d=4;
        DisjointSet* Set1 = DS_MakeSet(&a);
        DisjointSet* Set2 = DS_MakeSet(&b);
        DisjointSet* Set3 = DS_MakeSet(&c);
        DisjointSet* Set4 = DS_MakeSet(&d);

    printf("Set1 == Set2 : %d \n", DS_FindSet( Set1 ) == DS_FindSet( Set2 ) );

        DS_UnionSet( Set1, Set3 );
    printf("Set1 == Set3 : %d \n", DS_FindSet( Set1 ) == DS_FindSet( Set3 ) );

    DS_UnionSet( Set3, Set4 );
    printf("Set3 == Set4 : %d \n", DS_FindSet( Set3 ) == DS_FindSet( Set4 ) );

        return 0;
}

참조) 박상현, 『이것이 자료구조+알고리즘이다 with C언어』, 한빛미디어(2022)