[자료구조] 11. 분리집합

공부 날짜: 2021 . 10 . 20 

 

분리집합(Disjoint Set): 서로 공통된 원소를 갖지 않는 집합(교집합이 공집합). 두개 이상의 집합을 일컬을 때만 사용할 수 있는 개념.

원소가 어느 집합에 귀속되어 있는지를 쉽게 알아낼 수 있도록 하는 것이 목적. 

 

유용:

-서로 구분되어야 하는 데이터 집합을 다룰 때 

 

집합탐색: 어떤 한 원소가 소속되어 있는 집합을 알아내는 연산. 

 

특징: 자식이 부모를 가리키는 포인터를 갖고 있다. 

분리집합의 연산: 합집합/ 집합 탐색 

-합집합

: 루트노드가 다른 집합의 루트노드를 부모로 가리키게 만들면 된다. 

-집합탐색

:원소가 속해 있는 집합을 찾는 연산. 해당 원소가 속해 있는 트리의 루트 노드를 찾으면 됨.