트리의 높이가 계산 효율의 주된 장애물이기 때문에, 짧은 트리의 루트가 긴 트리의 루트를 가리키는 것이 좋은 전략입니다.두 개의 지시 트리를 병합 하시겠습니까?
이 은 실제로이 중요합니까? 내 말은 다른 방법으로하면 (길이가 긴 나무를 더 짧게 합치면) 나무 높이가 1 씩 증가합니다. 1의 증가가 실제 차이를 만들지 않으므로 (중요할까요?), 정말로 중요합니까? 어떤 나무가 합쳐 졌습니까? 아니면 더 짧은 트리가 더 오래 병합되는 이유에 대한 또 다른 이유가 있습니까?
참고 분리형 세트에 대해 이야기하고 있습니다.
당신이 말하는 트리의 종류 (이진 검색 트리, 분리 된 세트 또는 임의 트리)는 분명하지 않습니다. 하지만 어쨌든 이유는 1의 증가가 중요하지 않지만 n 합병을 수행하면 결국 n의 증가로 끝난다 고 생각합니다. 합병이 많이 필요한 데이터 구조 (예 : 분리 집합)가있는 경우 중요 할 수 있습니다.
문구가 부족합니다. 예를 들어, 일부 트리 구조에서는 하나의 엘레멘트를 하나씩 삽입해야 할 수 있습니다 (예 : 트리 재조정 - 일반적으로 높이 O (log n)의 트리를 원함). 어쩌면 이것이 의미하는 것입니다 : 그러면 더 큰 트리에 더 적은 수의 요소를 삽입하는 것이 더 쉽습니다. (1) 문제의 높이 증가 높이가 하나 :-) 증가하는 빈도에 파티에 의존하는 경우
물론,
편집 : disjoint sets로, 중요이라는 작은 (낮은) 나무는 것이다 더 커질 수 있습니다.
죄송합니다. 유형을 언급하는 것을 완전히 잊었습니다. 나는 분리 된 세트에 대해 이야기합니다. – fdh