13주차 - 상호 배타적 집합의 처리

상호 배타적 집합

종류

연결 리스트 / 트리를 이용해 처리함

트리를 이용해 처리하는 방식이 더 효율적임

본 포스트에서는 연결 리스트를 이용한 집합의 연산은 생략함

트리를 이용한 집합의 처리 방법

• 같은 집합의 원소들은 하나의 트리로 관리함
  • 자식 노드가 부모 노드를 가르킴
• 트리의 루트를 집합의 대표 원소로 삼음

종류

• Make-set
  • x만 원소로 가지는 집합을 만드는 연산
• Find-set
  • x가 속한 집합을 알아내기 위한 연산
• Union
  • 집합 x, y를 합치는 합집합 연산