이번에는 FIND와 UNION 연산의 성능을 향상시켜 보겠습니다. 다음 그림을 보세요.

▲ 그림 13-14 분리 집합 3

그림 13-14를 보면, 이전 배열에서는 루트 노드의 parent[i] 값이 단순히 -1이었습니다. 이번에는 루트 노드 값이 음수이기는 음수이되 그 절댓값이 집합에 있는 노드 개수를 나타내도록 바꾸었습니다. 예를 들어 {1, 2, 4} 루트 노드 2의 parent[2]=-3입니다. 절댓값을 씌우면 3이 나오므로 집합에 있는 노드 개수는 3인 것입니다. FIND 연산의 성능을 향상시켜 보겠습니다.

그림 13-15를 보면 왼쪽보다는 오른쪽이 트리 높이가 낮으므로 유리하겠지요?

▲ 그림 13-15 collapsing find