[자료구조]트리/포레스트(forest), forest -> binary tree

[정의] forest는 n개의 disjoint tree의 집합이다

나무가 모이면 숲이 되듯, tree가 여러개 모이면 forest라고 부른다.

 

forest는 tree의 개념과 매우 유사한데, 이는 '트리에서 루트를 제거하면 포리스트가 되기 때문'이라고 한다???

 

ㅇㅎㅇㅎ...원래 이렇게 생긴 거였구나...

 

 

다음 단원에서 'disjoint set'을 표현하기 위해서 forest를 사용할것이라고 한다. 

[forest를  binary tree로 변환하기]

1. forest에 있는 각 트리를 이진트리로 변환한다.

2. 변환된 모든 binary tree를 root node의 rightChild 필드를 통해 연결한다.

 

그러면...

 

요렇게 된다.(아직 그림 안넣음)

 

이 변환은 이렇게 정의할 수 있다고 한다.

Tree1, Tree2, ..., TreeN이 합쳐진 binary tree, B(T1, ..., TN)은 

: Tree1과 같은 루트를 가지며, 왼쪽 서브트리로 B(T11, T12, ... T1m)을 갖는데 T11, T12,..., T1m은 T1의 루트의 서브트리들이다. 

오른쪽 서브트리로는 B(T2, ...Tn)을 갖는다.