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): whil..

원문링크 : Union-Find(4) : Quick-Union Improvements