유니온파인드_UnionFind

Union-Find

• Disjoint Set을 표현할 때 사용하는 알고리즘
  • 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 집합을 구현하는데 비트벡터, 배열, 연결리스트를 이용할 수 있으나 그 중 효율적인 트리구조를 이용하여 구현

연산

• make-set(x)
  • 초기화
  • x를 유일한 원소로 하는 새로운 집합을 만든다.
• union(x,y)
  • 합하기
  • x가 속한 집합과 y가 속한 집합을 합친다.
• find(x)
  • 찾기
  • x가 속한 집합의 대표값(루트노드값)을 반환한다. x가 어떤 집합에 속해있는지 찾는 연산
• 전체 집합이 있을 때 구성 원소들이 겹치지 않도록 분할 하는데 자주 사용

최악의 상황

• 트리 구조가 완전 비대칭인 경우
• 연결리스트 형태
• 트리의 높이가 최대가 된다.
• 원소의 개수가 N일 때, 트리의 높이가 N-1이므로 union과 find(x)의 시간복잡도가 모두 O(N)
• 배열로 구현하는것보다 비효율적이다.