Union-Find(3) : Quick Union

Quick-union [lazy approach]

• 이번엔 id 배열이 인덱스별로 root 노드를 가리키고 있습니다.
  여기서 인덱스와 id 배열의 값이 동일한 것은 자기 자신이 곧 노드라는 뜻입니다.
  따라서 p와 q가 연결되어 있는지는 두 노드의 root 노드가 동일한지를 비교하면 됩니다.
• root 노드를 찾아가는 과정은 재귀적입니다.
  root 노드의 root가 자기 자신이 될 때까지 과정을 반복하게 됩니다.
• 여기서 id 배열의 값을 업데이트 할 때는 관련된 모든 값을 변경할 필요가 없습니다.
  단지 child가 되는 node의 root를 변경해주면 되는 것입니다.
• 마찬가지로 python 코드로 구현한 결과물은 다음과 같습니다.

class Quick_Union_UF(n):
    id = [x for x in range(n)]
    
    def root(i):
        while i != id[i]: # 자기 자신이 root가 될 때까지
            i = id[i]
        return i
    
    def connected(p, q): # root 같으면 True
        return root(p) == root(q)
    
    def union(p, q): # 자식, 부모
        i, j = root(p), root(q)
        id[i] = j

 

Quick-union is also too slow

• Quick-find가 너무 비효율적이라는 것과 마찬가지로 Quick-union도 닉값을 하지 못합니다.
  엄청 느리다는 뜻이죠.
• 최악의 경우에는 탐색을 수행하는데 n개의 object를 다 뒤져야 할수도 있습니다.
  트리가 세로 일자로 쭉 늘어지는 경우가 그러하겠죠.
  맨 밑의 child 노드의 root node(이것은 맨 위에 있다면)까지 선형 탐색(n)을 하게 될 것입니다.
• 따라서 find / union 둘 다 개선이 필요한 알고리즘이라고 볼 수 있습니다.

 

출처: Coursera, Algorithms, Part 1, Princeton University