BBST / union-find

BBST

motivation : BST가 균형이 안맞으면 점차 연결리스트나 다름 없어짐

 

example

AVL tree, Red-black Tree

 

union-find

disjoint set을 효율적으로 구현하는 자료구조

 

최적화

motivation : 균형이 안맞으면 점차 연결리스트나 다름 없어짐

 

모든 현실적인 입력에 대해 상수 시간에 작동

class UnionFind():
    def __init__(self, maxSize = 100):
        self.parent = [i for i in range(maxSize)]
        self.rank = [0]*maxSize
    
    # 루트 노드를 반환
    def find(self, a):
        if a == self.parent[a]: return a
        self.parent[a] = self.find(self.parent[a])
        return self.parent[a]
        
    # 두 집합을 합친다
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return
        
        if self.rank[ra] > self.rank[rb]:
            ra, rb = rb, ra
        
        # 이제 rank[ra] <= rank[rb] 가 무조건 성립한다.
        self.parent[ra] = rb
        if self.rank[ra] == self.rank[rb]:
            self.rank[rb] += 1

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현