Union-Find(4) : Quick-Union Improvements

Improvement 1: weighting

• 기존의 quick-union의 속도 문제를 개선하기 위한 weighted quick-union입니다.
  • 더 큰 트리가 위에 위치합니다. 즉, 작은 트리가 아래에 위치합니다 → worst case를 방지할 수 있습니다.
  • 작은 트리의 루트를 큰 트리의 루트와 연결합니다.
• 우측의 그림은 기존의 union과 weighted 방식으로 개선된 union의 결과를 도식화 한 것입니다.

 

Weighted quick-union: Python implementation

class Weighted_Quick_Union_UF(n):
    id = [x for x in range(n)]
    sz = [1 for _ in range(n)] # tree 내 원소 개수
    
    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)
    	if i == j:
        	return
        if sz[i] < sz[j]: # q 트리가 더 크면
        	id[i] = j # q 트리가 부모
            sz[j] += sz[i] # q 트리 원소 증가
        else: # p 트리가 더 크면
        	id[j] = i
            sz[i] += sz[j]

 

Weighted quick-union analysis

• Find 명령은 p와 q의 깊이에 비례하여 시간이 걸릴 것입니다.
  한편 Union 명령은 루트에 따른 상수 시간이 걸립니다.
• 이전의 Quick Union과 비교했을 경우, 트리의 깊이가 아무리 깊어도 최대 logN입니다.
  (이때 log는 밑을 2로 갖는 log입니다)
  • 왜일까요? 만약 x라는 노드의 깊이가 한 층 더 깊어지려면, x가 속한 tree의 크기가 최소 2배 이상은 되어야 하기 때문입니다.
    예를 들어 x가 속한 T1의 크기가 3이라고 가정하죠.
    이때 이 트리가 속하게 될 T2의 크기는 적어도 6이상이어야 합니다. 그래야지만 T1이 T2에 속하면서 밑으로 들어가 X의 깊이가 증가하기 때문이죠.
    (아래 표를 참고해주세요)
• 따라서 훨씬 효율적인 알고리즘이라는 것을 알 수 있습니다.

x의 깊이	0	1	2	3	4	...	log N
tree의 크기	1	2	4	8	16	...	N

• 표에서 볼 수 있듯이 union, connected의 시간 복잡도가 log 단위로 내려가서 획기적으로 시간을 아낄 수 있습니다.

 

Improvement 2: path compression

• 노드 9를 예시로 든다면, 굳이 이것의 root를 6으로 둘 필요가 없습니다.
  이것의 최종 root인 0을 가리키도록 변경하면 깊이가 줄어들어 find 과정이 훨씬 효율적일 것입니다.
• 물론 이 과정이 굉장히 간단하게 진행되어야지만 기존보다 효율적이겠죠.

 

Path compression: Python implementation

class Weighted_Quick_Union_UF(n):
    id = [x for x in range(n)]
    sz = [1 for _ in range(n)] # tree 내 원소 개수
    
    def root(i):
        while i != id[i]: # 자기 자신이 root가 될 때까지
        	id[i] = id[id[i]] # 한 줄 추가!
            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)
    	if i == j:
        	return
        if sz[i] < sz[j]: # q 트리가 더 크면
        	id[i] = j # q 트리가 부모
            sz[j] += sz[i] # q 트리 원소 증가
        else: # p 트리가 더 크면
        	id[j] = i
            sz[i] += sz[j]

• 이번에도 파이썬으로 코드를 작성한 결과입니다.
  딱 한 줄이 추가되었고, 이를 통해 트리를 굉장히 평평(flat)하게 만들 수 있습니다.

 

Weighted quick-union with path compression: amortized analysis

• log * N은 N을 1로 바꾸기 위해 log N을 취해야 하는 횟수를 나타내는 함수입니다.
  이를 iterate log function(반복 로그 함수)라고 부릅니다.
• 따라서 이 알고리즘은 log * N만큼의 시간, 즉 (거의) 선형시간으로 바꾼 획기적인 알고리즘으로 평가하고 있습니다.

 

Summary

 

 

 

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