Disjoint-Sets (서로소 집합)

서로소 집합 (Disjoint-Sets)

• 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들
• 집합에 속한 하나의 특정 멤버를 통해 각 집합을 구분 → 이를 대표원소(representative)라고 함
• 상호배타 집합을 표현하는 방법
  • 연결 리스트
  • 트리
• 상호배타 집합 연산
  • Make-Set(x)
  • Find-Set(x)
  • Union(x, y)

• 상호배타 집합 예시
  1. Make-Set(x)
  2. Make-Set(y)
  3. Make-Set(a)
  4. Make-Set(b)
  5. Union(x, y)
  6. Union(a, b)
  7. Find-Set(y) → return x (representative)
  8. Find-Set(b) → return a (representative)
  9. Union(x, a)

 

상호배타 집합 표현 - 연결리스트

• 같은 집합의 원소들은 하나의 연결리스트로 관리
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 지정
• 각 원소는 집합의 대표 원소를 가리키는 링크를 갖음

 

상호배타 집합 표현 - 트리

• 하나의 집합을 하나의 트리로 표현
• 자식 노드가 부모 노드를 가리키며 루트 노드를 대표원소로 지정

 

상호배타 집합에 대한 연산

• Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산

def Make_Set(x):
    p[x] = x

• Find_set(x) : x를 포함하는 집합을 찾는 연산

def Find_Set(x):
    if x == p[x]:
        return x
    else:
        return Find_set(p[x])

• Union(x, y) : x와 y를 포함하는 두 집합을 통합하는 연산

def Union(x, y):
    p[Find_set(y)] = Find_set(x)

 

• 문제점
  • 편향 트리일 경우, 대표 원소를 탐색하는 시간이 오래걸린다.
• 위의 문제를 해결하고 연산의 효율을 높이는 방법
  • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장
    • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 병합
  • Path compression
    • Find_Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 저장
• 랭크를 이용한 Union의 예

랭크를 이용한 Union에서 랭크가 증가하는 예

• Path compression의 예

 

효율을 높인 연산

• Make_Set

# p[x] : 노드 x의 부모 저장
# rank[x] : 루트 노드가 x인 트리의 랭크 값 저장
def Make_Set(x):
    p[x] = x
    rank[x] = 0

• Find_Set

def Find_Set(x):
    if x != p[x]:	# x가 대표원소가 아닌 경우
        p[x] = Find_Set(p[x])
    return p[x]

• Union

def Union(x, y):
    Link(Find_Set(x), Find_Set(y))
    
def Link(x, y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1