5장 - Forests/Find-Union

forest: 여러 개의 트리들을 모아놓은 것.

 

 

forest로 연결할 트리 A,E,G가 있다

이 트리들을 우선 이진트리로 바꾼다.(왼쪽-자식, 오른쪽-형제)

 

그럼 root노드는 형제가 없기 때문에, 이진트리에서 root의 오른쪽 자식은 항상 비게 된다

이 점을 이용해서, 여러 트리들을 root의 오른쪽 자식 노드로 연결-연결한다.

 

tree들을 forest로 표현 한 후의 inorder, preorder, postorder은 각각 어떻게 변할까?

inorder, preorder의 경우는 tree일때와 forest일 때가 동일하게 나오지만

postorder은 다르다!

 

Forest 순회 방법

preorder Traversal of Forest F

1. F가 empty이면 return
2. F의 첫번째 트리의 root를 방문
3. 첫번 째 트리의 서브트리들을 preorder로 순회
4. F의 나머지 트리들을 preorder로 순회

Inorder Traversal of Forest F

1. F가 empty이면 return
2. 첫번째 트리의 서브트리들을 inorder로 순회
3. F의 첫번째 트리의 root를 방문
4. F의 나머지 트리들을 inorder로 순회

preorder과 inorder 방법이 똑같은 것 같다?

 

---

집합 표현(set representation)

집합에 대한 연산

• disjoint set union(합치기)
• find(i) (원소가 어느 집합에 속해있는지 확인)

집합의 트리 표현 시

지금까지와는 다르게 자식들이 부모를 가리키는 구조가 된다.

int parent[10] = { -1, };

int find(int i) {
	for (; parent[i] >= 0; i = parent[i]); //-1값을 갖고있는 루트를 찾아서 반환
	return i;
}

void my_union(int i, int j)
{
	int pi;
	int pj;
	pi=find(i); //pi는 i의 부모
	pj = find(j);//pj는 j의 부모
	parent[pi] = pj;//루트를 변경
}

아주 간단한 코드.

그런데.. 이 코드를 사용하다 보면 부모를 찾기 위해 아주 긴 경로를 지나야 할 수도 있다.

 

노드 수가 많은 것이 부모가 되게 바꿔보자.

-> Union - by - rank

노드 수는 어떻게 기억하지?

부모노드는 -(음수)노드 개수 를 갖게 하면 된다.

void my_union(int i, int j)
{
	//입력받은 i,j는 루트라고 가정하자

	int temp = parent[i] + parent[j]; //총 원소개수
	if (parent[i] > parent[j]) { //노드 수는 음수로 저장하므로 j의 노드 수가 많은 경우이다.
		parent[i] = j;
		parent[j] = temp;
	}
	else {
		parent[j] = i;
		parent[i] = temp;
	}
}

그런데, 이 규칙을 적용하더라도 

2개씩 병합되는 경우 depth가 커져서 최대 log2n의 depth를 가질 수도 있게 된다.

이를 해결하기 위해 find(i)를 할 때마다 parent[i]를 갱신시켜주자.

 

int find(int i) {
	int root, node, next;
	for (root = i; parent[root] >= 0; root = parent[root])
		;//루트를 찾기
	for (node = i; node != root && parent[node] != root; node = next) {
		next = parent[node];
		parent[node] = root;
	}//루트 찾는 과정에 있는 모든 노드의 값을 root로 변경
	return root;
}

 

집합 표현을 이용한 동치 클래스 구현.