서로소 집합 자료 구조 (Union-Find Data Structure)

 

 

지난주 Leetcode Daily Problem의 테마는 Disjoint Set을 사용하는 문제가 많이 나왔었다. 그래서 이번에 개념을 확실히 정리해두려고 .

 

Disjoint Set

---

두 개의 겹치치 않는 집합(Set) 이 있다. 이런 집합을 Disjoint set이라고 부른다.

 

즉 공통 원소(Common Element)가 존재하지 않는 부분 집합(Subset)의 집합을 말한다. 그리고 Disjoint Set을 표현하기 가장 좋은 자료구조 중 하나가 Union-Find 자료구조다.

 

Union-Find

---

그럼 Union-Find 자료구조는 어떻게 Disjoint Set을 표현할까요?

 

제일 먼저 Union-Find는 보통 Tree 방식으로 표현이 됩니다. 그리고 세 가지 연산을 이용해서 Disjoint Set을 만들어갑니다.

 

첫번째로는 Make-set(x) 입니다. 이 연산을 통해서 Union-Find의 자료구조를 초기화 시키게 되죠. Pseduocode로 표현하게 되면 아래와 같이 표현할 수 있습니다. 

function MakeSet(x) is
    if x is not already in the forest then
        x.parent := x
        x.size := 1     // if nodes store size
        x.rank := 0     // if nodes store rank
    end if
end function

 

두번째로는 Find(x) 입니다. 원소 x가 속한 집합의 대표 값(Parent or Root)을 반환하는 연산입니다. 재귀나 반복문으로 표현할 수 있는데, 연산 속도를 고려한다면 반복문을 사용하는게 훨씬 빠릅니다. 

function Find(x) is
    if x.parent ≠ x then
        x.parent := Find(x.parent)
        return x.parent
    else
        return x
    end if
end function

 

위 연산의 경우에는 경로 압축(Path Compression)으로 최적화 되어있는 상태입니다. 경로 압축이란 Child인 원소들이 Root 노드를 바라보게 함으로서, Tree의 재귀 호출을 최대한 줄이려고 하는 방식입니다.

 

이 방식을 통해서 Union-Find의 Time Complexity는 O(log N)으로 줄어들게 됩니다.

 

 

마지막으로는 Union(x, y)입니다. 이 연산을 통해서 x가 속한 집합에 y가 속한 집합을 합칩니다. 즉 두 개의 집합을 합치는 연산입니다.

function Union(x, y) is
    // Replace nodes by roots
    x := Find(x)
    y := Find(y)

    if x = y then
        return  // x and y are already in the same set
    end if

    // If necessary, swap variables to ensure that
    // x has at least as many descendants as y
    if x.size < y.size then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // Update the size of x
    x.size := x.size + y.size
end function

 

Union을 통해 합쳐진 집합은 하나의 Root를 공유함으로서 한 개의 집합으로서 여겨집니다. 

 

그리고 이 Union 또한 Tree의 높이를 이용한 최적화가 적용되어 있는데요. 두 집합 중 높이가 더 높은 Tree 밑에 낮은 Tree를 자식으로 집어넣음으로써, 트리가 한쪽으로 Skewed(편향)되는 것을 막고 Balanced Tree(균형 트리) 형태로 만들어갈 수 있습니다. 아래 이미지를 참고하면 어떻게 트리가 최적화가 되는지 더 Clear하게 확인 할 수 있습니다.

 

 

왼쪽이 Height이 없는 경우 오른쪽이 Height을 사용한 경우입니다.

 

Reference

---

https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

https://www.geeksforgeeks.org/dsa/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/

Introduction to Disjoint Set (Union-Find Data Structure) - GeeksforGeeks

https://tutorialhorizon.com/algorithms/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/