무게 및 경로 압축에 의한 경험적 발견

Question

일반적으로 순위 및 경로 압축에 의한 휴리스틱은 빠른 분리 세트 데이터 구조 작업을 수행하는 데 사용됩니다. 여하튼, 나는 무게와 경로 압축에 의한 경험적 발견이 나에게 더 현명하다는 것을 알게된다. 다음 구현은 순위 및 경로 압축을 통한 휴리스틱과 동일한 실행 시간을 얻습니까?

참고 : 구조 노드에 사용 순위는 잘못된, 그것은 아이의 수보다는 나무의 높이 (이 일반적으로 순위를 의미)

//using heuristics by weight and path compression to improve running time 
typedef struct n{ 
    struct n *parent; 
    int u,v,weight; 
    int rank;  //if node is the parent, it keeps track of number of children. if not, it is -1. 
}node; 

node* MAKE(int u, int v, int weight) 
{ 
    node *n=(node*)malloc(sizeof(node)); 
    n->parent=n; 
    n->u=u; 
    n->v=v; 
    n->weight=weight; 
    n->rank=0; 
    return n; 
} 

node *FIND(node *n) 
{ 
    if(n->parent==n) 
     return n; 
    n->parent=FIND(n->parent); 
    return n->parent; 
} 

void MERGE(node *n1, node *n2)  //merge n1 and n2 and store in n1. 
{ 
    assert(n1->rank!=-1); 
    assert(n2->rank!=-1); 
    if(n1->rank<n2->rank) 
    { 
     MERGE(n2,n1); 
     return ; 
    } 
    n2->parent=n1; 
    n1->rank=n1->rank+n2->rank+1; 
    n2->rank=-1; 
} 

Answer 1

당신은 모두 weight 및 rank 사용을 의미입니다 너의 구조에! weight에 의해 weighted-merge heuristic을 의미하는 경우, 보통은 rank입니다 (그리고 rank에 의해, 내가 지적한대로 나무의 높이를 의미하고 아이들의 수는 아닙니다).

어린이 수를 기록해도 최적화가 이루어지지 않습니다. Find의 복잡성은 입력 노드가있는 트리의 자식 수가 아닌 트리의 높이의 함수이기 때문에.

경로 압축의 이점이 있습니다.