일지
알고리즘...101
niamdank
2022. 1. 11. 13:51
트리를 이용한 집합의 처리
연결 리스트를 이용한 집합의 처리보다 효율적인 방식으로 각각의 집합을 트리로 표현하는 방법이다.
기존의 트리와는 달리 자식 노드가 부모 노드를 가리키는 방식으로 표현된다.
이러한 방식을 사용하는 경우 두 집합을 합칠 때 단순하게 합치려는 노드의 루트가 기존 집합의 루트를 가리키도록 하면 된다.
연산의 효율성을 높이는 방법
- 랭크를 이용한 Union
각 노드에 자신의 서브 트리의 높이를 랭크(Rank)라는 이름으로 저장하고 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
- 경로 압축
FindSet 진행 시 중간에 만나는 모든 노드에 대해 루트를 직접 가리키도록 바꾸어 추후 FindSet을 할 때 경로의 길이를 줄이는 방법이다.
