유니온 파인드 Rank

유니온 파인드에서 ranks 배열을 사용하는 이유

• 트리의 높이를 최소화하고, find 메소드 연산의 효율성을 극대화 하기 위해서
  • 트리 높이 최소화 : 트리의 높이가 급격하게 증가하는 것을 방지할 수 있다. 더 빠르게 루트에 접근할 수 있습니다.
  • find 연산 효율성 향상 : 트리의 높이가 낮을수록 find 연산을 수행하는 데 필요한 시간이 줄어듭니다. 랭크를 사용하여 높이를 최소화함으로써, find 연산이 매우 빠르게 수행될 수 있습니다.

• 간단하게 높이를 파악해서 어떤 노드를 기준으로 합칠거냐를 결정하는데 사용됨
  

사용했을 때 와 하지 않았을 때 의 차이점

rank 배열을 사용하지 않았을 때 최악의 경우에 $O(N)$이 될 수 있다.

사용했을 경우 $O(α(n))$로 거의 상수 시간 복잡도와 비슷하다고 한다.

rank 배열 생성

먼저  rank 배열을 생성한다. 처음 초기값이 0인데 수정할 필요는 없다.
각 집합의 루트노드는 0이된다.

N = 4; // 노드의 개수
int[] ranks = new int[N];

rank 배열을 사용한 union 연산

    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) return;

        if (ranks[rootA] < ranks[rootB]) {
            parents[rootA] = rootB;
        } else {
            parents[rootB] = rootA; // rootB의 부모가 rootA가 된다.
            if (ranks[rootA] == ranks[rootB]) {
                ranks[rootA]++; // A가 B의 부모가 되어서 rank가 증가한다.
            }
        }
    } // End of union()

• 부모 노드 rank를 더 높인다.
  • 헷갈리지 말자 A노드가 B노드의 부모가 될 때, 그리고 A노드와 B노드의 높이가 같을 때 ranks[A]++ 이 된다.

       if (ranks[rootA] < ranks[rootB]) {
           
            parents[rootA] = rootB; // rootA가 속한 집합을 rootB가 속한 집합에 합치는 것을 의미한다.
        } else

parents[rootA] = rootB 구문은 rootA 노드의 부모를 rootB로 설정하는 것을 의미합니다. 즉, 이 연산을 통해 rootA가 속한 집합이 rootB가 속한 집합의 하위 집합으로 합쳐지게 됩니다.
이로써 rootB가 rootA를 포함한 집합의 새로운 루트 노드가 됩니다.

        } else {
            parents[rootB] = rootA; // rootB의 부모가 rootA가 된다.
            if (ranks[rootA] == ranks[rootB]) {
                ranks[rootA]++; // A가 B의 부모가 되어서 rank가 증가한다.
            }
        }

여기서는 parents[rootA] 의 높이가 더 높거나 같은 경우입니다.
rootB의 부모를 rootA가 설정한다.

결론

• rank 배열을 사용하면 데이터가 많을 때 최적화가 가능하다

• 랭크가 낮은 트리를 랭크가 높은 트리로 합친다

• 높이가 같을 경우 합쳐지는 쪽 부모 노드의 높이를 증가시킨다.