숲
숲의 개념
여러 개의 독립적인 트리(tree)로 구성된 집합을 의미하는 자료구조. 일반적으로는 앞서 설명한 개념과 같지만, 사전적으로는 트리가 하나인 집합이나, 트리가 아예 없는 공집합 또한 숲이라고 지칭할 수 있다.
숲은 n(n >= 0) 개 이상의 분리된 트리의 집합이다.
또한 하나의 트리에서 루트 노드를 제거하면 여러 개의 트리로 분할되므로, 손쉽게 숲을 얻을 수 있고, 반대로 여러 개의 트리를 하나의 루트로 묶으면 숲을 하나의 트리로도 만들 수 있다.
숲의 이진트리 변환
(1) 각 트리를 이진 트리로 바꾼다.
(2) 이때 TiBT의 루트는 왼쪽 서브트리만 가진다.
(3) TiBT의 루트를 최상위 루트로 하고
(4) 왼쪽 자식은 원래 가지고 있던 서브트리를 그대로,
(5) 그리고 오른쪽 자식은 나머지들의 이진 트리(BT2-n)가 되도록 한다.