Non-Binary Trees

General Trees

General Trees

Traversal

General Tree에서 Preorder Traversal과 Postorder Traversal은 정의가 된다.

그러나 Inorder Traversal은 binary tree에서는 정의가 되지만 non binary tree에서는 정의가 되지 않는다.

 

 

 

Equivalence Class Problem

determine if nodes in different trees

임의의 두 노드를 골랐을 때 두 노드가 같은 tree에 있는지 다른 tree에 있는지 어떻게 알아낼 수 있을까?

각 노드의 root를 비교해서 같다면 같은 tree에 있을 것이고, 다르다면 다른 tree에 있는 것일 것이다.

이때 root를 알아내는 operation을 Find라고 한다.

 

실제 생활에서 사용되는 예로는 SNS에서 나와 다른 사람이 공통적으로 아는 사람이 있는지 알아낼 때 사용이 된다.

 

 

Union/Find

Equivalence class problem을 해결하기 위하여 중요한 operation으로 UNION과 FIND가 있다.

UNION은 두개의 set을 합치는 것이고, FIND는 위에서 보았듯이 두 object가 같은 set에 있는지 확인하는 것이다.

 

Union

Union

 

두 개의 set에 있는 모든 원소들의 root를 하나의 root로 만든다. 이는 한 set에 있는 root의 parent를 다른 set에 있는 root로 만들면 된다.

 

UNION

여기서 FIND는 O(logn)이 걸린다(depth).

따라서 UNION의 시간은 두 tree의 depth에 영향을 받을 것이다.

 

따라서 UNION을 할 때 tree들의 depth를 작게 유지해야 효율적이다.

이를 위해서 tree를 합칠 때 depth가 작은 트리를 depth가 큰 트리에 연결을 시킨다.

Union

Weighted union rule : 적은 노드가 있는 tree를 노드가 많은 tree에 연결을 시킨다.

결과적으로 가장 height이 작은 tree를 반환한다.

 

Theorem : 

n개의 independent한 equivalence class에 속한 n개의 node가 있다고 하자.

Weighted union rule를 이용하여 Union operation을 차례로 진행시키면 tree의 depth는 아무리 커도 logn이하이다.

 

증명 :

제일 마지막 트리에 있는 가장 큰 깊이를 가진 노드 v를 생각해보자. 처음에는 v의 깊이도 0이었을 것이다. v의 깊이는 weighted union rule에 의하여 v가 속한 tree의 노드의 개수와 같거나 많은 tree와 합칠 때만 증가하게 된다.

따라서 v의 final depth는 v의 깊이가 증가하는 횟수와 같고(깊이는 합쳐질 때마다 최대 1만큼 커지므로), 그러므로 logn보다 작다.

 

 

Path Compression

FIND를 할 때 지나가는 node의 parent를 root로 바꿔버리는 것.

UNION(H,E)

위 그림처럼 UNION(H,E)를 한다고 하자.

그럼 FIND(H)로 A를 찾을 것이고, FIND(E)로 F를 찾을 것이다.

위에서 본 FIND는 root가 나올 때까지 parent node로 올라가기 때문에 FIND(H)를 수행하면서 H,C,A를 거치고, FIND(E)를 하면서 E,D,F를 거친다.

 

path compression은 이때 지나가는 모든 node들의 parent를 root로 바꿔버린다. 이렇게 하면 tree의 depth를 더 줄일 수 있다.

 

path compression을 이용한다면 Union을 많이 반복했을 때 tree의 depth가 1에 가깝게 되어 find operation이 O(1)밖에 걸리지 않는다.

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업