✅ 경로 압축 (Path Compression)

Find 연산 수행 시 트리 구조를 평평하게 만드는 방법.

루트 노드까지 순회 중 방문한 각 노드들이 직접 루트 노드를 가리키도록 하여 모든 노드들이 같은 대표 노드를 공유하도록 한다.

시간복잡도 : O(1)

✅ 유니온 바이 랭크 (Union by rank)

항상 작은 트리를 큰 트리 루트에 붙이는 방법.

여기서 작은 트리는 상대적으로 높이가 낮거나 사이즈가 작은 트리를 의미.

이 방법을 사용하기 위해서는 Rank 배열에 트리의 높이 또는 크기를 저장하여 이용한다

• Union by size : Rank 배열에 트리의 사이즈(=노드 수) 저장. Union 함수 실행 시 노드 수가 작은 트리를 큰 트리에 합침.
• Union by height : Rank 배열에 트리의 높이를 저장. Union 함수 실행 시 높이가 낮은 트리를 높은 트리에 합침.

➡ 사용 이유

: Union Find 연산은 최악의 경우 O(N(노드수)) 시간이 걸리는데 Union by Rank 와 경로 압축을 통해 O(logN) 까지 줄일 수 있다.

➡ 사용하는 경우

: 주로 크루스칼 알고리즘(Kruskal’s Algorithm) 구현 또는 그래프 사이클 탐지 시 사용.