DataStructure : Union-Find

Algorithm_PS/Algorithm_Data Structure

DataStructure : Union-Find

Frisbeen 2024. 6. 5. 17:40

이런 서로 다른 트리들을 비교할때 어케해야할까의 고민
두 집합에 속한 원소들은 중복되지 않고, 순서도 특정된게 없으니 1차원배열에 싹 다 저장한다.
모든 집합의 원소 즉, 서로 다른 트리들의 원소를 0,1,2…,n-1로 넣으면 이를 1차원배열의 인덱스로 활용한다.
이런 서로 다른 트리들을 비교할때 어케해야할까의 고민
두 집합에 속한 원소들은 중복되지 않고, 순서도 특정된게 없으니 1차원배열에 싹 다 저장한다.
모든 집합의 원소 즉, 서로 다른 트리들의 원소를 0,1,2…,n-1로 넣으면 이를 1차원배열의 인덱스로 활용한다.

트리의 루트는 각 집합의 대표이다.

루트의 배열 원소에는 루트 자식을 넣는다. ( 루트와 루트 자식은 같은 인덱스값)

루트가 아닌 노드의 원소는 그 원소의 부모노드( 루트 아래아래 자식의 인덱스값은 자식의 부모값)

union 연산; 2개의 집합을 하나의 집합으로 만들자

기준은 rank이다. rank가 높은 루트가 union 후에도 합쳐진 트리의 루트가 된다. 즉 랭크가 높은놈이 승리
합쳐진 루트의 높이가 커지는 것을 방지 (이것이 랭크기반으로 하는 이유)
높이가 낮을수록 find 수행시간을 줄인다( find는 루트까지 가야하므로)

find 연산; 인자로 주어지는 x가 속한 집합의 대표 노드인 루트를 찾자.

경로압축

찾는것뿐만 아니라 find를 수행하면서 루트까지 올라가는 경로상의 노드의 부모 노드를 루트로 갱신. (경로압축)

즉 올라가면서 모든 노드의 부모를 루트로 공통 부모화 시킨다.

경로압축을 왜하는가. 당장 find의 시간은 줄지 않지만, 추후의 연산의 수행시간은 단축한다.

트리의 높이는 바뀌도, 트리의 랭크는 바뀌지 않는다?

이걸로 루트의 rank는 트리의 높이와 달라질수있다.

초기 상태:루트 노드 3의 랭크는 2노드 2는 3의 자식노드 4는 2의 자식find(4)를 호출하면:노드 4는 루트 노드 3과 직접 연결됩니다.트리 구조는 3 -> 2, 3 -> 4로 변경됩니다.이 경우 트리의 높이는 줄어들지만, 루트 노드 3의 랭크는 여전히 2로 유지됩니다.

따라서, 경로 압축을 통해 트리의 구조가 변경되더라도 루트 노드의 랭크는 변하지 않습니다. 이는 유니온-파인드에서의 효율적인 연산을 가능하게 합니다.

Class :: 두개를 합쳐보자. union & find —> UnionFind class

Node class

Public class Node{
	private int rank;
	private int parent
	
	public Node(int parent, int rank){
		this....
	}
	@GetSet
	
}

//TODO --> 혼자 구현해볼것
public class UnionFind {
    private Node[] arr;
    public UnionFind(Node[] arr){
        this.arr = arr;
    }

    private int find(int x){
        //내 자신이 내 부모, 즉 내가 루트라면
        if(x != arr[x].getParent()){
            //재귀
            arr[x].setParent(find(arr[x].getParent()));
        }
        return arr[x].getParent();
    }

    private void union(int x, int y){
        int xroot = find(x);
        int yroot= find(y);
        if(xroot== yroot){
            return;
        }
        if(arr[xroot].getRank() > arr[yroot].getRank()){
            arr[yroot].setParent(xroot);
        }
        else if(arr[xroot].getRank() < arr[yroot].getRank()){
            arr[xroot].setParent(yroot);
        }
        //둘의 rank가 같다면
        else{
            arr[yroot].setParent(xroot);
            int changedRank = arr[xroot].getRank()+1;
            arr[xroot].setRank(changedRank);
        }
    }
}

수행 시간.

union 연산 : find를 제외한 순수한 union 연산은 O(1).

find 연산 : 최대 트리의 높이만큼 올라가니, 트리의 높이에 비례

find를 하면서 경로 압축을 하기에, 경로상의 노드에 대해 추후 수행되는 find 연산은, 트리의 높이보다는 적게 소요

즉, find는 트리의 높이에 비례하는게 맞으나, 계속해서 하면 할수록 경로압축을 하기에 정확히 높이만큼 걸리지 않고, 그것보다는 적게 소요.