경로 압축과 순위에 의한 결합은 서로 어떻게 보완합니까?

Question

나는 노동 조합 발견 문제에 대해 읽었습니다. 두 가지 주요 개선점은 경로 압축과 순위 별 조합입니다. 늘어나는만큼 나무를 결합하는 방법을 결정하는 데는 계급 별 조합을 이해합니다. 두 개의 분리 된 트리 T1과 T2가있는 경우 더 높은 순위의 트리에 작은 순위의 트리 루트를 연결합니다. 경로 압축을 사용하지 않으면 순위는 트리의 깊이에 불과합니다. 이는 나무의 깊이를 늘리려는 것이 아니기 때문에 찾기와 합집합에 직접 영향을주기 때문에 의미가 있습니다.

내 문제는 경로 압축을 사용할 때도 마찬가지입니다. 나는 두 최적화가 서로를 보완한다는 것을 계속 읽었지만 나는 그것을 보지 못했다. 경로 압축 때문에 순위는 더 이상 트리의 깊이가 아닙니다 (깊이의 상한이됩니다). T1에 2 개의 브랜치 (T1의 순위를 3으로 함)가 있고 T2의 깊이에 2와 2의 순위가 있다고 가정 해 보겠습니다. 아래에 "*"가 표시된 T1의 잎에서 찾기 연산 (경로 압축 포함)을 수행한다고 가정합니다. 이제 우리가 T1의 루트와 T2의 루트를 합친다면, T2는 T1의 루트에 연결될 것입니다 (순위는 find에 의해 갱신되지 않기 때문에). 결과 트리는 깊이가 3입니다. 그러나 T2에 T1을 연결하면 성능이 향상 될 수 있습니다. T1 ("*")의 잎에 발견 후

T1: o (Rank = 3) T2: o (Rank = 2) 
    /\      | 
    o o      o 
    |       | 
    o       o 
    | 
    * 

, 우리는

T1: o  (Rank = 3)  T2: o (Rank = 2)  
    /| |\       | 
    * o o o      o 
            | 
            o 
Result of T1 union T2 
     o 
/| | |\ 
    * o o o o Rank = 3 and Max Depth = 3 
      | 
      o 
      | 
      o 

을 얻을 노동 조합 T1 및 T2의 뿌리에 내가 여기서 뭔가를 놓치고 있습니까? 순위에 의한 경로 압축과 결합은 어떻게 서로 보완합니까? 순위는 나무의 깊이에 대한 상한선이지만 계급 별 조합이 구조의 전반적인 성능을 향상시키는 방법을 알지 못합니다. 이것은 뿌리를 무작위로 결합한 조합보다 어떻게 더 좋은가?

미리 도움을 주셔서 감사합니다.

Answer 1

조합은 트리의 최대 깊이가 로그 N임을 보장하므로 모든 작업에서 최악의 경우 O (로그 N)의 상한을 설정합니다. 특별한 조합이없는

경로 압축 (N 로그)에 에 각 작업의 비용을 상각,하지만 최악의 경우가 비용 제한하지 않습니다 O의 상한 규칙. (상각 된 비용에 더 엄격한 한계가있을 수 있지만 O (log N)은 증명 방법을 알고 있습니다.)

두 가지를 함께 사용하면 최악의 경우 O (log N) 제한이 적용됩니다 상각 된 결합은 O ((N))으로 향상되며, 이는 사실상 일정하다. 이 방법으로 두 최적화가 보완 적입니다.

계급 별 조합이 절대적으로 최적은 아니지만 보장없이이 보장없이 작동하는 일련의 작업이 있다는 것이 맞습니다. 그게 중요합니다. 일반적으로 사례 실적을 최적화하기 위해 노력하지 않습니다. 은 최악의 경우 또는 의 평균은입니다.