union find는 disjoint set이라고도 불리우는 자료구조로 흔히 집합의 포함관계를 표현하는데 사용되며, 대단히 빠른 시간 안에 소속 여부를 판단할 수 있다. 유니온 파인드는 크게 3가지 요소로 구성되는데, 부모를 표현하기 위한 메모리(테이블), 유니온 함수, 파인드 함수가 바록 그것이다.
유니온 파인드 구조 내에서 각 원소들은 hierachical한 트리의 형태로 구성된다. 여기서 일반적인 트리와 다른 점이 있다면, 자식 노드가 부모 노드를 가리킨다는 점이다. 테이블을 통해서 부모의 부모를 거듭해서 찾다 보면 최종적으로 자기 자신을 가리키는, 트리의 root에 도달하게 되는데, 이 루트 노드의 값으로 소속 관계를 식별한다. 여기서 테이블은 각 원소의 부모를 저장하는 역할을 맡는다.
파인드 함수는 테이블을 재귀적으로 참조하며, 최종적으로는 해당 노드가 속한 트리의 루트 노드를 반환한다. 루트 노드는 트리에서 단 하나만 존재한다는 점을 통해서 각 노드가 서로 다른 트리에 속해있는지를 판단할 수 있다.
유니온 함수는 트리에 노드를 추가하는 역할을 한다. 일반적으로 테이블에 자기 자신과 부모를 쌍으로 하는 엔트리를 추가하는 방식으로 구성된다.
union 알고리즘의 시간 복잡도는 테이블에 단순히 등록만 하면 끝이기에 O(1)이라 할 수 있다. 하지만, find 알고리즘의 시간 복잡도는 트리가 어떤 방식으로 구조화 되었느냐에 따라 결정된다. 따라서 최악의 경우는 모든 노드가 트리 내에서 선형으로 연결되는 형태이며, 이 때 find는 O(N)의 시간 복잡도를 갖는다. 즉, 유니온 파인드의 명성에 무색하게 생각보다 부족한 성능을 보이며, 이를 극복하기 위해서 다음의 구조가 등장했다.
앞서 find 알고리즘의 성능이 트리의 모양, 깊이에 따라서 결정됨을 알았다. 이를 해결하기 위해서 등장한 방법이 바로 union by rank이다. 이 방식은 트리의 깊이가 증가하는 것을 방지하고자 고안되었다. 먼저 트리를 대표하는 루트 노드에게 해당 트리의 깊이를 음수값으로 저장한다. 음수값으로 저장하는 이유는 스스로가 루트 노드임을 구분하기 위해서이다.
유니온 과정에서 트리의 깊이가 증가하는 것은 상대적으로 짧은 트리에 긴 트리를 붙이기 때문이다. 만약 긴 트리에 짧은 트리를 붙인다면, 길이의 증가량이 없거나, 있더라도 그 증가량이 상대적으로 다를 것이다. 따라서 union과정에서 루트 노드가 저장하는 rank(트리의 깊이)를 확인하고, 이를 바탕으로 깊은 트리에 얕은 트리를 붙이도록 유도하여 트리의 깊이가 증가하는 것을 방지한다.
경로 압축은 보다 직접적으로 트리의 깊이를 줄이는 방법이다. 간단하게 말하면, find의 대상이 되는 노드와 그 조상 전부를 루트의 자식 노드로 입양시키는 것이다.
find를 수행하는 과정에서는 필연적으로 트리를 거슬러 오르며 root의 값을 찾는 과정이 수반된다. 여기에 재귀를 이용하면 최초의 탐색 대상과, 그 부모들은 모두 자신의 root가 어떤 값인지를 알게 된다. 따라서 우리는 탐색 과정에서 만나는 모든 조상 노드의 부모를 root로 초기화 할 수 있다.
Union by rank를 통해서 트리를 균형된 형태로 발전시킬 수 있으며, Path Compression을 통해서 한 번 탐색한 노드에 대해서는 탐색 시간을 극단적으로 줄일 수 있다. 따라서 최악의 경우 O(log N), 최선의 경우 O(1)을 달성할 수 있다.